CPG graphs: some structural and hardness results (Q827595)

A grid graph is the Cartesian product of two paths. Two paths \(P\) and \(P^\prime\) touch (in a grid graph) if \(V(P)\cap V(P^\prime)=\{v\}\) for an end-vertex \(v\) of one of \(P\) or \(P^\prime\). A graph \(G\) is a contact graph of paths on a grid, shortly CPG graph, if there exist a collection of paths on a grid that present vertices of \(G\). Two vertices of \(G\) are adjacent the corresponding paths touch. Let \(G\) be a CPG graph and let \(\mathcal{G}\) be the corresponding grid and \(\mathcal{P}\) the corresponding path collection. If every path from \(\mathcal{P}\) bends for 90 degrees at most \(k\geq 0\) times on \(\mathcal{G}\), then \(G\) is a \(B_k\)-CPG graph. Present work brings several complexity results for \(B_k\)-CPG graphs. One of the results is that the recognition of \(B_k\)-CPG graph belongs to the class of NP-complete problems for any \(k\geq 1\) and that it remains in this class even if we restrict to planar graphs for any \(k\geq 3\).