Symmetric Drawings of Series Parallel Digraphs in Two Dimensions

Seok-Hee Hong, Peter Eades and Sang-Ho Lee, Drawing Series Parallel Digraphs Symmetrically, Computational Geometry: Theory and Applications, Vol. 17, Issue 3-4, pp. 165-188, 2000.

In this paper we present algorithms for drawing series parallel digraphs with as much symmetry as possible. The first step is to compute a certain kind of automorphism, called an "upward planar automorphism" for an input series parallel digraph. The next step uses these automorphisms to construct a symmetric drawing of the graph. We present several variations of the second step, with visibility drawings, "bus-orthogonal" drawings, and polyline drawings. All algorithms run in linear time.

Seok-Hee Hong, Peter Eades, Aaron Quigley and Sang-Ho Lee, Drawing Algorithms for Series-Parallel Digraphs in Two and Three Dimensions, Proceedings of the 6th Symp. on Graph Drawing '98, Lecture Notes in Computer Science, Springer, Montreal, Canada, 1998.

In this paper we have introduced two algorithms for drawing series parallel digraphs. One constructs two dimensional drawings which display symmetries, the other constructs three dimensional drawings with a footprint of minimum size.

For viewing large drawings, pls click the drawings.