# Graph Planarity by Replacing Cliques with Paths +
## 3 NP-Completeness for Simple Topological 3-Plane Graphs
In addition, by collapsing each variable and clause gadget into a vertex, and each chain connecting them into an edge, the resulting graph \(G^{\prime}\) preserves the planarity of the Planar Positive 1-in-3-SAT instance. This implies that the only crossings for each edge of \(G\) are with other edges in the gadget it belongs to and, possibly, with the edges of the 3-cliques of a chain. Hence, \(G\) is 3-planar. Namely, each base edge is crossing-free; each internal edge of a 4-clique has one crossing; each external edge of a 4-clique has two crossings, and the same is true for the left and right edges of each 3-clique in a chain; finally, the left and right edges of each 3-clique in either a variable or a clause gadget have three crossings. In the following, we prove the equivalence between the original instance of Planar Positive 1-in-3-SAT and the constructed instance \(G\) of 4-C2 PP. For this, we first give a lemma stating that variable gadgets correctly represent the behavior of a variable; indeed, they can assume one out of two possible states in any solution for 4-C2 PP. Lemma 1: _Let \(G_{x}\) be the variable gadget for a variable \(x\) in \(G\). Then, in any solution for 4-C2 PP, either the left edge of each 3-clique \(\tau^{x}_{j}\), with \(j=1,\ldots,n_{x}\), is removed, or the right edge of each 3-clique \(\tau^{x}_{j}\) is removed._  
Proof: We first consider the possible removals of edges in \(t^{x}_{1},\ldots,t^{x}_{2n_{x}}\) and claim that, in any solution for 4-C2 PP, one of the two following conditions are satisfied: (i) for each 3-clique \(t^{x}_{i}\), if \(i\) is odd, then the left edge is removed, while if \(i\) is even the right edge is removed; and (ii) for each 3-clique \(t^{x}_{i}\), if \(i\) is odd, then the right edge is removed, while if \(i\) is even the left edge is removed. Note that this claim is sufficient to prove the statement; in fact, if Condition (i) holds (as in Figure 2(a)), then the right edge of each 3-clique \(\tau^{x}_{j}\) must be removed, in order to resolve its crossings with the right edge of \(t^{x}_{2j-1}\) and with the left edge of \(t^{x}_{2j}\), while if Condition (ii) holds, then the left edge of each 3-clique \(\tau^{x}_{j}\) must be removed, in order to resolve its crossings with the left edge of \(t^{x}_{2j-1}\) and with the right edge of \(t^{x}_{2j}\). To prove the claim, we consider the possible removals of edges of \(t^{x}_{1}\). Suppose first that the base edge of \(t^{x}_{1}\) is removed. Thus, the crossings between the left (right) edge of \(t^{x}_{1}\) and the left (right) edge of \(t^{x}_{2}\) are not resolved; this implies that they have to be resolved by removing both the left and the right edge of \(t^{x}_{2}\), which is not possible. If the right edge of \(t^{x}_{1}\) is removed, then the crossing between the right edges of \(t^{x}_{1}\) and \(t^{x}_{2}\) is resolved, while the one between their left edges is not. Hence, the left edge of \(t^{x}_{2}\) must be removed. By iterating this argument we conclude that the right (left) edge of each \(t^{x}_{i}\) with \(i\) odd (even) is removed. Symmetrically, we can prove that, if the left edge of \(t^{x}_{1}\) is removed, then the left (right) edge of each \(t^{x}_{i}\) with \(i\) odd (even) is removed. This concludes the proof of the lemma. Given Lemma 1, we can associate the truth value of a variable \(x\) with the fact that either the left or the right edge of each 3-clique \(\tau^{x}_{j}\) in the variable gadget \(G_{x}\) of \(G\) is removed. We use this association to prove the following theorem. Theorem 1: _The 4-C2 PP problem is NP-complete, even for 3-plane graphs._  
Proof: Given an instance of Planar Positive 1-in-3-SAT, we construct an instance \(G\) of 4-C2 PP in linear time as described above. We prove their equivalence. Suppose first that there exists a solution for 4-C2 PP, i.e., a set of edges of \(G\) whose removal resolves all crossings. By Lemma 1, for each variable \(x\) either the left or the right edge of each 3-clique \(\tau^{x}_{j}\) in the variable gadget \(G_{x}\) is removed.