Skip to content
DraconiticResearch
Search Sources API
203,234 studies31 sourcesUpdated 17 min ago
PreprintarXiv licencearXiv

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

  • Bin Sun
  • Shou-Jun Xu
  • Yu Yang
Open at sourcePDFDOICite

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 Bk-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 B0-CPG graphs of maximum degree 8 is NP-complete, and that recognizing planar B1-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.

Related

  1. Markov Chain CLTs: Resolving Open Problems
    Austin Brown, Jeffrey S. Rosenthal, Quan Zhou
    arXivPreprintarXiv licenceFull textProbabilityStatisticsarXiv
  2. Planar Obliquely Reflected BSVIs on General Filtered Spaces: Non-Symmetric Rotation Fields and Associated Control Problems
    Andreea Negruţ, Aurel Răşcanu, Eduard Rotenstein
    arXivPreprintCC BY-NC-ND 4.0Full textProbabilityarXiv
  3. Spectral extremal problems on 1-planar graphs without Friendship graph
    Jiamin Li, Dan Li, Yuanyuan Chen
    arXivPreprintarXiv licenceFull textCombinatorics & discrete mathematicsarXiv
  4. Open Inextensible Filaments in Planar Stokes Flow: Well-Posedness, Endpoint Asymptotics, and Straightening
    Han Zhou
    arXivPreprintCC BY 4.0Full textAnalysis & PDEsMathematical physicsarXiv
  5. On Two Open Problems by Johnson and Kollár
    Siyuan Fu, Zhiming Li, Huaiqing Zuo
    arXivPreprintCC BY 4.0Full textAlgebra & number theoryarXiv

Cite

BibTeXRIS
BibTeX
@misc{sun2026resolving,
  title = {{Resolving Two Open Problems of Planar $B_k$-CPG Recognition: $k=0,1$}},
  author = {Bin Sun and Shou-Jun Xu and Yu Yang},
  howpublished = {arXiv},
  year = {2026},
  month = oct,
  doi = {10.48550/arxiv.2610.05838},
  eprint = {2610.05838},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2610.05838},
}
RIS
TY  - UNPB
TI  - Resolving Two Open Problems of Planar B_k-CPG Recognition: k=0,1
AU  - Bin Sun
AU  - Shou-Jun Xu
AU  - Yu Yang
PY  - 2026
DA  - 2026/10/05
PB  - arXiv
DO  - 10.48550/arxiv.2610.05838
UR  - https://arxiv.org/abs/2610.05838
AB  - 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.
ER  -