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

DOI10.1007/978-3-642-34611-8_28zbMath1341.05203arXiv1206.5159OpenAlexW1918340579MaRDI QIDQ5200514

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

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) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph representations (geometric and intersection representations, etc.) (05C62)

Related Items (15)

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

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