# Graph Planarity by Replacing Cliques with Paths +
## 3 NP-Completeness for Simple Topological 3-Plane Graphs
If the right edge is removed, we assign value True to variable \(x\), otherwise we assign False. To prove that this assignment results in a solution for the given formula of Planar Positive 1-in-3-SAT, we first show that, for each clause \(c\) that contains variable \(x\), the right (left) edge of the 3-clique \(t_{c}(x)\) of the clause gadget \(G_{c}\) corresponding to \(x\) is removed if and only if the right (left) edge of each 3-clique \(\tau^{x}_{j}\) is removed. Namely, consider the chain that connects \(t_{c}(x)\) with a 3-clique \(\tau^{x}_{j}\) of \(G_{x}\). Note that, for any two consecutive 3-cliques along the chain, the left edge of one 3-clique and the right edge of the other 3-clique must be removed. Since the chain has odd length, the right (left) edge of \(t_{c}(x)\) is removed if and only if the right (left) edge of \(\tau_{j}^{x}\) is removed, that is, the truth value of \(G_{x}\) is transferred to the 3-clique \(t_{c}(x)\) of \(G_{c}\). Finally, consider any clause \(c\), composed of variables \(x\), \(y\), and \(z\). Let \(t_{c}(x)\), \(t_{c}(y)\), and \(t_{c}(z)\) be the three 3-cliques of the clause gadget \(G_{c}\) of \(c\) corresponding to \(x\), \(y\), and \(z\), respectively; also, let \(v\) be the central vertex of the 4-clique of \(G_{c}\), and let \(v_{x}\), \(v_{y}\), and \(v_{z}\) be the vertices of this 4-clique lying inside \(t_{c}(x)\), \(t_{c}(y)\), and \(t_{c}(z)\), respectively; see Figure 3. We assume without loss of generality that \(v_{x}\), \(v_{y}\), and \(v_{z}\) appear in this clockwise order around \(v\). As discussed above, the left or the right edge of \(t_{c}(x)\) (of \(t_{c}(y)\); of \(t_{c}(z)\)) is removed depending on whether the left or the right edge of each \(\tau_{j}^{x}\) (of each \(\tau_{j}^{y}\); of each \(\tau_{j}^{z}\)) is removed. We show that, for exactly one of \(t_{c}(x)\), \(t_{c}(y)\), and \(t_{c}(z)\) the right edge is removed, which then implies that exactly one of \(x\), \(y\), and \(z\) is True, and hence the instance of Planar Positive 1-in-3-SAT is positive. Suppose first that for each of \(t_{c}(x)\), \(t_{c}(y)\), and \(t_{c}(z)\) the left edge is removed (and hence all the three variables are set to False), as in Figure 3b. This implies that the crossings between the right edges of the three 3-cliques and the three edges of triangle \((v_{x},v_{y},v_{z})\) are not resolved. Hence, all the edges of this triangle should be removed, which is not possible since the remaining edges of the 4-clique do not form a path. Suppose now that for at least two of \(t_{c}(x)\), \(t_{c}(y)\), and \(t_{c}(z)\), say \(t_{c}(x)\) and \(t_{c}(y)\), the right edge is removed (and hence \(x\) and \(y\) are set to True), as in Figure 3c. Since each edge of triangle \((v_{x},v_{y},v)\) is crossed by the left edge of one of \(t_{c}(x)\) and \(t_{c}(y)\), by construction, these crossings are not resolved. Hence, all the edges of \((v_{x},v_{y},v)\) should be removed, which is not possible since the remaining edges of the 4-clique do not form a path of length 4. Suppose finally that for exactly one of \(t_{c}(x)\), \(t_{c}(y)\), and \(t_{c}(z)\), say \(t_{c}(x)\), the right edge is removed (and hence \(x\) is the only one to be set to True), as in Figure 3a. Then, by removing edges \((v,v_{x})\), \((v_{x},v_{y})\), and \((v_{y},v_{z})\), all the crossings are resolved and the remaining edges of the 4-clique form a path of length 4, as desired. The proof of the other direction is analogous. Namely, suppose that there exists a truth assignment that assigns a True value to exactly one variable in each clause. Then, for each variable \(x\) that is set to True (to False), we remove the right (left) edge of each 3-clique \(t_{i}^{x}\), with \(i=2j-1\) and \(j=1,\ldots,n_{x}\), we remove the left (right) edge of each 3-clique \(t_{i}^{x}\), with \(i=2j\) and \(j=1,\ldots,n_{x}\), and we remove the right (left) edge of each 3-clique \(\tau_{j}^{x}\), with \(j=1,\ldots,n_{x}\).