Rectilinear-upward planarity testing of digraphs

DOI10.1016/J.JCSS.2026.103775MaRDI QIDQ6845954zbMATH OpenFDO

Authors Walter Didimo, Michael Kaufmann, Giuseppe Liotta, Giacomo Ortali, Maurizio Patrignani

Publication date 12 March 2026

Published in Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/J.JCSS.2026.103775

zbMATH Keywords

graph drawingorthogonal drawingsparameterized complexityrectilinear planarityupward drawingsupward planarity

Mathematics Subject Classification ID

Computer science (68-XX)

Cites work

• A linear-time algorithm for testing the truth of certain quantified Boolean formulas
• Accelerated bend minimization
• Algorithms for plane representations of acyclic digraphs
• Canonical Inference for Implicational Systems
• Computing an st-numbering
• Computing bend-minimum orthogonal drawings of plane series-parallel graphs in linear time
• Dividing a Graph into Triconnected Components
• Efficient Planarity Testing
• Graph Drawing
• Graph drawing software
• scientific article; zbMATH DE number 2123122 (Why is no real title available?)
• scientific article; zbMATH DE number 2123123 (Why is no real title available?)
• scientific article; zbMATH DE number 2080088 (Why is no real title available?)
• HV-planarity: algorithms and complexity
• Improving the running time of embedded upward planarity testing
• No-bend orthogonal drawings and no-bend orthogonally convex drawings of planar graphs (extended abstract)
• On Embedding a Graph in the Grid with the Minimum Number of Bends
• On the Complexity of Timetable and Multicommodity Flow Problems
• On the computational complexity of upward and rectilinear planarity testing
• On the parameterized complexity of bend-minimum orthogonal planarity
• On-Line Planarity Testing
• Optimal Orthogonal Drawings of Planar 3-Graphs in Linear Time
• Optimal Upward Planarity Testing of Single-Source Digraphs
• Orthogonal Drawings of Plane Graphs Without Bends
• Orthogonal planarity testing of bounded treewidth graphs
• Parameterized algorithms for upward planarity
• Planar rectilinear drawings of outerplanar graphs in linear time
• Rectilinear Graphs and Their Embeddings
• Rectilinear planarity of partial 2-trees
• Rectilinear Planarity of Partial 2-Trees
• Sketched representations and orthogonal planarity of bounded treewidth graphs
• Spirality and Optimal Orthogonal Drawings
• Testing upward planarity of partial 2-trees
• TWO FIXED-PARAMETER TRACTABLE ALGORITHMS FOR TESTING UPWARD PLANARITY
• Upward and orthogonal planarity are W[1]-hard parameterized by treewidth
• Upward and quasi-upward planarity testing of embedded mixed graphs
• Upward drawings of triconnected digraphs.
• Upward Planar Drawing of Single-Source Acyclic Digraphs
• Upward spirality and upward planarity testing

This page was built for publication: Rectilinear-upward planarity testing of digraphs

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