Straight-line drawings of planar graphs with constraints

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.