Resolving Two Open Problems of Planar $B_k$-CPG Recognition: $k=0,1$

Abstract

A $k$-bend path is a non-self-intersecting polyline that lies on a grid and consists of at most $k+1$ axis-parallel line segments. A $B_k$-CPG graph is a graph whose vertices can be represented by pairwise interiorly disjoint $k$-bend paths on a grid such that two vertices are adjacent if and only if the corresponding grid paths touch at a grid point. We prove that recognizing planar $B_0$-CPG graphs of maximum degree 8 is NP-complete, and that recognizing planar $B_1$-CPG graphs of maximum degree 11 is NP-complete. These results settle two of the three planar recognition problems left open by Champseix, Galby, Munaro, and Ries.

arXiv comment20 pages, 8 figures