Back to Search
Start Over
How to Draw a Series-Parallel Digraph
- Publication Year :
- 1992
- Publisher :
- Springer, 1992.
-
Abstract
- Upward and dominance drawings of acyclic digraphs find important applications in the display of hierarchical structures such as PERT diagrams, subroutine-call charts, and is-a relationships. The combinatorial model underlying such hierarchical structures is often a series-parallel digraph. In this paper the problem of constructing upward and dominance drawings of series-parallel digraphs is investigated. We show that the area requirement of upward and dominance drawings of series-parallel digraphs crucially depends on the choice of planar embedding. Also, we present efficient sequential and parallel algorithms for drawing series-parallel digraphs. Our results show that while series-parallel digraphs have a rather simple and well understood combinatorial structure, naive drawing strategies lead to drawings with exponential area, and clever algorithms are needed to achieve optimal area.
- Subjects :
- Discrete mathematics
Applied Mathematics
Structure (category theory)
Parallel algorithm
Digraph
Series and parallel circuits
Theoretical Computer Science
Exponential function
Combinatorics
Computational Mathematics
Computational Theory and Mathematics
Simple (abstract algebra)
Graph drawing
Geometry and Topology
Dominance drawing
Computer Science::Data Structures and Algorithms
MathematicsofComputing_DISCRETEMATHEMATICS
Mathematics
Subjects
Details
- Language :
- English
- Database :
- OpenAIRE
- Accession number :
- edsair.doi.dedup.....6849d5db561c42429b3f80f4eead0cb6