Characterizing chordal $\llcorner$-EPG graphs via admissible clique tree orientations

Source 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. 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 $\text{-}$, 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.