Skip to main content
Top

2004 | OriginalPaper | Chapter

Drawing Series-Parallel Graphs on Restricted Integer 3D Grids

Author : Emilio Di Giacomo

Published in: Graph Drawing

Publisher: Springer Berlin Heidelberg

Activate our intelligent search to find suitable subject content or patents.

search-config
loading …

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.

Metadata
Title
Drawing Series-Parallel Graphs on Restricted Integer 3D Grids
Author
Emilio Di Giacomo
Copyright Year
2004
Publisher
Springer Berlin Heidelberg
DOI
https://doi.org/10.1007/978-3-540-24595-7_22

Premium Partner