On the bend-number of planar and outerplanar graphs

DOI10.1007/978-3-642-29344-3_39zbMath1303.05038arXiv1112.3353OpenAlexW1992898832MaRDI QIDQ477341

Daniel Heldt, Torsten Ueckerdt, Kolja Knauer

Publication date: 3 December 2014

Published in: Discrete Applied Mathematics, LATIN 2012: Theoretical Informatics (Search for Journal in Brave)

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

zbMATH Keywords

planar graphouterplanar graphbend-numberEPG-representation

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Graph representations (geometric and intersection representations, etc.) (05C62)

Related Items (17)

On edge intersection graphs of paths with 2 bends ⋮ Monotonic Representations of Outerplanar Graphs as Edge Intersection Graphs of Paths on a Grid ⋮ CPG graphs: some structural and hardness results ⋮ VPG and EPG bend-numbers of Halin graphs ⋮ On independent set in \(B_1\)-EPG graphs ⋮ Hardness and approximation for L-EPG and \(B_1\)-EPG graphs ⋮ Proper circular arc graphs as intersection graphs of paths on a grid ⋮ Characterising circular-arc contact \(B_0\)-VPG graphs ⋮ Edge-intersection graphs of boundary-generated paths in a grid ⋮ Three ways to cover a graph ⋮ On \(k\)-bend and monotonic \(\ell\)-bend edge intersection graphs of paths on a grid ⋮ Edge-intersection graphs of grid paths: the bend-number ⋮ Unnamed Item ⋮ On contact graphs of paths on a grid ⋮ On the bend-number of planar and outerplanar graphs ⋮ On the bend number of circular-arc graphs as edge intersection graphs of paths on a grid ⋮ Characterizations of cographs as intersection graphs of paths on a grid

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• On the bend-number of planar and outerplanar graphs
• Some properties of edge intersection graphs of single-bend paths on a grid
• The interval number of a planar graph: Three intervals suffice
• Three ways to cover a graph
• On two dual classes of planar graphs
• Edge intersection graphs of systems of paths on a grid with a bounded number of bends
• On star and caterpillar arboricity
• Star arboricity
• Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms
• A partial k-arboretum of graphs with bounded treewidth
• Partitioning graphs of bounded tree-width
• Star arboricity of graphs
• Caterpillar arboricity of planar graphs
• Edge-intersection graphs of grid paths: the bend-number
• Representing edge intersection graphs of paths on degree 4 trees
• Approximation Algorithms for B 1-EPG Graphs
• Planar Graphs as VPG-Graphs
• Edge intersection graphs of single bend paths on a grid
• On double and multiple interval graphs
• Rectangular duals of planar graphs
• Some results on linear arboricity
• Extremal Values of the Interval Number of a Graph
• On Triangle Contact Graphs
• On Diagrams Representing Maps

This page was built for publication: On the bend-number of planar and outerplanar graphs