Outerplanar graph drawings with few slopes

We consider straight-line outerplanar drawings of outerplanar graphs in which a small number of distinct edge slopes are used, that is, the segments representing edges are parallel to a small number of directions. We prove that Delta - 1 edge slopes suffice for every outerplanar graph with maximum degree Delta >= 4. This improves on the previous bound of O(Delta(5)), which was shown for planar partial 3-trees, a superclass of outerplanar graphs. The bound is tight: for every Delta >= 4 there is an outerplanar graph with maximum degree Delta that requires at least Delta - 1 distinct edge slopes in an outerplanar straight-line drawing. (C) 2014 Elsevier B.V. All rights reserved.


Published in:
Computational Geometry-Theory And Applications, 47, 5, 614-624
Year:
2014
Publisher:
Amsterdam, Elsevier Science Bv
ISSN:
0925-7721
Keywords:
Laboratories:




 Record created 2014-05-02, last modified 2018-03-17


Rate this document:

Rate this document:
1
2
3
 
(Not yet reviewed)