Improving the running time of embedded upward planarity testing

DOI10.1016/j.ipl.2010.02.004zbMath1209.68609OpenAlexW2057903654MaRDI QIDQ991781

Aimal Rextin, Patrick Healy, Sarmad Abbasi

Publication date: 7 September 2010

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ipl.2010.02.004

zbMATH Keywords

algorithmsgraph drawingupward planarity

Mathematics Subject Classification ID

Nonnumerical algorithms (68W05) Graph theory (including graph drawing) in computer science (68R10)

Related Items

Computing maximum upward planar subgraphs of single-source embedded digraphs ⋮ Bitonic st-orderings for Upward Planar Graphs ⋮ Strip planarity testing for embedded planar graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Upward drawings of triconnected digraphs.
• Fundamentals of planar ordered sets
• Algorithms for plane representations of acyclic digraphs
• Quasi-upward planarity
• On the Computational Complexity of Upward and Rectilinear Planarity Testing
• Optimal Upward Planarity Testing of Single-Source Digraphs
• Upward Planar Drawing of Single-Source Acyclic Digraphs
• Algorithms – ESA 2004
• SOFSEM 2005: Theory and Practice of Computer Science