Edge intersection graphs of LL-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: ⌞,⌜,⌟,⌝⌞,⌜,⌟,⌝, and we consider zero bend paths (i.e., ∣∣ and–) to be degenerate ⌞⌞’s. These graphs, called B1B1-EPG graphs, were first introduced by Golumbic et al. (2009). We consider the natural subclasses of B1B1-EPG formed by the subsets of the four single bend shapes (i.e., {⌞},{⌞,⌜},{⌞,⌝}{⌞},{⌞,⌜},{⌞,⌝}, and {⌞,⌜,⌝}{⌞,⌜,⌝}) and we denote the classes by [⌞],[⌞,⌜],[⌞,⌝][⌞],[⌞,⌜],[⌞,⌝], and [⌞,⌜,⌝][⌞,⌜,⌝] 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., [⌞]⊊[⌞,⌜],[⌞,⌝]⊊[⌞,⌜,⌝]⊊B1[⌞]⊊[⌞,⌜],[⌞,⌝]⊊[⌞,⌜,⌝]⊊B1-EPG and [⌞,⌜][⌞,⌜] is incomparable with [⌞,⌝][⌞,⌝]). Additionally, we give characterizations and polytime recognition algorithms for special subclasses of Split     ∩[⌞].