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.
