Drawing algorithms for series-parallel digraphs in two and three dimensions

S H Hong, P Eades, A Quigley, S H Lee

Research output: Chapter in Book/Report/Conference proceedingConference contribution

21 Citations (Scopus)

Abstract

Series parallel digraphs are one of the most common types of graphs: they appear in flow diagrams, dependency charts, and in PERT networks. Algorithms for drawing series parallel digraphs have appeared in [2,3].

In this paper we describe algorithms which can draw series parallel digraphs in two and three dimensions. Sample drawings are in Figure 1. Specific variations of the algorithms can be used to obtain symmetric drawings, or drawings in which the "footprint" (that is, the projection in the xy plane) is minimized.

This extended abstract is organized as follows. In the next section, we summarize the necessary background for series parallel digraphs. Then concepts for symmetric drawings, especially with respect to series parallel digraphs, are presented in Section 3. The two dimensional algorithm, is given in Section 4; building on the two dimensional algorithm, the three dimensional algorithm is given in Section 5.

Original languageEnglish
Title of host publicationGraph Drawing: 6th International Symposium, GD’ 98 Montréal, Canada, August 13–15, 1998 Proceedings
EditorsS. H. Whitesides
PublisherSpringer
Pages198-209
Number of pages12
ISBN (Print)978-3-540-65473-5
DOIs
Publication statusPublished - 1998
Event6th International Symposium on Graph Drawing (GD '98) - Montreal, Canada
Duration: 13 Aug 199815 Aug 1998

Publication series

NameLecture Notes in Computer Science
Volume1547
ISSN (Print)0302-9743

Conference

Conference6th International Symposium on Graph Drawing (GD '98)
Country/TerritoryCanada
CityMontreal
Period13/08/9815/08/98

Keywords

  • GRAPHS

Fingerprint

Dive into the research topics of 'Drawing algorithms for series-parallel digraphs in two and three dimensions'. Together they form a unique fingerprint.

Cite this