Abstract:
This thesis deals with straight-line drawings of planar graphs with some constraints. Usually
various constraints are imposed on the drawings of planar graphs to meet the requirements of
the application areas like VLSI layout, road networks, software engineering, etc. Constraints
are also adapted to increase the readability of the drawings of graphs.
In some applications in VLSI design it is required to draw a graph such that the vertices
are drawn on a given set of lines. A set of lines that supports drawings of all graphs of n
vertices in some class is called universal for that class. We show that ⌊n+3
2 ⌋ parallel lines are
universal for drawing planar 3-trees of n vertices and such a drawing can be found in linear
time. We also introduce a new data structure to represent a plane 3-tree which we call a “face
representative tree.”
We next study the problem of finding a monotone drawing of a planar graph where at
least a monotone path exists between every pair of vertices in the drawing of the graph. In
this research we first show that every series-parallel graph of n vertices admits a straightline
monotone grid drawing on an O(n) × O(n2) grid and such a drawing can be computed
in linear time. We later give a linear-time algorithm to find a straight-line monotone grid
drawing of a planar graph on an O(n) × O(n2) grid. Our results solve two open problems
on monotone drawings posed by Angelini et al.
While dealing with monotone drawings of planar graphs, we discover a special spanning
tree of a plane graph which we call a “good spanning tree.” We show that every connected
planar graph has an embedding that contains a good spanning tree. We also give linear-time
algorithms for finding 2-visibility representations and spike-V PG representations of planar
graphs using good spanning trees. Finally, we solve the Hamiltonian cycle problem for
series-parallel graphs and show some applications of this class of graphs in graph drawings.
