Point - set embeddings of planar graphs with fewer bends

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.