For a fixed integer k≥ 0, given a planar graph G, decide whether there exists a family of pairwise interiorly disjoint, non-self-intersecting grid paths (P_v)_v∈ V(G) such that each P_v consists of at most k+1 axis-parallel line segments, and, for all distinct u,v∈ V(G), uv∈ E(G) if and only if P_u and P_v touch at a grid point. The source claims that this recognition problem is mathsfNP-complete for planar input graphs of maximum degree at most 8 when k=0, and of maximum degree at most 11 when k=1.

Planar B_k-CPG recognition problems

For a fixed integer $k\ge 0$ , given a planar graph $G$ , decide whether there exists a family of pairwise interiorly disjoint, non-self-intersecting grid paths $(P_v)_{v\in V(G)}$ such that each $P_v$ consists of at most $k+1$ axis-parallel line segments, and, for all distinct $u,v\in V(G)$ , $uv\in E(G)$ if and only if $P_u$ and $P_v$ touch at a grid point. The source claims that this recognition problem is $\mathsf{NP}$ -complete for planar input graphs of maximum degree at most $8$ when $k=0$ , and of maximum degree at most $11$ when $k=1$ .

References

Primary source

arXiv

Additional references

Resolving Two Open Problems of Planar B_k-CPG Recognition: k=0,1 — arXiv — Bin Sun, Shou-Jun Xu, Yu Yang

computational-complexity graph-theory

Posted 2 days ago · edited 2 days ago

Progress summary

Refreshed 2 days ago

Claimed progress

A new paper claims to settle two of the three remaining planar cases, but the claim has not been independently checked.

The problem concerns the computational complexity of recognizing planar contact graphs formed by grid paths with at most $k$ bends. Earlier work left three planar cases unresolved; the latest paper claims to resolve two of them.

Known results

Recognition is $\mathsf{NP}$ -complete for $B_0$ -CPG graphs.
Recognition is $\mathsf{NP}$ -complete for unrestricted $B_k$ -CPG graphs for every $k\ge 1$ .
Recognition is $\mathsf{NP}$ -hard for planar $B_k$ -CPG graphs when $k\ge 3$ .
The planar cases $k\le 2$ were explicitly left open.

October 5, 2026 claimed progress

Bin Sun, Shou-Jun Xu, and Yu Yang’s paper Resolving Two Open Problems of Planar $B_k$ -CPG Recognition: $k=0,1$ claims $\mathsf{NP}$ -completeness at the stated degree thresholds for planar $B_0$ - and $B_1$ -CPG recognition. If correct, only the third previously identified planar case remains open; the claim is unverified here.

Current status (as of October 2026): Two planar recognition cases are claimed resolved, one case remains open, and the new results have not been independently verified.

Sources

No solutions have been posted yet.