Logo image
Sign in
On the bend-number of planar and outerplanar graphs
Journal article   Open access   Peer reviewed

On the bend-number of planar and outerplanar graphs

Daniel Heldt, Kolja Knauer and Torsten Ueckerdt
Discrete Applied Mathematics, Vol.179, pp.109-119
12/2014

Abstract

EPG-representation Planar graph Outerplanar graph Bend-number
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.
url
Find in HALView

Metrics

1 Record Views

Details

Logo image