Edge intersection graphs of L-shaped paths in grids

DOI10.1016/J.DAM.2015.01.039zbMATH Open1339.05381arXiv1204.5702OpenAlexW2152052626MaRDI QIDQ299080FDOQ299080

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)

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

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

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

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)

Cites Work

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

Cited In (18)

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