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, Bordeaux, France , pp. 13-24 (Official URL: http://dx.doi.org/10.1007/978-3-319-03841-4_2).

Full text not available from this repository.

Abstract

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
ID Code:1357

Repository Staff Only: item control page

References

Bertolazzi, P., Di Battista, G., Liotta, G., Mannino, C.: Upward drawings of triconnected digraphs. Algorithmica 12(6), 476–497 (1994)

Bertolazzi, P., Di Battista, G., Didimo, W.: Quasi-upward planarity. Algorithmica 32(3), 474–506 (2002)

Chimani, M., Zeranski, R.: Upward planarity testing via SAT. In: Didimo, W., Patrignani, M. (eds.) GD 2012. LNCS, vol. 7704, pp. 248–259. Springer, Heidelberg (2013)

Di Battista, G., Garg, A., Liotta, G., Parise, A., Tamassia, R., Tassinari, E., Vargiu, F., Vismara, L.: Drawing directed acyclic graphs: An experimental study. Int. J. of Computational Geometry and Appl. 10(6), 623–648 (2000)

Di Battista, G., Liu, W.P., Rival, I.: Bipartite graphs, upward drawings, and planarity. Information Processing Letters 36(6), 317–322 (1990)

Di Battista, G., Tamassia, R.: On-line planarity testing. SIAM J. on Computing 25, 956–997 (1996)

Didimo, W., Giordano, F., Liotta, G.: Upward spirality and upward planarity testing. SIAM J. on Discrete Mathematics 23(4), 1842–1899 (2009)

Fulek, R., Pelsmajer, M.J., Schaefer, M., Štefankovič, D.: Hanani–Tutte, monotone drawings, and level-planarity. Thirty Essays on Geom. Graph Th., 263–287 (2013)

Garg, A., Tamassia, R.: On the computational complexity of upward and rectilinear planarity testing. SIAM J. on Computing 31(2), 601–625 (2002)

Healy, P., Lynch, K.: Fixed-parameter tractable algorithms for testing upward planarity. In: Vojtáš, P., Bieliková, M., Charron-Bost, B., Sýkora, O. (eds.) SOFSEM 2005. LNCS, vol. 3381, pp. 199–208. Springer, Heidelberg (2005)

Hutton, M.D., Lubiw, A.: Upward planar drawing of single source acyclic digraphs. In: Proc. SODA 1991, pp. 203–211 (1991)

Pach, J., Toth, G.: Monotone drawings of planar graphs. J. of Graph Theory 46(1), 39–47 (2004)

Papakostas, A.: Upward planarity testing of outerplanar dags. In: Tamassia, R., Tollis, I.G. (eds.) GD 1994. LNCS, vol. 894, pp. 298–306. Springer, Heidelberg (1995)

Welzl, E., Di Battista, G., Garg, A., Liotta, G., Tamassia, R., Tassinari, E., Vargiu, F.: An experimental comparison of four graph drawing algorithms. Computational Geometry 7, 303–325 (1997)