On the bend-number of planar and outerplanar graphs - LIRMM - Laboratoire d’Informatique, de Robotique et de Microélectronique de Montpellier
Article Dans Une Revue Discrete Applied Mathematics Année : 2014

On the bend-number of planar and outerplanar graphs

Résumé

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
Origine Fichiers produits par l'(les) auteur(s)
Loading...

Dates et versions

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

Identifiants

Citer

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⟩
208 Consultations
65 Téléchargements

Altmetric

Partager

More