de.mpg.escidoc.pubman.appbase.FacesBean
English
 
Help Guide Disclaimer Contact us Login
  Advanced SearchBrowse

Item

ITEM ACTIONSEXPORT

Released

Thesis

Quasi-orthogonales Zeichnen planarer Graphen mit wenigen Knicken

MPS-Authors
http://pubman.mpdl.mpg.de/cone/persons/resource/persons44788

Klau,  Gunnar W.
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

Locator
There are no locators available
Fulltext (public)
There are no public fulltexts available
Supplementary Material (public)
There is no public supplementary material available
Citation

Klau, G. W. (1997). Quasi-orthogonales Zeichnen planarer Graphen mit wenigen Knicken. Master Thesis, Universität des Saarlandes, Saarbrücken.


Cite as: http://hdl.handle.net/11858/00-001M-0000-000F-397C-B
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}.