Drawing Series-Parallel Graphs on Restricted Integer 3D Grids

Di Giacomo, Emilio (2004) Drawing Series-Parallel Graphs on Restricted Integer 3D Grids. In: Graph Drawing 11th International Symposium, GD 2003, September 21-24, 2003, Perugia, Italy , pp. 238-246 (Official URL: http://dx.doi.org/10.1007/978-3-540-24595-7_22).

Full text not available from this repository.

Abstract

A k-track drawing is a crossing-free 3D straight-line grid drawing of a graph G on a set of k parallel lines called tracks. The minimum value of k for which G admits a k-track drawing is called the track number of G. In the existing literature a lower bound of five and an upper bound of fifteen are known for the track number of series-parallel graph. In this paper we reduce this gap for a large subclass of series-parallel graph for which the lower bound remains five but we show an upper bound of eight. We also describe a linear time drawing algorithm that computes a 3D straight-line grid drawing of these graphs in volume 4 × 4 × 2n.

Item Type:Conference Paper
Additional Information:10.1007/978-3-540-24595-7_22
Classifications:Z Theory > Z.250 Geometry
P Styles > P.900 Visibility
P Styles > P.060 3D
ID Code:453

Repository Staff Only: item control page

References

F. R. K. Chung, F. T. Leighton, and A. Rosenberg. Embedding graphs in books: A layout problem with applications to VLSI design. SIAM J on Alg. and Disc. Methods, 8:33-58, 1987.

G. Di Battista, P. Eades, R. Tamassia, and I. G. Tollis. Graph Drawing. Prentice Hall, Upper Saddle River, NJ, 1999.

G. Di Battista, R. Tamassia. On-line maintenance of triconnected components with SPQR-trees. Algorithmica, 15(4):302-318, 1996.

E. Di Giacomo, G. Liotta, and H. Meijer. 3D Straight-line drawings of k-trees. Submitted for publication.

E. Di Giacomo, G. Liotta, and S. K. Wismath. Drawing series-parallel graphs on a box. In Proc. CCCG 2002, 2002.

V. Dujmovic, P. Morin, and D. Wood. Pathwidth and three-dimensional straight line grid drawings of graphs. In Proc. GD 2002, volume 2528 of LNCS, pages 42-53. Springer-Verlag, 2002.

V. Dujmovic and D. R. Wood. Tree-partitions of k-trees with application in graph layout. In Proc. WG 2003, LNCS. Springer-Verlag, to appear.

S. Felsner, G. Liotta, and S.K. Wismath. Straight line drawings on restricted integer grids in two and three dimensions. In Proc. GD 2001), volume 2265 of LNCS, pages 328-342. Springer-Verlag, 2001.

D. R. Wood. Queue layouts, tree-width, and three-dimensional graph drawing. In Proc. FSTTCS '02, volume 2556 of LNCS, pages 348-359. Springer-Verlag, 2002.