Planar 3SAT is NP-complete. A planar 3SAT instance is a 3SAT instance for which the graph built using the following rules is planar:
- add a vertex for every $x_i$ and $\bar{x_i}$
- add a vertex for every clause $C_j$
- add an edge for every $(x_i,\bar{x_i})$ pair
- add an edge from vertex $x_i$ (or $\bar{x_i}$) to each vertex that represent a clause that contains it
- add edges between two consecutive variables $(x_1,x_2),(x_2,x_3),...,(x_n,x_1)$
In particular, rule 5 builds a "backbone" that splits the clauses in two distinct regions.
Planar 1-in-3 SAT is NP-complete, too.
But for planar 1-in-3 SAT are the planarity conditions defined in the same way as in Planar 3SAT ? In particular, can we assume that there is a backbone that links the variables $(x_i,x_{i+1})$ ?