MPI-INF/SWS Research Reports 1991-2021

2. Number - All Departments


Quasi-orthogonal drawing of planar graphs

Klau, Gunnar W. and Mutzel, Petra

May 1998, 15 pages.

Status: available - back from printing

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.

  • Attachement: (303 KBytes)

URL to this document:

Hide details for BibTeXBibTeX
  AUTHOR = {Klau, Gunnar W. and Mutzel, Petra},
  TITLE = {Quasi-orthogonal drawing of planar graphs},
  TYPE = {Research Report},
  INSTITUTION = {Max-Planck-Institut f{\"u}r Informatik},
  ADDRESS = {Im Stadtwald, D-66123 Saarbr{\"u}cken, Germany},
  NUMBER = {MPI-I-98-1-013},
  MONTH = {May},
  YEAR = {1998},
  ISSN = {0946-011X},