On the bend-number of planar and outerplanar graphs
From MaRDI portal
Publication:477341
DOI10.1016/j.dam.2014.07.015zbMath1303.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
Planar graphs; geometric and topological aspects of graph theory (05C10) Graph representations (geometric and intersection representations, etc.) (05C62)
Related Items
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
