# Planarity conditions for Planar 1-in-3 SAT

Planar 3SAT is NP-complete. A planar 3SAT instance is a 3SAT instance for which the graph built using the following rules is planar:

1. add a vertex for every $x_i$ and $\bar{x_i}$
2. add a vertex for every clause $C_j$
3. add an edge for every $(x_i,\bar{x_i})$ pair
4. add an edge from vertex $x_i$ (or $\bar{x_i}$) to each vertex that represent a clause that contains it
5. 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})$ ?
• Just in case if anyone would be looking for the paper where they show hardness of Planar 1-in-3SAT (less stronger version). Here is a link: dl.acm.org/citation.cfm?doid=1137856.1137859 From their proof one can see that the "backbone" requirement is easily met. – sud03r Mar 22 '17 at 3:44

Yes you can. Actually you can even show that something stronger is true. The problem know as Positive Planar 1-in-3-SAT is NP-complete as shown by Mulzer and Rote.

In this version of 1-in-3-SAT, you require for every input formula that

• you have three variables per clause, none of them negated
• the graph of the formula is planar, even if you add the "backbone" between the variable vertices

The reduction is from Planar 3-SAT.