Characterizing chordal llcorner-EPG graphs via admissible clique tree orientations

@misc{sun2026characterizing,
  title = {{Characterizing chordal $\llcorner$-EPG graphs via admissible clique tree orientations}},
  author = {Bin Sun and Shou-Jun Xu and Yu Yang},
  howpublished = {arXiv},
  year = {2026},
  month = oct,
  doi = {10.48550/arxiv.2610.09443},
  eprint = {2610.09443},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2610.09443},
}

TY  - UNPB
TI  - Characterizing chordal llcorner-EPG graphs via admissible clique tree orientations
AU  - Bin Sun
AU  - Shou-Jun Xu
AU  - Yu Yang
PY  - 2026
DA  - 2026/10/07
PB  - arXiv
DO  - 10.48550/arxiv.2610.09443
UR  - https://arxiv.org/abs/2610.09443
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. An llcorner-EPG graph is a graph whose vertices can be represented by 1-bend paths on a grid, where each path is either llcorner, shortmid, or −, such that two vertices are adjacent if and only if the corresponding paths share at least one grid edge. Characterizing chordal llcorner-EPG graphs was explicitly posed as an open problem by Cameron, Chaplick, and Hoàng. We resolve this by giving two equivalent characterizations of connected chordal llcorner-EPG graphs. The first assigns to every connected chordal llcorner-EPG graph an ordered clique partition tree of its vertex set, where the underlying tree is the bipartite incidence graph of the horizontal and vertical edge-intersection components. The second is stated purely in terms of maximal cliques: a connected chordal graph is llcorner-EPG if and only if some clique tree admits an admissible partial orientation. A reduction lemma replaces local clique labels by maximal cliques, linking the two characterizations. For a prescribed clique tree, the existence of an admissible partial orientation reduces to 2-SAT and is decided in O(nM^2) time, where n and M are the numbers of vertices and maximal cliques. Finally, we show that strong chordality is not sufficient: we exhibit a strongly chordal graph that is a minimal forbidden induced subgraph for llcorner-EPG, and a family of split graphs with a unique clique tree for which membership in llcorner-EPG reduces to a neighborhood condition.
ER  -