Planar SAT

In other words, it asks whether the variables of a given Boolean formula—whose incidence graph consisting of variables and clauses can be embedded on a plane—can be consistently replaced by the values TRUE or FALSE in such a way that the formula evaluates to TRUE.

If this is the case, the formula is called satisfiable.

On the other hand, if no such assignment exists, the function expressed by the formula is FALSE for all possible variable assignments and the formula is unsatisfiable.

Like 3SAT, PLANAR-SAT is NP-complete, and is commonly used in reductions.

Every 3SAT problem can be converted to an incidence graph in the following manner: For every variable

Positive and negative literals are distinguished using edge colorings.

The formula is satisfiable if and only if there is a way to assign TRUE or FALSE to each variable node such that every clause node is connected to at least one TRUE by a positive edge or FALSE by a negative edge.

It is important because it is a restricted variant, and is still NP-complete.

Many problems (for example games and puzzles) cannot represent non-planar graphs.

Hence, Planar 3SAT provides a way to prove those problems to be NP-hard.

It is thus sufficient to show that it is NP-hard via reduction from 3SAT.

First, draw the incidence graph of the 3SAT formula.

Since no two variables or clauses are connected, the resulting graph will be bipartite.

Suppose the resulting graph is not planar.

For every crossing of edges (a, c1) and (b, c2), introduce nine new variables a1, b1, α, β, γ, δ, ξ, a2, b2, and replace every crossing of edges with a crossover gadget shown in the diagram.

α ∨ β ∨ γ ∨ δ

( ¬ α ∨ ¬ β ) ∧ ( ¬ β ∨ ¬ γ ) ∧ ( ¬ γ ∨ ¬ δ ) ∧ ( ¬ δ ∨ ¬ α ) ,

One can easily show that these clauses are satisfiable if and only if

This algorithm shows that it is possible to convert each crossing into its planar equivalent using only a constant amount of new additions.

Since the number of crossings is polynomial in terms of the number of clauses and variables, the reduction is polynomial.

[2] Reduction from Planar SAT is a commonly used method in NP-completeness proofs of logic puzzles.

Examples of these include Fillomino,[10] Nurikabe,[11] Shakashaka,[12] Tatamibari,[13] and Tentai Show.

[14] These proofs involve constructing gadgets that can simulate wires carrying signals (Boolean values), input and output gates, signal splitters, NOT gates and AND (or OR) gates in order to represent the planar embedding of any Boolean circuit.

Since the circuits are planar, crossover of wires do not need to be considered.

This is the problem of deciding whether a polygonal chain with fixed edge lengths and angles has a planar configuration without crossings.

It has been proven to be strongly NP-hard via a reduction from planar monotone rectilinear 3SAT.

[15] This is the problem of partitioning a polygon into simpler polygons such that the total length of all edges used in the partition is as small as possible.

But if it contains holes (even degenerate holes—single points), the problem is NP-hard, by reduction from Planar SAT.

[16] A related problem is minimum-weight triangulation - finding a triangulation of minimal total edge length.

The decision version of this problem is proven to be NP-complete via a reduction from a variant of Planar 1-in-3SAT.

Graph of the formula (x_1 or not x_2) and (not x_1 or x_2 or not x_3)
Example of a planar SAT problem. The black edges correspond to non-inverted variables and the red edges correspond to inverted variables.
Graph with black and red edges
Left side is a crossing; right side is the crossover gadget. The small dots represent clauses. The black and red edges correspond to non-inverted and inverted variables respectively.