Edge Intersection Graphs of L-Shaped Paths in Grids

In this paper we continue the study of the edge intersection graphs of one (or zero) bend paths on a rectangular grid. That is, the edge intersection graphs where each vertex is represented by one of the following shapes: $llcorner$,$ulcorner$, $urcorner$, $lrcorner$, and we consider zero bend paths (i.e., | and $-$) to be degenerate $llcorner$s. These graphs, called $B_1$-EPG graphs, were first introduced by Golumbic et al (2009). We consider the natural subclasses of $B_1$-EPG formed by the subsets of the four single bend shapes (i.e., {$llcorner$}, {$llcorner$,$ulcorner$}, {$llcorner$,$urcorner$}, and {$llcorner$,$ulcorner$,$urcorner$}) and we denote the classes by [$llcorner$], [$llcorner$,$ulcorner$], [$llcorner$,$urcorner$], and [$llcorner$,$ulcorner$,$urcorner$] respectively. Note: all other subsets are isomorphic to these up to 90 degree rotation. We show that testing for membership in each of these classes is NP-complete and observe the expected strict inclusions and incomparability (i.e., [$llcorner$] $subsetneq$ [$llcorner$,$ulcorner$], [$llcorner$,$urcorner$] $subsetneq$ [$llcorner$,$ulcorner$,$urcorner$] $subsetneq$ $B_1$-EPG; also, [$llcorner$,$ulcorner$] is incomparable with [$llcorner$,$urcorner$]). Additionally, we give characterizations and polytime recognition algorithms for special subclasses of Split $cap$ [$llcorner$].

Asteroids in rooted and directed path graphs

An asteroidal triple is a stable set of three vertices such that each pair is connected by a path avoiding the neighborhood of the third vertex. Asteroidal triples play a central role in a classical characterization of interval graphs by Lekkerkerker and Boland. Their result says that a chordal graph is an interval graph if and only if it contains no asteroidal triple. In this paper, we prove an analogous theorem for directed path graphs which are the intersection graphs of directed paths in a directed tree. For this purpose, we introduce the notion of a strong path. Two non-adjacent vertices are linked by a strong path if either they have a common neighbor or they are the endpoints of two vertex-disjoint chordless paths satisfying certain conditions. A strong asteroidal triple is an asteroidal triple such that each pair is linked by a strong path. We prove that a chordal graph is a directed path graph if and only if it contains no strong asteroidal triple. We also introduce a related notion of asteroidal quadruple, and conjecture a characterization of rooted path graphs which are the intersection graphs of directed paths in a rooted tree.