Home | Issues | About JGAA | Instructions for Authors |
Advances in Graph Drawing. Special Issue on Selected Papers from
the Ninth International Symposium on Graph Drawing, GD 2001
DOI: 10.7155/jgaa.00073
Polar Coordinate Drawing of Planar Graphs with Good Angular Resolution
Vol. 7, no. 4, pp. 311-333, 2003. Regular paper.
Abstract We present a novel way to draw planar graphs with
good angular resolution. We introduce the polar coordinate
representation and describe a family of algorithms for constructing
it.
The main advantage of the polar representation is
that it allows independent control over grid size and bend
positions.
We first describe a standard (Cartesian) representation algorithm, CRA,
which we then modify to obtain a polar representation algorithm, PRA.
In both algorithms we are concerned with the following drawing
criteria: angular resolution, bends per edge, vertex resolution,
bend-point resolution, edge separation, and drawing area.
The CRA algorithm achieves 1 bend per edge, unit vertex
and bend resolution, √2/2 edge separation, 5n×[(5n)/2] drawing area and [1/(2d(v))] angular
resolution, where d(v) is the degree of vertex v.
The PRA algorithm has an improved angular resolution of [(π)/(4d(v))], 1 bend per edge,
and unit vertex resolution. For the PRA algorithm, the
bend-point resolution and edge separation are parameters that can be
modified to achieve different types of drawings and drawing areas. In
particular, for the same parameters as the CRA algorithm (unit
bend-point resolution and √2/2 edge separation), the PRA
algorithm creates a drawing of size 9n ×[(9n)/2].
|
Journal Supporters
|