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

DOI10.1007/978-3-642-34611-8_28MaRDI QIDQ5200514zbMATH OpenOpenAlexFDO

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)

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

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)

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.

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

Cited in

(18)

• Computing maximum independent set on outerstring graphs and their relatives
• 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
• Space-efficient algorithms for reachability in directed geometric graphs
• B0-VPG Representation of AT-free Outerplanar 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

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)