English
 
Help Privacy Policy Disclaimer
  Advanced SearchBrowse

Item

ITEM ACTIONSEXPORT
Add to Basket
 Local TagsRelease HistoryDetailsSummary
  Quasi-orthogonales Zeichnen planarer Graphen mit wenigen Knicken

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

Item is

 

show all hide all

Basic

show hide
Item Permalink: https://hdl.handle.net/11858/00-001M-0000-000F-397C-B Version Permalink: https://hdl.handle.net/11858/00-001M-0000-0024-A7E3-6
Genre: Thesis

Files

show Files
hide Files
:
diplom.ps.gz (Any fulltext), 475KB
 
File Permalink:
-
Name:
diplom.ps.gz
Description:
-
OA-Status:
Visibility:
Private
MIME-Type / Checksum:
application/gzip
Technical Metadata:
Copyright Date:
-
Copyright Info:
-
License:
-

Locators

show

Creators

show
hide
 Creators:
Klau, Gunnar W.1, Author           
Affiliations:
1Algorithms and Complexity, MPI for Informatics, Max Planck Society, ou_24019              

Content

show
hide
Free keywords: -
 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}.

Details

show
hide
Language(s): deu - German
 Dates: 2010-03-0219971997
 Publication Status: Issued
 Pages: -
 Publishing info: Saarbrücken : Universität des Saarlandes
 Table of Contents: -
 Rev. Type: -
 Identifiers: eDoc: 517742
Other: Local-ID: C1256428004B93B8-4B54EBD9F73645DEC12565B7005E795F-Klau97a
 Degree: Master

Event

show

Legal Case

show

Project information

show

Source

show