Straightening out planar poly-line drawings
classification
💻 cs.CG
cs.DMcs.DS
keywords
heightpoly-linedrawingsincreasemaintainingmonotonerequiredsome
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.