Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
418688 | Discrete Applied Mathematics | 2014 | 11 Pages |
Abstract
The bend-number b(G)b(G) of a graph GG is the minimum kk such that GG may be represented as the edge intersection graph of a set of grid paths with at most kk 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 bounds for the maximum bend-number of planar graphs from 2 and 5 to 3 and 4, respectively.
Keywords
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Daniel Heldt, Kolja Knauer, Torsten Ueckerdt,