Minimum segment drawings of series-parallel graphs with the maximum degree three

Abstract

This thesis deals with minimum segment drawings of planar graphs. A minimum segment drawing of a planar graph G is a planar straight line drawing of G that has the minimum number of line segments among all possible planar straight line drawings of G. Computation of minimum segment drawings has recently drawn much attention among the graph drawing community. The problem is not only important for visualization applications, but has also given rise to a number of interesting theoretical problems. Unfortunately, very few significant results regarding this problem are known to date. For example, although there is an algorithm for computing minimum segment drawings of trees, no such algorithm is known for biconnected and triconnected planar graphs. The problem has also been studied for plane graphs. Although most graph drawing problems are known to be easy for plane graphs, the minimum segment drawing problem does not exhibit this trait. Even for degree-restricted cases of plane graphs, e.g., for plane triconnected cubic graphs, it has not been possible yet to give an algorithm for computing minimum segment drawings. Series-parallel graphs are well-known planar graphs that often arise in various problems involving scheduling, electrical networks, dataflow analysis, and database logic programs. In this thesis, we study the minimum segment drawing problem for biconnected series-parallel graphs with the maximum degree three. For such a graph G, we give a linear-time algorithm for choosing a suitable embedding of G that admits a minimum segment drawing, and a linear-time algorithm for computing a minimum segment drawing of G.