On the bend-number of planar and outerplanar graphs
From MaRDI portal
Publication:477341
DOI10.1007/978-3-642-29344-3_39zbMATH Open1303.05038arXiv1112.3353OpenAlexW1992898832MaRDI QIDQ477341FDOQ477341
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)
Abstract: The bend-number b(G) of a graph G is the minimum k such that G may be represented as the edge intersection graph of a set of grid paths with at most k bends. We confirm a conjecture of Biedl and Stern showing that the maximum bend-number of outerplanar graphs is 2. Moreover we improve the formerly known lower and upper bound for the maximum bend-number of planar graphs from 2 and 5 to 3 and 4, respectively.
Full work available at URL: https://arxiv.org/abs/1112.3353
Recommendations
- On the bend-number of planar and outerplanar graphs
- On Betti numbers of a class of bipartite planar graphs
- A generalization of outerplanar graphs
- On the bend number of circular-arc graphs as edge intersection graphs of paths on a grid
- On the bend number of circular-arc graphs as edge intersection graphs of paths on a grid
- Outerplanar crossing numbers of planar graphs
- On the number of vertices of positively curved planar graphs
- Bounds on the bend number of split and cocomparability graphs
- On the bondage number of planar and directed graphs
- scientific article; zbMATH DE number 4008413
Planar graphs; geometric and topological aspects of graph theory (05C10) Graph representations (geometric and intersection representations, etc.) (05C62)
Cites Work
- Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms
- A partial k-arboretum of graphs with bounded treewidth
- Representing edge intersection graphs of paths on degree 4 trees
- Edge-intersection graphs of grid paths: the bend-number
- Planar graphs as VPG-graphs
- Edge intersection graphs of single bend paths on a grid
- Title not available (Why is that?)
- Edge intersection graphs of systems of paths on a grid with a bounded number of bends
- Approximation Algorithms for B 1-EPG Graphs
- Some properties of edge intersection graphs of single-bend paths on a grid
- On the bend-number of planar and outerplanar graphs
- On Triangle Contact Graphs
- Rectangular duals of planar graphs
- On Diagrams Representing Maps
- Star arboricity
- Title not available (Why is that?)
- Star arboricity of graphs
- On star and caterpillar arboricity
- Partitioning graphs of bounded tree-width
- Caterpillar arboricity of planar graphs
- On double and multiple interval graphs
- Some results on linear arboricity
- Title not available (Why is that?)
- Extremal Values of the Interval Number of a Graph
- Title not available (Why is that?)
- The interval number of a planar graph: Three intervals suffice
- Three ways to cover a graph
- On two dual classes of planar graphs
Cited In (19)
- On the number of vertices of positively curved planar graphs
- CPG graphs: some structural and hardness results
- Edge-intersection graphs of boundary-generated paths in a grid
- Proper circular arc graphs as intersection graphs of paths on a grid
- On contact graphs of paths on a grid
- On \(k\)-bend and monotonic \(\ell\)-bend edge intersection graphs of paths on a grid
- Title not available (Why is that?)
- Monotonic Representations of Outerplanar Graphs as Edge Intersection Graphs of Paths on a Grid
- On edge intersection graphs of paths with 2 bends
- Characterizations of cographs as intersection graphs of paths on a grid
- On the Total Number of Bends for Planar Octilinear Drawings
- VPG and EPG bend-numbers of Halin graphs
- On the bend-number of planar and outerplanar graphs
- On independent set in \(B_1\)-EPG graphs
- On the bend number of circular-arc graphs as edge intersection graphs of paths on a grid
- Edge-intersection graphs of grid paths: the bend-number
- Three ways to cover a graph
- Hardness and approximation for L-EPG and \(B_1\)-EPG graphs
- Characterising circular-arc contact \(B_0\)-VPG graphs
This page was built for publication: On the bend-number of planar and outerplanar graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q477341)
