198560
20181203023502.0
0925-7721
10.1016/j.comgeo.2014.01.003
doi
000332813800005
ISI
ARTICLE
Outerplanar graph drawings with few slopes
Amsterdam
2014
Elsevier Science Bv
2014
11
Journal Articles
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.
Outerplanar graph
Striagh-line drawing
Slope number
Knauer, Kolja
Micek, Piotr
Jagiellonian Univ, Fac Math & Comp Sci, Theoret Comp Sci Dept, Krakow, Poland
Walczak, Bartosz
Jagiellonian Univ, Fac Math & Comp Sci, Theoret Comp Sci Dept, Krakow, Poland
232136
247119
614-624
5
Computational Geometry-Theory And Applications
47
DCG
252234
U11887
oai:infoscience.tind.io:198560
article
SB
183120
EPFL-ARTICLE-198560
EPFL
PUBLISHED
REVIEWED
ARTICLE