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

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

doi:10.1007/3-540-37623-2_15

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

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

School of Computer Science

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

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 language	English
Title of host publication	Graph Drawing: 6th International Symposium, GD’ 98 Montréal, Canada, August 13–15, 1998 Proceedings
Editors	S. H. Whitesides
Publisher	Springer
Pages	198-209
Number of pages	12
ISBN (Print)	978-3-540-65473-5
DOIs	https://doi.org/10.1007/3-540-37623-2_15
Publication status	Published - 1998
Event	6th International Symposium on Graph Drawing (GD '98) - Montreal, Canada Duration: 13 Aug 1998 → 15 Aug 1998

Publication series

Name	Lecture Notes in Computer Science
Volume	1547
ISSN (Print)	0302-9743

Conference

Conference	6th International Symposium on Graph Drawing (GD '98)
Country/Territory	Canada
City	Montreal
Period	13/08/98 → 15/08/98

Keywords

GRAPHS

Access to Document

10.1007/3-540-37623-2_15

Cite this

Hong, S. H., Eades, P., Quigley, A., & Lee, S. H. (1998). Drawing algorithms for series-parallel digraphs in two and three dimensions. In S. H. Whitesides (Ed.), Graph Drawing: 6th International Symposium, GD’ 98 Montréal, Canada, August 13–15, 1998 Proceedings (pp. 198-209). (Lecture Notes in Computer Science; Vol. 1547). Springer. https://doi.org/10.1007/3-540-37623-2_15

@inproceedings{0fe7c88fa33a4c85915d940a67f02d7f,

title = "Drawing algorithms for series-parallel digraphs in two and three dimensions",

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.",

keywords = "GRAPHS",

author = "Hong, {S H} and P Eades and A Quigley and Lee, {S H}",

year = "1998",

doi = "10.1007/3-540-37623-2_15",

language = "English",

isbn = "978-3-540-65473-5",

series = "Lecture Notes in Computer Science",

publisher = "Springer",

pages = "198--209",

editor = "Whitesides, {S. H.}",

booktitle = "Graph Drawing: 6th International Symposium, GD{\textquoteright} 98 Montr{\'e}al, Canada, August 13–15, 1998 Proceedings",

address = "Netherlands",

note = "6th International Symposium on Graph Drawing (GD '98) ; Conference date: 13-08-1998 Through 15-08-1998",

}

Hong, SH, Eades, P, Quigley, A & Lee, SH 1998, Drawing algorithms for series-parallel digraphs in two and three dimensions. in SH Whitesides (ed.), Graph Drawing: 6th International Symposium, GD’ 98 Montréal, Canada, August 13–15, 1998 Proceedings. Lecture Notes in Computer Science, vol. 1547, Springer, pp. 198-209, 6th International Symposium on Graph Drawing (GD '98) , Montreal, Canada, 13/08/98. https://doi.org/10.1007/3-540-37623-2_15

Drawing algorithms for series-parallel digraphs in two and three dimensions. / Hong, S H ; Eades, P ; Quigley, A et al.
Graph Drawing: 6th International Symposium, GD’ 98 Montréal, Canada, August 13–15, 1998 Proceedings. ed. / S. H. Whitesides. Springer, 1998. p. 198-209 (Lecture Notes in Computer Science; Vol. 1547).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

TY - GEN

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

AU - Hong, S H

AU - Eades, P

AU - Quigley, A

AU - Lee, S H

PY - 1998

Y1 - 1998

N2 - 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.

AB - 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.

KW - GRAPHS

U2 - 10.1007/3-540-37623-2_15

DO - 10.1007/3-540-37623-2_15

M3 - Conference contribution

SN - 978-3-540-65473-5

T3 - Lecture Notes in Computer Science

SP - 198

EP - 209

BT - Graph Drawing: 6th International Symposium, GD’ 98 Montréal, Canada, August 13–15, 1998 Proceedings

A2 - Whitesides, S. H.

PB - Springer

T2 - 6th International Symposium on Graph Drawing (GD '98)

Y2 - 13 August 1998 through 15 August 1998

ER -

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

Abstract

Publication series

Conference

Keywords

Access to Document

Fingerprint

Cite this