# Graph Planarity by Replacing Cliques with Paths +
## 2 Relationship between _h_-Clique2 Path Planarity and the Partition Spanning Forest Problem  
The input of the problem studied by [PERSON] et al. [15] is a set of colored points in the plane, and the goal is to decide whether there exist straight-line spanning trees, one for each same-colored point subset, that do not cross each other. Since edges are straight-line, their drawings are determined by the positions of the points, and hence each same-colored point subset can, in fact, be seen as a straight-line drawing of a clique, from which edges have to be removed so that each clique becomes a tree and the drawing becomes planar.  
The authors proved NP-completeness for the case in which the spanning tree is a path, even when there are at most four vertices with the same color. This result implies that 4-C2 PP for geometric graphs is NP-complete. On the other hand, they provided a linear-time algorithm when there exist at most three vertices with the same color, which then extends to 3-C2 PP for geometric graphs.  
Although not explicitly mentioned in [15], the drawings produced by the reduction used to prove the NP-completeness of 4-C2 PP for geometric graphs are 4-planar. We now provide some details about this reduction.  
The authors of [15] performed a polynomial-time reduction from Planar 3-Satisfiability. The variable gadget (shown in the yellow region of Figure 1) consists of a triangle \(X\) whose edges are \(x\), \(x_{l}\), and \(x_{r}\). Edge \(x\) is crossing-free and the truth value of \(X\) is encoded according to which edgeamong \(x_{l}\) and \(x_{r}\) is crossing-free. Let \(T_{1}\) and \(T_{2}\) be two triangles whose vertices are \(u,y,z\) and \(v,y,z\), respectively. They define two faces \(f_{1}\) and \(f_{2}\), respectively. Concatenate a triangle \(T_{3}\) defined as in the variable gadget with \(f_{1}\) by inserting its crossing-free edge \((y,z)\) inside \(f_{1}\) and by crossing the other two edges of \(T_{3}\) with \((u,y)\) and \((u,z)\), respectively. Now, concatenate another triangle \(T_{4}\) defined as in the variable gadget with \(f_{2}\). If the crossing-free edge of \(T_{4}\) is inside \(f_{2}\), the gadget composed by \(T_{1},T_{2},T_{3}\) and \(T_{4}\) is the wire gadget; if the crossing-free edge of \(T_{4}\) is outside \(f_{2}\), the gadget composed by \(T_{1},T_{2},T_{3}\) and \(T_{4}\) is the inverter gadget. The splitting gadget consists of three variable gadgets \(X,Y\) and \(Z\), and two 4-cliques, concatenated as illustrated inside the blue region in Figure 2, where the yellow region contains a variable gadget, the orange region contains a wire gadget and the violet region contains an inverter gadget. As shown in Figure 2, multiple splittings of a variable \(X\) lead to an instance where a triangle has two edges with four crossings.  
The NP-completeness of 4-C2 PP for geometric graphs implies the NP-completeness of 4-C2 PP for simple topological 4-plane graphs. In what follows, we further explore the complexity of 4-C2 PP in relation to \(k\)-planarity by considering values of \(k<4\). In particular, we prove that the problem remains NP-complete for \(k=3\), while it becomes linear-time solvable for \(k=1\).