Height-Preserving Transformations of Planar Graph Drawings - Graph Drawing - page 380

The research of this paper was driven by the following question: Does one
really need to develop algorithms and lower bounds for these four drawing styles
separately? Or is it possible to take a drawing in one style, and convert it directly
to another style, preserving some of the features along the way? This would
significantly simplify the development of algorithms and lower bounds.
This paper studies the existence of such transformations under the objective
of maintaining the height of the drawing. It also includes some discussion on
the width, and shows that transformations that maintain the height sometimes
require an exponential blow-up in the width. Due to some prior work and ap-
plications, two variations of the drawing styles are included. First, a drawing is
called y-monotone if each edge is drawn as a y -monotone curve. Every straight-
line drawing and every visibility representation is y -monotone, but orthogonal
drawings and poly-line drawings need not be. Second, a drawing is called flat
if every vertex is represented by a horizontal line segment. Every straight-line
drawing and every poly-line drawing is automatically flat, but orthogonal draw-
ings and visibility representations need not be. Fig. 1 lists the results, which can
be summarized as follows:
- Straight-line drawings, y -monotone poly-line drawings, flat visibility repre-
sentations and flat y -monotone orthogonal drawings are equivalent, where
“equivalent” means “can be transformed into each other such that the height
of the drawings remains the same”.
- Poly-line drawings and orthogonal drawings are also equivalent.
- y -monotone orthogonal drawings are strictly between orthogonal drawings
and visibility representations.
- Visibility representations are between orthogonal y -monotone drawings and
straight-line drawings, where the latter relationship may be an equality.
The transformations keep the width linearly bounded or better, with the notable
exception of creating straight-line drawings: here we show that an exponential
increase in width is required for some graphs if the height must stay the same.
These results have some applications given in Section 6. Most importantly,
they allow to derive some height-bounds for which no direct proof appears
known, and they can be used to formulate some NP-hard graph drawing prob-
lems as integer programs.
2 Preliminaries
Throughout this paper G denotes a planar graph, and ʓ denotes a planar draw-
ing of G that represents vertices of G as axis-aligned boxes (possibly degenerated
into horizontal segments or points) and edges of G as polygonal curves (possibly
straight line segments). The common end of two line segments in a polygonal
curve is called a bend . ʓ is called y-monotone if for all edges the y -coordinates
monotonically increase while going from one end to the other; horizontal seg-
ments are allowed. ʓ is called flat if all vertices are horizontal segments.
Call a drawing a grid-drawing if all corners of vertex-boxes and all endpoints
of segments of polygonal curves have integer coordinates. A grid drawing is said