Edge Intersection Graphs of L-Shaped Paths in Grids

Abstract

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 $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., {$└$}, {$└$,$┌$}, {$└$,$┐$}, 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., [$└$] $⊊$ [$└$,$┌$], [$└$,$┐$] $⊊$ [$└$,$┌$,$┐$] $⊊$ $B_1$-EPG; also, [$└$,$┌$] is incomparable with [$└$,$┐$]). Additionally, we give characterizations and polytime recognition algorithms for special subclasses of Split $\cap$ [$└$].

14 pages, to appear in DAM special issue for LAGOS'13

Cited by in corpus (7)

• On edge intersection graphs of paths with 2 bends
• The Complexity of Helly-$B_1$ EPG Graph Recognition
• Edge intersection hypergraphs - a new hypergraph concept
• Graphs of Edge-Intersecting and Non-Splitting One Bend Paths in a Grid
• Graphs of Edge-Intersecting Non-Splitting Paths in a Tree: Representations of Holes-Part II
• Nearly all cacti are edge intersection hypergraphs of 3-uniform hypergraphs
• Cycles as edge intersection hypergraphs