Upward Planarity Testing: A Computational Study

Chimani, Markus and Zeranski, Robert (2013) Upward Planarity Testing: A Computational Study. In: 21st International Symposium, GD 2013, September 23-25, 2013 , pp. 13-24(Official URL: http://dx.doi.org/10.1007/978-3-319-03841-4_2).

Full text not available from this repository.


A directed acyclic graph (DAG) is upward planar if it can be drawn without any crossings while all edges—when following them in their direction—are drawn with strictly monotonously increasing y-coordinates. Testing whether a graph allows such a drawing is known to be NP-complete, but there is a substantial collection of different algorithmic approaches known in literature. In this paper, we give an overview of the known algorithms, ranging from combinatorial FPT and branch-and-bound algorithms to ILP and SAT formulations. Most approaches of the first class have only been considered from the theoretical point of view, but have never been implemented. For the first time, we give an extensive experimental comparison between virtually all known approaches to the problem. Furthermore, we present a new SAT formulation based on a recent theoretical result by Fulek et al. [8], which turns out to perform best among all known algorithms.

Item Type: Conference Paper
Classifications: G Algorithms and Complexity > G.770 Planarity Testing
P Styles > P.840 Upward
URI: http://gdea.informatik.uni-koeln.de/id/eprint/1357

Actions (login required)

View Item View Item