2014/04/23 by Therese Biedl, Biedl, Therese
Computer Science · #Computational Geometry (cs.CG) #Data Structures and Algorithms (cs.DS) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #cs.CG #cs.DM #cs.DS
paper · pdf · doi:10.48550/arxiv.1404.5892
The main result turns out to be known (Pach & Toth, J. Graph Theory 2004, http://onlinelibrary.wiley.com/doi/10.1002/jgt.10168/pdf )
arxiv created 2014/04/24 · arxiv updated 2014/04/25
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.