{"id":"arxiv/2610.05838","url":"https://arxiv.org/abs/2610.05838","tags":["math.CO"],"score":0,"title":"Resolving Two Open Problems of Planar $B_k$-CPG Recognition: $k=0,1$","domain":"math.CO","source":"arxiv","authors":["Bin Sun","Shou-Jun Xu","Yu Yang"],"reviews":0,"subject":"math.CO","summary":"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…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-10-05","reactions":{}}