2012/05/31 by Kolja Knauer, Piotr Micek, Bartosz Walczak · 1 citation
Computer Science · Mathematics · #cs.CG #cs.DM #math.CO #msc:05C62 #msc:68R10
paper · pdf · doi:10.1016/j.comgeo.2014.01.003
published as Comput.Geom. 47 (2014) 614-624 · Major revision of the whole paper
arxiv created 2014/04/10 · arxiv updated 2014/04/11
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 Δ-1 edge slopes suffice for every outerplanar graph with maximum degree Δ≥ 4. This improves on the previous bound of O(Δ5), which was shown for planar partial 3-trees, a superclass of outerplanar graphs. The bound is tight: for every Δ≥ 4 there is an outerplanar graph with maximum degree Δ that requires at least Δ-1 distinct edge slopes in an outerplanar straight-line drawing.