Anzeige
Erschienen in:
1988 | ReviewPaper | Buchkapitel
Upward drawings of acyclic digraphs
verfasst von : Giuseppe Di Battista, Roberto Tamassia
Erschienen in: Graph-Theoretic Concepts in Computer Science
Verlag: Springer Berlin Heidelberg
Enthalten in: Professional Book Archive
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
The problem of representing acyclic digraphs in the plane is considered. We present algorithms that construct planar drawings of acyclic digraphs such that all edges are straight-line segments flowing in the same direction, e.g., from the left to the right or from the bottom to the top. The time complexity for constructing such upward drawings is O (n log n), where n is the number of vertices of the digraph. For covering digraphs of lattices (Hasse diagrams), the complexity is reduced to O(n). We also show that the planar digraphs that admit an upward drawing are exactly the subgraphs of planar st-graphs.