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 , pp. 238-246(Official URL: http://dx.doi.org/10.1007/978-3-540-24595-7_22).

Full text not available from this repository.


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
URI: http://gdea.informatik.uni-koeln.de/id/eprint/453

Actions (login required)

View Item View Item