pith. sign in

arxiv: 1205.2548 · v2 · pith:JATHD27Vnew · submitted 2012-05-11 · 💻 cs.CG · cs.DM· math.CO

Outerplanar graph drawings with few slopes

classification 💻 cs.CG cs.DMmath.CO
keywords outerplanardeltaslopesedgegraphbounddegreedelta-1
0
0 comments X
read the original 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 $\Delta-1$ edge slopes suffice for every outerplanar graph with maximum degree $\Delta\ge 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\ge 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.

This paper has not been read by Pith yet.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.