Bend-Bounded Path Intersection Graphs: Sausages, Noodles, and Waffles on a Grill

DOI10.1007/978-3-642-34611-8_28zbMATH Open1341.05203arXiv1206.5159OpenAlexW1918340579MaRDI QIDQ5200514FDOQ5200514

Authors: Steven Chaplick, Vít Jelínek, Jan Kratochvíl, Tomáš Vyskočil 

Publication date: 6 November 2012

Published in: Graph-Theoretic Concepts in Computer Science (Search for Journal in Brave)

Abstract: In this paper we study properties of intersection graphs of k-bend paths in the rectangular grid. A k-bend path is a path with at most k 90 degree turns. The class of graphs representable by intersections of k-bend paths is denoted by B_k-VPG. We show here that for every fixed k, B_k-VPG is a proper subset of B_{k+1}-VPG and that recognition of graphs from B_k-VPG is NP-complete even when the input graph is given by a B_{k+1}-VPG representation. We also show that the class B_k-VPG (for k>0) is in no inclusion relation with the class of intersection graphs of straight line segments in the plane.

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

Recommendations

• On edge-intersection graphs of \(k\)-bend paths in grids
• Edge-Intersection Graphs of k-Bend Paths in Grids
• Edge-intersection graphs of grid paths: the bend-number
• Edge intersection graphs of systems of paths on a grid with a bounded number of bends
• Graphs of edge-intersecting and non-splitting one bend paths in a grid
• On \(k\)-bend and monotonic \(\ell\)-bend edge intersection graphs of paths on a grid
• On edge intersection graphs of paths with 2 bends
• On edge intersection graphs of paths with 2 bends
• Edge intersection graphs of single bend paths on a grid
• Some properties of edge intersection graphs of single bend paths on a grid

zbMATH Keywords

intersection graphs of straight line segments in the plane

Mathematics Subject Classification ID

Paths and cycles (05C38) Graph representations (geometric and intersection representations, etc.) (05C62) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Cited In (18)

• Bounds on the bend number of split and cocomparability graphs
• Finding geometric representations of apex graphs is NP-hard
• CPG graphs: some structural and hardness results
• String graphs of \(k\)-bend paths on a grid
• Intersection graphs of L-shapes and segments in the plane
• Posets and VPG graphs
• On edge intersection graphs of paths with 2 bends
• On edge intersection graphs of paths with 2 bends
• Characterization and a 2D Visualization of B$$_{0}$$-VPG Cocomparability Graphs
• Maximum independent set on \(B_1\)-VPG graphs
• B0-VPG Representation of AT-free Outerplanar Graphs
• Space-efficient algorithms for reachability in directed geometric graphs
• On some special classes of contact \(B_0\)-VPG graphs
• Finding geometric representations of apex graphs is \textsf{NP}-hard
• \(B_0\)-VPG representation of AT-free outerplanar graphs
• Characterising circular-arc contact \(B_0\)-VPG graphs
• Characterization of \(\mathrm{B}_0\)-VPG cocomparability graphs and a 2D visualization of their posets
• Computing maximum independent set on outerstring graphs and their relatives

This page was built for publication: Bend-Bounded Path Intersection Graphs: Sausages, Noodles, and Waffles on a Grill

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