Skip to content
Preprint

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

Oct 2026 · 0 citations · 17 references
Mathematics

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.

View source

We use cookies to run the site and, with your consent, for analytics and to show ads. See our Cookie Policy.