Edge intersection graphs of L-shaped paths in grids

DOI10.1016/J.DAM.2015.01.039MaRDI QIDQ299080zbMATH OpenOpenAlexFDO

Authors Kathie Cameron, Steven Chaplick, Chính T. Hoàng

Publication date 22 June 2016

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1204.5702

zbMATH Keywords

NP-completenesssplit graphs\(L\)-graphsedge intersection graphsgrid pathsrecognition algorithms

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

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: $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$].

Recommendations

• Hardness and approximation for L-EPG and \(B_1\)-EPG graphs
• Graphs of edge-intersecting and non-splitting one bend paths in a grid
• Edge intersection graphs of single bend paths on a grid
• scientific article; zbMATH DE number 7272507
• On edge intersection graphs of paths with 2 bends

Cites work

• Approximation algorithms for \(B _{1}\)-EPG graphs
• Edge intersection graphs of single bend paths on a grid
• Edge-intersection graphs of grid paths: the bend-number
• Reducibility among combinatorial problems
• Some properties of edge intersection graphs of single-bend paths on a grid
• Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms
• The edge intersection graphs of paths in a tree

Cited in

(18)

• Hardness and approximation for L-EPG and \(B_1\)-EPG graphs
• On edge intersection graphs of paths with 2 bends
• Longest (s, t)-paths in L-shaped grid graphs
• On \(k\)-bend and monotonic \(\ell\)-bend edge intersection graphs of paths on a grid
• Intersection graphs of L-shapes and segments in the plane
• Intersection graphs of L-shapes and segments in the plane
• Edge-intersection graphs of boundary-generated paths in a grid
• Recognizing geometric intersection graphs stabbed by a line
• scientific article; zbMATH DE number 7272507 (Why is no real title available?)
• Vertex intersection graphs of paths on a grid: characterization within block graphs
• Edge-intersection graphs of grid paths: the bend-number
• On independent set in \(B_1\)-EPG graphs
• On edge intersection graphs of paths with 2 bends
• Graphs of edge-intersecting and non-splitting one bend paths in a grid
• The complexity of Helly-\(B_1\) EPG graph recognition
• On split \(B_1\)-EPG graphs
• Vertex Intersection Graphs of Paths on a Grid
• Monotonic Representations of Outerplanar Graphs as Edge Intersection Graphs of Paths on a Grid

This page was built for publication: Edge intersection graphs of \(L\)-shaped paths in grids

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q299080)