<p>There's a nice compilation of definitions of related NP-complete planar satisfiability problems at <a href="http://courses.csail.mit.edu/6.890/fall14/scribe/lec7.pdf">http://courses.csail.mit.edu/6.890/fall14/scribe/lec7.pdf</a></p>

<p>One of them, planar monotone 3-sat, allows you to split each terminal into positive and negative, with the terminals placed along a line with the positive part on one side of the line and the negative part on the other side of the line. The clauses have only positive or only negative terminals and are placed on the positive or negative side of the line respectively.</p>

CC BY-SA 3.0
2016-01-12T16:18:48.427Z
2016-01-12T16:18:48.427Z
David Eppstein
<p>What is the standard definition of Planar 3-SAT? I have seen a number of different definitions. What was the original paper that defined it and proved it to be NP-complete?</p>

CC BY-SA 3.0
2014-07-22T16:24:05.197Z
What did you find confusing about the results?
Niel de Beaudrap
CC BY-SA 3.0
2014-07-22T16:43:02.237Z
I see different definitions, like some says: The bipartite graph between clauses and the literals must be planar (i don't know by literals do they mean only x_i's or both x_i and its negation, I mean i don't know what is their gadget graph exactly here?). Some other define two types for it: only the bipartite edges between clauses and literals, or these plus (x_i, ~x_i). Or some other says, the above graph plus the (x_i,x_{i+1})'s? I can not even find the original paper published on it? Basically I can not find a good reference with a perfect definition for it?
user24175
CC BY-SA 3.0
2014-07-22T18:02:43.003Z
The original reference is: [D. Lichtenstein, "Planar formulae and their uses" (1982)](http://general-k-cut.googlecode.com/svn/trunk/articles/planar_formulate_and_their_uses(d.lichtenstein).pdf); but there are many small variations that are still NP-complete (the NPC proof of most of them is easy).
Marzio De Biasi
CC BY-SA 3.0
2014-07-22T18:38:35.957Z
@Marzio De Biasi Thank you so much! But, based on this paer, planar 3-SAT is the case that the bipartite graph between the clauses that literals (only x_i's not their negations) is planar. Right? We can easily conclude the case that we include also the negation of x_i's just by adding an edge between them, without disturbing the planarity, right?
user24175
CC BY-SA 3.0
2014-07-22T18:45:37.873Z
@user24175: yes, you can split the $x_i$ node in $+x_i, -x_i$
Marzio De Biasi
CC BY-SA 3.0
2014-07-22T18:47:56.907Z
@ Marzio De Biasi Thank you so much again!
user24175
CC BY-SA 3.0
2016-01-12T14:00:31.640Z
@Marzio Do you happen to have a reference for the claim that it's possible to split the $x_i$ into positive and negative vertices? It's not trivial as far as I can see it, and currently I'm unable to find a paper on this in the jungle of 3-SAT publications. :(
Lukas Barth
CC BY-SA 3.0
2016-01-14T21:47:51.743Z
@tinLoaf: as cited in the very good lecture linked by David Eppstein in his answer, you can look at Mark de Berg and Amirali Khosravi, Optimal Binary Space Partitions in the Plane; in which it is proved that *monotone planar 3-SAT* is NPC: variables are placed on a horizontal line, all positive clauses are drawn above, all negative clauses are drawn below; in that representation it is easy to replace each variable $x_i$ with two stacked (and also linked) literals, the positive literal $+x_i$ above, the negative literal $-x_i$ below, without breaking planarity condition.
Marzio De Biasi
<cc.complexity-theory><reference-request><np-hardness><sat><planar-graphs>
Definition of Planar 3-SAT
user24175
# Definition of Planar 3-SAT

(Asked by: username_0 on 2014-07-22)

What is the standard definition of Planar 3-SAT? I have seen a number of different definitions. What was the original paper that defined it and proved it to be NP-complete?

**Tags:** cc.complexity-theory, reference-request, np-hardness, sat, planar-graphs
> **Comments:**
> **username_1**: What did you find confusing about the results?  
> **username_0**: I see different definitions, like some says: The bipartite graph between clauses and the literals must be planar (i don't know by literals do they mean only x_i's or both x_i and its negation, I mean i don't know what is their gadget graph exactly here?). Some other define two types for it: only the bipartite edges between clauses and literals, or these plus (x_i, ~x_i). Or some other says, the above graph plus the (x_i,x_{i+1})'s? I can not even find the original paper published on it? Basically I can not find a good reference with a perfect definition for it?  
> **username_2**: The original reference is: [D. Lichtenstein, "Planar formulae and their uses" (1982)](http://general-k-cut.googlecode.com/svn/trunk/articles/planar_formulate_and_their_uses(d.lichtenstein).pdf); but there are many small variations that are still NP-complete (the NPC proof of most of them is easy).  
> **username_0**: @Marzio De Biasi Thank you so much! But, based on this paer, planar 3-SAT is the case that the bipartite graph between the clauses that literals (only x_i's not their negations) is planar. Right? We can easily conclude the case that we include also the negation of x_i's just by adding an edge between them, without disturbing the planarity, right?  
> **username_2**: @user24175: yes, you can split the $x_i$ node in $+x_i, -x_i$  
> **username_0**: @ Marzio De Biasi Thank you so much again!  
> **username_3**: @Marzio Do you happen to have a reference for the claim that it's possible to split the $x_i$ into positive and negative vertices? It's not trivial as far as I can see it, and currently I'm unable to find a paper on this in the jungle of 3-SAT publications. :(  
> **username_2**: @tinLoaf: as cited in the very good lecture linked by David Eppstein in his answer, you can look at Mark de Berg and Amirali Khosravi, Optimal Binary Space Partitions in the Plane; in which it is proved that *monotone planar 3-SAT* is NPC: variables are placed on a horizontal line, all positive clauses are drawn above, all negative clauses are drawn below; in that representation it is easy to replace each variable $x_i$ with two stacked (and also linked) literals, the positive literal $+x_i$ above, the negative literal $-x_i$ below, without breaking planarity condition.  

---

## 1 answers

### Answer by username_4 on 2016-01-12. Score: 12

There's a nice compilation of definitions of related NP-complete planar satisfiability problems at <http://courses.csail.mit.edu/6.890/fall14/scribe/lec7.pdf>

One of them, planar monotone 3-sat, allows you to split each terminal into positive and negative, with the terminals placed along a line with the positive part on one side of the line and the negative part on the other side of the line. The clauses have only positive or only negative terminals and are placed on the positive or negative side of the line respectively.


---

