平面 3 SAT
3 SAT を表すグラフが平面グラフになるよう制限したもの
平面 3 SATから帰着して他のn-上界 3 SATを構成すると（平面グラフになることが保証されているので）図が書きやすくて便利
帰着に用いたガジェットは非平面SATからの帰着にも使える
3 SAT を表すグラフ
黒い四角が節
丸い点が変数を表す
変数が節に含まれる場合は辺で結ぶ
負リテラルが節に含まれる場合は赤線で結ぶ
同じ変数が複数の節に含まれる場合は、同じ変数から複数の辺が伸びていく
下の図は$ \lbrace\lbrace x,\lnot y,z\rbrace\rbraceを表す
https://scrapbox.io/files/649d839d1f30ea001c015402.png
グラフ表示が平面上に描けるので、節を3頂点保有するハイパーエッジにしたハイパーグラフ表現でも平面上に描ける
コッチの表現を先に思いついたから否定をグラフ上に描きたくないとか全て三角で表したいとかで、平面 正 linear exactly 1-in-3 SAT でもNP完全のままかどうか検証してた
https://scrapbox.io/files/649df11ca71df7001b10d0ae.png
平面 3 SAT への帰着
重なった部分を平面グラフにカッコいいガジェット(cross over gadget)を使って埋め込む