Upward planarity testing in practice: SAT formulations and comparative study

DOI10.1145/2699875MaRDI QIDQ2828203zbMATH OpenOpenAlexWikidataFDO

Authors Markus Chimani, Robert Zeranski

Publication date 24 October 2016

Published in ACM Journal of Experimental Algorithmics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1145/2699875

zbMATH Keywords

combinatorial algorithmsexperimental evaluationgraph drawingimplementationsSAT formulationupward planarity

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Directed graphs (digraphs), tournaments (05C20) Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20) Nonnumerical algorithms (68W05)

Recommendations

• Upward planarity testing via SAT
• Upward Planarity Testing: A Computational Study
• Upward planarity testing
• Upward Planar Drawing of Single-Source Acyclic Digraphs
• scientific article; zbMATH DE number 432821

Cites work

• Algorithms – ESA 2004
• An exact approach to upward crossing minimization
• An experimental comparison of four graph drawing algorithms.
• Bipartite graphs, upward drawings, and planarity
• Drawing directed acyclic graphs: an experimental study
• Efficient Planarity Testing
• Grid sifting, leveling and crossing reduction
• Hanani-Tutte, monotone drawings, and level-planarity
• scientific article; zbMATH DE number 432821 (Why is no real title available?)
• scientific article; zbMATH DE number 1303565 (Why is no real title available?)
• scientific article; zbMATH DE number 1979538 (Why is no real title available?)
• scientific article; zbMATH DE number 1500676 (Why is no real title available?)
• scientific article; zbMATH DE number 1830748 (Why is no real title available?)
• Layer-free upward crossing minimization
• On the computational complexity of upward and rectilinear planarity testing
• On the upward planarity of mixed plane graphs
• On-Line Planarity Testing
• Quasi-upward planarity
• SOFSEM 2005: Theory and Practice of Computer Science
• Upward and quasi-upward planarity testing of embedded mixed graphs
• Upward drawings of triconnected digraphs.
• Upward planarity testing via SAT
• Upward Planarity Testing: A Computational Study
• Upward spirality and upward planarity testing

Cited in

(9)

• The complexity of upward drawings on spheres
• Upward Planarity Testing: A Computational Study
• Upward planarity testing via SAT
• Right Angle Crossing Drawings of Graphs
• Universal slope sets for upward planar drawings
• Universal slope sets for upward planar drawings
• On the upward book thickness problem: combinatorial and complexity results
• Upward planarity testing of biconnected outerplanar DAGs solves partition
• Improving the running time of embedded upward planarity testing

This page was built for publication: Upward planarity testing in practice: SAT formulations and comparative study

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