On the bend-number of planar and outerplanar graphs - LIRMM - Laboratoire d’Informatique, de Robotique et de Microélectronique de Montpellier
Journal Articles Discrete Applied Mathematics Year : 2014

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.
Fichier principal
Vignette du fichier
1112.3353.pdf (231.96 Ko) Télécharger le fichier
Origin Files produced by the author(s)
Loading...

Dates and versions

lirmm-01414962 , version 1 (20-12-2019)

Identifiers

Cite

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

Altmetric

Share

More