Upward Planar Drawing of Single-Source Acyclic Digraphs

DOI10.1137/S0097539792235906MaRDI QIDQ4877519zbMATH OpenWikidataFDO

Authors Michael D. Hutton, Anna Lubiw

Publication date 18 August 1996

Published in SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1137/S0097539792235906

zbMATH Keywords

directed acyclic graphupward plane drawing

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Combinatorics in computer science (68R05) Graph theory (including graph drawing) in computer science (68R10) Parallel algorithms in computer science (68W10)

Recommendations

• scientific article; zbMATH DE number 431511
• scientific article; zbMATH DE number 432821
• scientific article; zbMATH DE number 4062623
• 1-bend upward planar drawings of SP-digraphs
• Path-monotonic upward drawings of graphs
• Bipartite graphs, upward drawings, and planarity
• Computing maximum upward planar subgraphs of single-source embedded digraphs
• Maximum upward planar subgraph of a single-source embedded digraph

Cited in

(40)

• Volume requirements of 3D upward drawings
• Algorithms for plane representations of acyclic digraphs
• Every triangle-free planar graph has a planar upward drawing
• Predicting nearly as well as the best pruning of a planar decision graph.
• An SPQR-tree-like embedding representation for upward planarity
• On the number of upward planar orientations of maximal planar graphs
• Baxter posets
• Computing maximum upward planar subgraphs of single-source embedded digraphs
• Upward and quasi-upward planarity testing of embedded mixed graphs
• On the sphericity testing of single source digraphs
• Upward three-dimensional grid drawings of graphs
• Upward planar graphs and their duals
• Upward planarity testing in practice: SAT formulations and comparative study
• Bitonic st-orderings for upward planar graphs
• scientific article; zbMATH DE number 431511 (Why is no real title available?)
• scientific article; zbMATH DE number 432821 (Why is no real title available?)
• ON MINIMUM AREA PLANAR UPWARD DRAWINGS OF DIRECTED TREES AND OTHER FAMILIES OF DIRECTED ACYCLIC GRAPHS
• Maximum upward planar subgraph of a single-source embedded digraph
• An Improved Upward Planarity Testing Algorithm and Related Applications
• A Fully Dynamic Algorithm to Test the Upward Planarity of Single-Source Embedded Digraphs
• scientific article; zbMATH DE number 4062623 (Why is no real title available?)
• scientific article; zbMATH DE number 68923 (Why is no real title available?)
• Upward planarity testing via SAT
• Strip planarity testing for embedded planar graphs
• Upward Planar Drawings and Switch-regularity Heuristics
• Building Blocks of Upward Planar Digraphs
• TWO FIXED-PARAMETER TRACTABLE ALGORITHMS FOR TESTING UPWARD PLANARITY
• Multilevel planarity
• Confluent Hasse Diagrams
• scientific article; zbMATH DE number 7765366 (Why is no real title available?)
• Testing upward planarity of partial 2-trees
• On upward-planar L-drawings of graphs
• Upward and orthogonal planarity are W[1]-hard parameterized by treewidth
• Rectilinear-upward planarity testing of digraphs
• Rectilinear-upward planarity testing of digraphs
• Dynamic embeddings of dynamic single-source upward planar graphs
• Upward and rectilinear planarity are W[1]-hard parameterized by treewidth
• Maximum upward planar subgraphs of embedded planar digraphs
• Upward drawings of triconnected digraphs.
• Improving the running time of embedded upward planarity testing

This page was built for publication: Upward Planar Drawing of Single-Source Acyclic Digraphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4877519)