Straightening out planar poly-line drawings

Abstract. This paper addresses the following question: Given a planar poly-line drawing of a graph, can we “straighten it out”, i.e., convert it to a planar straight-line drawing, while keeping some features unchanged? 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 re-quired 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