2004 | OriginalPaper | Chapter
Drawing Series-Parallel Graphs on Restricted Integer 3D Grids
Author : Emilio Di Giacomo
Published in: Graph Drawing
Publisher: Springer Berlin Heidelberg
Included in: Professional Book Archive
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
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.