Max-Planck-Institut für Informatik
max planck institut
informatik
mpii logo Minerva of the Max Planck Society
 

MPI-INF D1 Publications :: Thesis :: Klau, Gunnar W.


MPI-INF D1 Publications
Show all entries of:this year (2019)last year (2018)two years ago (2017)Open in Notes
Action:login to update

Thesis - Master's thesis | @MastersThesis | Masterarbeit


Author
Author(s)*:Klau, Gunnar W.
BibTeX citekey*:Klau97a
Language:German

Title, School
Title*:Quasi-orthogonales Zeichnen planarer Graphen mit wenigen Knicken
School:Universität des Saarlandes
Type of Thesis*:Master's thesis
Month:January
Year:1997


Note, Abstract, Copyright
LaTeX 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}.

Keywords:graph drawing, orthogonal, bend

Referees, Status, Dates
1. Referee:Prof. Dr. Kurt Mehlhorn
2. Referee:Prof. Dr. Michael Kaufmann
Supervisor:Dr. Petra Mutzel
Status:Completed
Date Kolloquium:20 November 2019

Correlation
MPG Unit:Max-Planck-Institut für Informatik
MPG Subunit:Algorithms and Complexity Group
Audience:experts only
Appearance:MPII WWW Server, MPII FTP Server, MPG publications list, university publications list, working group publication list, Fachbeirat


BibTeX Entry:
@MASTERSTHESIS{Klau97a,
AUTHOR = {Klau, Gunnar W.},
TITLE = {Quasi-orthogonales Zeichnen planarer Graphen mit wenigen Knicken},
SCHOOL = {Universit{\"a}t des Saarlandes},
YEAR = {1997},
TYPE = {Master's thesis}
MONTH = {January},
}



Entry last modified by Gunnar Klau, 03/02/2010
Hide details for Edit History (please click the blue arrow to see the details)Edit History (please click the blue arrow to see the details)

Editor(s)
Gunnar Klau
Created
02/26/1998 06:11:54 PM
Revisions
3.
2.
1.
0.
Editor(s)
Gunnar Klau
Uwe Brahm
Gunnar Klau
Gunnar Klau
Edit Dates
30/03/98 15:22:55
02/26/98 08:04:10 PM
26/02/98 19:03:13
26/02/98 18:11:55