Abstract:
An upward point-set embedding of an upward planar digraph G on a set of
points S with a mapping © : V (G) → S is a drawing ¡ of G where each vertex
of G is placed on a point of S according to ©, each edge is drawn upward and
no two edges cross each other. In this thesis we give an algorithm for finding an
upward point-set embedding of an upward planar digraph G with a mapping
if it exists. Our algorithm finds a drawing with at most n − 3 bends per edge
whereas the best known previous algorithm finds a drawing with at most 2n−3
bends. Furthermore we also find an upper bound on total number of bends for
an upward point-set embedding.
An orthogonal point-set embedding of a planar graph G on a set S of points
in Euclidean plane is a drawing of G where each vertex of G is placed on
a point of S, each edge is drawn as a sequence of alternate horizontal and
vertical line segments and any two edges do not cross except at their common
end. Orthogonal point-set embeddings have practical applications in circuit
schematics on pre-fabricated printed circuit boards (PCBs), where position of
components on the PCB is prescribed and standard cell technology employed
during the VLSI layout design process. In both the cases, it is always desirable
to minimize the number of bends, points at which the edge changes its direction
in the drawing. Because bends increase the manufacturing cost in PCB board
and VLSI chip. In this thesis we devise an algorithm for orthogonal point-set
embedding of 3-connected cubic planar graphs having a hamiltonian cycle with
at most ³5n
2 + 2´ bends. We also give an algorithm for finding an orthogonal
point-set embedding of 4-connected planar graphs (¢ ≤ 4) with at most 6n
bends. To the best of our knowledge this is the first work on orthogonal pointset
embedding with fewer bends.
