Upward Planarity Testing via SAT

Chimani, Markus and Zeranski, Robert (2013) Upward Planarity Testing via SAT. In: 20th International Symposium, GD 2012, September 19-21, 2012 , pp. 248-259(Official URL: http://link.springer.com/chapter/10.1007/978-3-642...).

Full text not available from this repository.


A directed acyclic graph is upward planar if it allows a drawing without edge crossings where all edges are drawn as curves with monotonously increasing y-coordinates. The problem to decide whether a graph is upward planar or not is NP-complete in general, and while special graph classes are polynomial time solvable, there is not much known about solving the problem for general graphs in practice. The only attempt so far was a branch-and-bound algorithm over the graph’s triconnectivity structure which was able to solve sparse graphs. In this paper, we propose a fundamentally different approach, based on the seemingly novel concept of ordered embeddings. We carefully model the problem as a special SAT instance, i.e., a logic formula for which we check satisfiability. Solving these SAT instances allows us to decide upward planarity for arbitrary graphs. We then show experimentally that this approach seems to dominate the known alternative approaches and is able to solve traditionally used graph drawing benchmarks effectively.

Item Type: Conference Paper
Additional Information: 10.1007/978-3-642-36763-2_22
Classifications: G Algorithms and Complexity > G.770 Planarity Testing
P Styles > P.840 Upward
URI: http://gdea.informatik.uni-koeln.de/id/eprint/1314

Actions (login required)

View Item View Item