Item

Abstract

Drawing a graph nicely in the plane is a challenging task and mostly the appropriate problems of maximizing several aesthetic criteria are NP--complete. This thesis addresses the problem of finding an embedding for a given planar graph such that the nodes are drawn on integer grid points and the edges are following the horizontal and vertical grid lines without crossing each other. These drawings are known as {\em orthogonal grid drawings} and are highly accepted in practical applications such as automatic drawing of diagrams and VLSI--design if the number of bends in the drawing is low. We present an algorithm that extends an approach known as Tamassia's bend minimization algorithm which produces a bend--optimal drawing for a planar graph with a fixed planar representation and maximal degree of four. Therefore we introduce the concept of {\em quasi--orthogonal grid embeddings} which allow the edges to run locally between grid points in order to cope with graphs that have an arbitrarily high degree. Furthermore a new method for compacting the size of the drawing is proposed. The appendix of the thesis contains the full {\tt cweb}--documented implementation, demos can be found in {\tt /KM/usr/gdraw/DEMO/ortho}.