Deutsch
 
Hilfe Datenschutzhinweis Impressum
  DetailsucheBrowse

Datensatz

DATENSATZ AKTIONENEXPORT

Freigegeben

Bericht

Quasi-orthogonal drawing of planar graphs

MPG-Autoren
/persons/resource/persons44788

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

/persons/resource/persons45092

Mutzel,  Petra
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

Externe Ressourcen
Es sind keine externen Ressourcen hinterlegt
Volltexte (beschränkter Zugriff)
Für Ihren IP-Bereich sind aktuell keine Volltexte freigegeben.
Volltexte (frei zugänglich)

MPI-I-98-1-013.pdf
(beliebiger Volltext), 167KB

Ergänzendes Material (frei zugänglich)
Es sind keine frei zugänglichen Ergänzenden Materialien verfügbar
Zitation

Klau, G. W., & Mutzel, P.(1998). Quasi-orthogonal drawing of planar graphs (MPI-I-1998-1-013). Saarbrücken: Max-Planck-Institut für Informatik.


Zitierlink: https://hdl.handle.net/11858/00-001M-0000-0014-7BCC-8
Zusammenfassung
Orthogonal drawings of graphs are highly accepted in practice. For planar graphs with vertex degree of at most four, Tamassia gives a polynomial time algorithm which computes a region preserving orthogonal grid embedding with the minimum number of bends. However, the graphs arising in practical applications rarely have bounded vertex degree. In order to cope with general planar graphs, we introduce the quasi--orthogonal drawing model. In this model, vertices are drawn on grid points, and edges follow the grid paths except around vertices of high degree. Furthermore we present an extension of Tamassia's algorithm that constructs quasi--orthogonal drawings. We compare the drawings to those obtained using related approaches.