Minimum segment drawings of outerplanar graphs

Abstract

In a straight line drawing of a planar graph each vertex is drawn as a point and each edge is drawn as a straight line segment. One of the important aesthetic criteria for a straight line drawing is to minimize the number of maximal straight line segments required for the straight line drawing. Finding a minimum segment drawing of a planar graph is analogous to aligning maximum number of objects according to their relations. Hence the problem of obtaining a minimum segment drawing of a given graph has important practical applications in the fields like Optical Fiber Communication, bend minimization in VLSI Layout Planning, aesthetics in Architectural Floorplanning, antenna placement in Sensor Networks, etc. The problem of finding minimum segment drawings has been studied for different classes of planar graphs which include trees, outerplanar graphs, 2-trees and planar 3-trees. Researchers were able to give bounds on the number of segments required for straight line drawing of the classes of graphs mentioned above. Recently, Samee et al. gave an algorithm to find minimum segment drawings of a restricted class of series-parallel graphs with the maximum degree three. Other than that no algorithm has been devised so far for finding minimum segment drawings of non trivial classes of planar graphs. Outerplanar graphs are an important subclass of planar graphs where every vertex of the graph appears on the outerface. Dujmovic et al. posed an open problem of finding a polynomial time algorithm to compute an outerplanar drawing of a given outerplanar graph with the minimum number of segments. Motivated by this open problem, in this thesis we give a lineartime algorithm for finding a minimum segment drawing of a dual-path outerplane graph. We also give an algorithm for finding a minimum segment drawing of a subdivision of a dual-path outerplanc graph.