Polar Coordinate Drawing of Planar Graphs with Good Angular Resolution

Duncan, Christian A. and Kobourov, Stephen G. (2002) Polar Coordinate Drawing of Planar Graphs with Good Angular Resolution. In: Graph Drawing 9th International Symposium, GD 2001, September 23-26, 2001, Vienna, Austria , pp. 407-421 (Official URL: http://dx.doi.org/10.1007/3-540-45848-4_32).

Full text not available from this repository.

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 which use polar representation. The main advantage of using a polar representation is that it allows us to exert independent control over grid size and bend positions. Polar coordinates allow us to specify different vertex resolution, bend-point resolution and edge separation. 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, $\sqrt{2}/2$ edge separation, $5n \times \frac{5n}{2}$ drawing area and $\frac{1}{2d(v)}$ angular resolution, where $d(v)$ is the degree of vertex $v$. The PRA algorithm has an improved angular resolution of $\frac{\pi}{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 $\sqrt{2}/2$ edge separation), the PRA algorithm creates a drawing of size $9n \times \frac{9n}{2}$.

Item Type:Conference Paper
Additional Information:10.1007/3-540-45848-4_32
Classifications:Z Theory > Z.500 Representations
G Algorithms and Complexity > G.999 Others
M Methods > M.600 Planar
ID Code:498

Repository Staff Only: item control page

References

C. C. Cheng, C. A. Duncan, M. T. Goodrich, and S. G. Kobourov. Drawing planar graphs with circular arcs. Discrete and Computational Geometry, 25:405-418, 2001.

M. Chrobak and T. Payne. A linear-time algorithm for drawing planar graphs. Inform. Process. Lett., 54:241-246, 1995.

H. de Fraysseix, J. Pach, and R. Pollack. How to draw a planar graph on a grid. Combinatorica, 10:41-51, 1990.

G. Di Battista, P. Eades, R. Tamassia, and I. G. Tollis. Graph Drawing: Algorithms for the Visualization of Graphs. Prentice-Hall, New Jersey, 1999.

A. Garg and R. Tamassia. Planar drawings and angular resolution: Algorithms and bounds. In J. van Leeuwen, editor, Algorithms (Proc. ESA '94), volume 855 of LNCS, pages 12-23. Springer-Verlag, 1994.

M.T. Goodrich and C.G. Wagner. A framework for drawing planar graphs with curves and polylines. In Proc. Graph Drawing: 6th International Symp. (GD '98), volume 1547 of Lecture Notes in Comput. Sci., pages 153-166. Springer, 1998.

C. Gutwenger and P. Mutzel. planar polyline drawings with good angular resolution. In Proc. Graph Drawing: 6th International Symp. (GD '98), volume 1547 of Lecture Notes in Comput. Sci., pages 167-182. Springer, 1998.

Goos Kant. Drawing planar graphs using the canonical ordering. Algorithmica, 16:4-32, 1996. (Special issue on Graph Drawing, edited by G. Di Battista and R. Tamassia).

S. Malitz and A. Papakostas. On the angular resolution of planar graphs. SIAM J. Discr. Math., 7:172-183, 1994.