An Improved Upward Planarity Testing Algorithm and Related Applications

DOI10.1007/978-3-642-00202-1_29MaRDI QIDQ3605509zbMATH OpenOpenAlexFDO

Authors Sarmad Abbasi, Patrick Healy, Aimal Rextin

Publication date 24 February 2009

Published in WALCOM: Algorithms and Computation (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-642-00202-1_29

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Directed graphs (digraphs), tournaments (05C20) Graph theory (including graph drawing) in computer science (68R10) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

Recommendations

• Improving the running time of embedded upward planarity testing
• Optimal Upward Planarity Testing of Single-Source Digraphs
• Upward Planar Drawing of Single-Source Acyclic Digraphs
• Graph Drawing
• Upward spirality and upward planarity testing

Cites work

• Algorithms – ESA 2004
• Algorithms for plane representations of acyclic digraphs
• Fundamentals of planar ordered sets
• scientific article; zbMATH DE number 2123123 (Why is no real title available?)
• scientific article; zbMATH DE number 3887060 (Why is no real title available?)
• scientific article; zbMATH DE number 1368469 (Why is no real title available?)
• On the computational complexity of upward and rectilinear planarity testing
• Optimal Upward Planarity Testing of Single-Source Digraphs
• Quasi-upward planarity
• SOFSEM 2005: Theory and Practice of Computer Science
• Upward drawings of triconnected digraphs.
• Upward Planar Drawing of Single-Source Acyclic Digraphs

Cited in

(6)

• Quasi-upward planarity
• On the computational complexity of upward and rectilinear planarity testing
• Upward Planarity Testing: A Computational Study
• A Fully Dynamic Algorithm to Test the Upward Planarity of Single-Source Embedded Digraphs
• Graph Drawing
• Improving the running time of embedded upward planarity testing

Describes a project that uses

Uses Software

• LEDA

This page was built for publication: An Improved Upward Planarity Testing Algorithm and Related Applications

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