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

Bin Sun, Shou-Jun Xu, Yu Yang

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 b…