Help Privacy Policy Disclaimer
  Advanced SearchBrowse





Quasi-orthogonal drawing of planar graphs


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


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

External Resource
No external resources are shared
Fulltext (restricted access)
There are currently no full texts shared for your IP range.
Fulltext (public)

(Any fulltext), 167KB

Supplementary Material (public)
There is no public supplementary material available

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.

Cite as: https://hdl.handle.net/11858/00-001M-0000-0014-7BCC-8
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.