2011/12/14 by Heldt, Daniel, Knauer, Kolja, Ueckerdt, Torsten
#05C62 #Combinatorics (math.CO) #Discrete Mathematics (cs.DM) #F.2.2 #FOS: Computer and information sciences #FOS: Mathematics #G.2.1
paper · doi:10.48550/arxiv.1112.3353
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.