Algorithms for plane representations of acyclic digraphs

DOI10.1016/0304-3975(88)90123-5zbMath0678.68059OpenAlexW2002906478WikidataQ56227817 ScholiaQ56227817MaRDI QIDQ1124349

Giuseppe Di Battista, Roberto Tamassia

Publication date: 1988

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0304-3975(88)90123-5

zbMATH Keywords

embedding drawing planar graph Acyclic digraphs st-graphs

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Planar graphs; geometric and topological aspects of graph theory (05C10) Directed graphs (digraphs), tournaments (05C20)

Related Items

Upward Planar Drawings with Three and More Slopes, Rooted Uniform Monotone Minimum Spanning Trees, Monotone Drawings of 3-Connected Plane Graphs, How to draw a series-parallel digraph, Spirality of orthogonal representations and optimal drawings of series-parallel graphs and 3-planar graphs (extended abstract), Upward Straight-Line Embeddings of Directed Graphs into Point Sets, Upward planar drawings with three and more slopes, Upward planarity testing, Nearly optimal monotone drawing of trees, Compact Monotone Drawing of Trees, Upward planar drawings with two slopes, Upward planar drawings on the standing and the rolling cylinders, Special graph representation and visualization of semantic networks, On the Page Number of Upward Planar Directed Acyclic Graphs, Bitonic $st$-orderings for upward planar graphs: splits and bends in the variable embedding scenario, A Sublinear Bound on the Page Number of Upward Planar Graphs, Upward book embeddability of $st$-graphs: complexity and algorithms, Planar Confluent Orthogonal Drawings of 4-Modal Digraphs, Good acyclic orientations of 4‐regular 4‐connected graphs, Fully Dynamic Transitive Closure in plane dags with one source and one sink, A graphical calculus for semi-groupal categories, Recognizing DAGs with page-number 2 is NP-complete, Planar confluent orthogonal drawings of 4-modal digraphs, $st$-orientations with few transitive edges, Good spanning trees in graph drawing, $st$-Orientations with Few Transitive Edges, Bitonic st-orderings for Upward Planar Graphs, Parameterized approaches to orthogonal compaction, Straight-line rectangular drawings of clustered graphs, ON MINIMUM AREA PLANAR UPWARD DRAWINGS OF DIRECTED TREES AND OTHER FAMILIES OF DIRECTED ACYCLIC GRAPHS, Dynamic maintenance of planar digraphs, with applications, Bipartite graphs, upward drawings, and planarity, Unnamed Item, Planar L-Drawings of Directed Graphs, Drawing subcubic 1-planar graphs with few bends, few slopes, and large angles, Computing Upward Topological Book Embeddings of Upward Planar Digraphs, Representations of graphs and networks (coding, layouts and embeddings), Drawing Subcubic 1-Planar Graphs with Few Bends, Few Slopes, and Large Angles, Order, genus, and diagram invariance, Upward point set embeddings of paths and trees, Constrained visibility representations of graphs, Extending upward planar graph drawings, Area requirement and symmetry display of planar upward drawings, Maximum upward planar subgraphs of embedded planar digraphs, Directed rectangle-visibility graphs have unbounded dimension, Unnamed Item, Monotone drawings of graphs with few directions, On the number of upward planar orientations of maximal planar graphs, Strip planarity testing for embedded planar graphs, Some results on visibility graphs, Upward drawings of triconnected digraphs., Computing upward topological book embeddings of upward planar digraphs, Simultaneous Embeddings with Few Bends and Crossings, A note on optimal area algorithms for upward drawings of binary trees, Colored simultaneous geometric embeddings and universal pointsets, Universal slope sets for upward planar drawings, Upward planar morphs, Improving the running time of embedded upward planarity testing, Crossing-Optimal Acyclic Hamiltonian Path Completion and Its Application to Upward Topological Book Embeddings, An Improved Upward Planarity Testing Algorithm and Related Applications, The partial visibility representation extension problem, Convexity-increasing morphs of planar graphs, Upward planar morphs, Universal slope sets for upward planar drawings, Embeddability Problems for Upward Planar Digraphs, Recognizing DAGs with page-number 2 is NP-complete, Upward planar graphs and their duals, Confluent Hasse Diagrams, On the upward book thickness problem: combinatorial and complexity results, On the upward embedding on the torus, On the upward book thickness problem: combinatorial and complexity results, Upward Book Embeddings of st-Graphs, Combinatorial characterization of upward planarity, On 3D visibility representations of graphs with few crossings per edge, Baxter posets, Advances in the theory and practice of graph drawing, Upward straight-line embeddings of directed graphs into point sets, TWO FIXED-PARAMETER TRACTABLE ALGORITHMS FOR TESTING UPWARD PLANARITY, Multilevel Planarity, Right Angle Crossing Drawings of Graphs, Bipolar orientations revisited, Characterization of $\mathrm{B}_0$-VPG cocomparability graphs and a 2D visualization of their posets, Crossing-Optimal Acyclic HP-Completion for Outerplanar st-Digraphs, Characterization and a 2D Visualization of B$$_{0}$$-VPG Cocomparability Graphs, Straight-line monotone grid drawings of series–parallel graphs, Every triangle-free planar graph has a planar upward drawing, Towards area requirements for drawing hierarchically planar graphs

Cites Work