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$].
تحميل البحث