Upward planarity testing

DOI10.1007/BF01108622zbMath0836.68081WikidataQ55966842 ScholiaQ55966842MaRDI QIDQ1904391

Ashim Garg, Roberto Tamassia

Publication date: 11 April 1996

Published in: Order (Search for Journal in Brave)

zbMATH Keywords

NP-completenessdigraphsplanar drawingupward planarity testing

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Planar graphs; geometric and topological aspects of graph theory (05C10) Parallel algorithms in computer science (68W10) Ordered sets (06A99)

Related Items

Monotone Drawings of Graphs with Fixed Embedding ⋮ Upward Planarity Testing of Embedded Mixed Graphs ⋮ A graphical calculus for semi-groupal categories ⋮ Parameterized complexity of graph planarity with restricted cyclic orders ⋮ DRAWING DIRECTED ACYCLIC GRAPHS: AN EXPERIMENTAL STUDY ⋮ Maximum upward planar subgraphs of embedded planar digraphs ⋮ Unnamed Item ⋮ The partial visibility representation extension problem ⋮ Parameterized complexity of graph planarity with restricted cyclic orders ⋮ Upward planar graphs and their duals ⋮ Combinatorial characterization of upward planarity ⋮ Advances in the theory and practice of graph drawing ⋮ TWO FIXED-PARAMETER TRACTABLE ALGORITHMS FOR TESTING UPWARD PLANARITY ⋮ Monotone drawings of graphs with fixed embedding

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Bipartite graphs, upward drawings, and planarity
• Upward drawings of triconnected digraphs.
• Fundamentals of planar ordered sets
• Algorithms for plane representations of acyclic digraphs
• Area requirement and symmetry display of planar upward drawings
• Planar lattices and planar graphs
• Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms
• Algorithms for drawing graphs: An annotated bibliography
• Planar acyclic oriented graphs
• On the Computational Complexity of Upward and Rectilinear Planarity Testing
• A Depth-First-Search Characterization of Planarity
• Efficient Planarity Testing
• Planar Lattices
• HOW TO DRAW A SERIES-PARALLEL DIGRAPH
• Optimal Upward Planarity Testing of Single-Source Digraphs
• Dividing a Graph into Triconnected Components
• Partial orders of dimension 2