pith. sign in

arxiv: 1404.5892 · v2 · pith:UCRTZHLPnew · submitted 2014-04-23 · 💻 cs.CG · cs.DM· cs.DS

Straightening out planar poly-line drawings

classification 💻 cs.CG cs.DMcs.DS
keywords heightpoly-linedrawingsincreasemaintainingmonotonerequiredsome
0
0 comments X
read the original abstract

We show that any $y$-monotone poly-line drawing can be straightened out while maintaining $y$-coordinates and height. The width may increase much, but we also show that on some graphs exponential width is required if we do not want to increase the height. Likewise $y$-monotonicity is required: there are poly-line drawings (not $y$-monotone) that cannot be straightened out while maintaining the height. We give some applications of our result.

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.