Skip to Main content Skip to Navigation
Journal articles

On the bend-number of planar and outerplanar graphs

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.
Document type :
Journal articles
Complete list of metadatas

Cited literature [19 references]  Display  Hide  Download

https://hal-lirmm.ccsd.cnrs.fr/lirmm-01414962
Contributor : Daniel Goncalves <>
Submitted on : Friday, December 20, 2019 - 12:54:31 PM
Last modification on : Monday, May 11, 2020 - 10:58:09 AM
Document(s) archivé(s) le : Saturday, March 21, 2020 - 4:51:24 PM

File

1112.3353.pdf
Files produced by the author(s)

Identifiers

Collections

Citation

Daniel Heldt, Kolja Knauer, Torsten Ueckerdt. On the bend-number of planar and outerplanar graphs. Discrete Applied Mathematics, Elsevier, 2014, 179, pp.109-119. ⟨10.1016/j.dam.2014.07.015⟩. ⟨lirmm-01414962⟩

Share

Metrics

Record views

264

Files downloads

98