TWO FIXED-PARAMETER TRACTABLE ALGORITHMS FOR TESTING UPWARD PLANARITY

DOI10.1142/S0129054106004285zbMath1103.68095MaRDI QIDQ5493896

Karol Lynch, Patrick Healy

Publication date: 16 October 2006

Published in: International Journal of Foundations of Computer Science (Search for Journal in Brave)

zbMATH Keywords

graph drawingparameterized complexityupward planaritySPQR-trees

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (11)

Upward Planar Drawings with Three and More Slopes ⋮ Upward planar drawings with three and more slopes ⋮ Quasi-upward planar drawings with minimum curve complexity ⋮ Upward planar drawings with two slopes ⋮ Parameterized analysis and crossing minimization problems ⋮ Testing upward planarity of partial 2-trees ⋮ Grid recognition: classical and parameterized computational perspectives ⋮ Sketched representations and orthogonal planarity of bounded treewidth graphs ⋮ Upward and quasi-upward planarity testing of embedded mixed graphs ⋮ Maximum upward planar subgraphs of embedded planar digraphs ⋮ Orthogonal planarity testing of bounded treewidth graphs

Cites Work

• Unnamed Item
• Fundamentals of planar ordered sets
• Algorithms for plane representations of acyclic digraphs
• Quasi-upward planarity
• Upward planarity testing
• On-line maintenance of triconnected components with SPQR-trees
• On the Computational Complexity of Upward and Rectilinear Planarity Testing
• Optimal Upward Planarity Testing of Single-Source Digraphs
• On-Line Planarity Testing
• Upward Planar Drawing of Single-Source Acyclic Digraphs

This page was built for publication: TWO FIXED-PARAMETER TRACTABLE ALGORITHMS FOR TESTING UPWARD PLANARITY