# Graph Planarity by Replacing Cliques with Paths +
## 3 NP-Completeness for Simple Topological 3-Plane Graphs  
In this section, we prove that the 4-C2 PP problem remains NP-complete even when the input is a simple topological 3-plane graph. Since the planarity of a simple topological graph can be checked in linear time, the \(h\)-C2 PP problem for simple topological \(k\)-plane graphs belongs to NP for all values of \(h\) and \(k\). In the following, we prove the NP-hardness by means of a reduction from the Planar Positive 1-in-3-SAT problem. In this version of the Satisfiability problem, which is known to be NP-complete [16], each variable appears only with its positive literal, each clause has at most three variables, the graph obtained by connecting each variable with all the clauses it belongs to is planar, and the goal is to find a truth assignment in such a way that, for each clause, exactly one of its three variables is set to True. Our reduction is technically different from the one presented in [15], which reduces from Planar 3-Satisfiability. Figure 2: A drawing produced by the reduction in [15]. The yellow region contains a variable gadget, the blue region contains a splitting gadget, the orange region contains a wire gadget, and the violet region contains an inverter gadget. For each 3-clique we use in the reduction, there is a _base edge_, which is crossing-free in the constructed topological graph, while the other two edges always have crossings. We call _left_ (_right_) the edge that follows (precedes) the base edge in the clockwise order of the edges along the 3-clique. In addition, if an edge \(e\) of a clique does not belong to the path replacing the clique, we say that \(e\) is _removed_, and that all the crossings involving \(e\) in \(G\) are _resolved_. For each variable \(x\), let \(n_{x}\) be the number of clauses containing \(x\). We construct a simple topological graph gadget \(G_{x}\) for \(x\), called _variable gadget_ (see the left dotted box in Figure 3a). This gadget contains \(2n_{x}\) 3-cliques \(t_{1}^{x},\ldots,t_{2n_{x}}^{x}\), forming a ring, so that the left (right) edge of \(t_{i}^{x}\) only crosses the left (right) edge of \(t_{i-1}^{x}\) and of \(t_{i+1}^{x}\), for each \(i=1,\ldots,2n_{x}\). In addition, gadget \(G_{x}\) contains \(n_{x}\) additional 3-cliques, called \(\tau_{1}^{x},\ldots,\tau_{n_{x}}^{x}\), so that the right edge of \(\tau_{j}^{x}\) crosses the left edge of \(t_{2j-1}^{x}\) and the right edge of \(t_{2j}^{x}\), while the left edge of \(\tau_{j}^{x}\) crosses the left edge of \(t_{2j}^{x}\) and the right edge of \(t_{2j-1}^{x}\). Then, for each clause \(c\), we construct a simple topological graph gadget \(G_{c}\), called _clause gadget_, which is composed of a planar drawing of a 4-clique, together with three 3-cliques whose left and right edges cross the edges of the 4-clique as in the right dotted box in Figure 3a. In particular, observe that the right (left) edge of each 3-clique crosses exactly one (two) edges of the 4-clique. Every 3-clique in \(G_{c}\) corresponds to one of the three variables of \(c\). Let \(x\) be one of such variables; assuming that \(c\) is the \(j\)th clause that contains \(x\) according to the order of the clauses in the given  
Figure 3: **(a)** The variable gadget \(G_{x}\) for a variable \(x\) is represented in the left dotted box. The clause gadget for a clause \(c\) is represented in the right dotted box. The chain connecting \(G_{x}\) to \(G_{c}\) is represented with lighter colors. The removed edges are dashed red. **(b)** All variables are False. **(c)** At least two variables are True. formula, we connect the 3-clique corresponding to \(x\) in the clause gadget \(G_{c}\) to the 3-clique \(\tau^{x}_{j}\) of the variable gadget \(G_{x}\) of \(x\) by a chain of 3-cliques of odd length, as in Figure 2(a). By construction, the resulting simple topological graph \(G\) contains cliques of size at most 4, namely one per clause, and hence is a valid instance of 4-C2 PP.