Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
414729 | Computational Geometry | 2014 | 11 Pages |
Abstract
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Δ−1 edge slopes suffice for every outerplanar graph with maximum degree Δ⩾4Δ⩾4. This improves on the previous bound of O(Δ5)O(Δ5), which was shown for planar partial 3-trees, a superclass of outerplanar graphs. The bound is tight: for every Δ⩾4Δ⩾4 there is an outerplanar graph with maximum degree Δ that requires at least Δ−1Δ−1 distinct edge slopes in an outerplanar straight-line drawing.
Keywords
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Kolja Knauer, Piotr Micek, Bartosz Walczak,