On the bend-number of planar and outerplanar graphs

Daniel Heldt 1 Kolja Knauer 2 Torsten Ueckerdt 3
2 ALGCO - Algorithmes, Graphes et Combinatoire
LIRMM - Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier
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.
Type de document :
Article dans une revue
Discrete Applied Mathematics, Elsevier, 2014, 179, pp.109-119. 〈10.1016/j.dam.2014.07.015〉
Liste complète des métadonnées

https://hal-lirmm.ccsd.cnrs.fr/lirmm-01414962
Contributeur : Daniel Goncalves <>
Soumis le : lundi 12 décembre 2016 - 16:54:20
Dernière modification le : jeudi 24 mai 2018 - 15:59:22

Lien texte intégral

Identifiants

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〉

Partager

Métriques

Consultations de la notice

95