Maximum Upward Planar Subgraphs of Embedded Planar Digraphs

Binucci, Carla and Didimo, Walter and Giordano, Francesco (2008) Maximum Upward Planar Subgraphs of Embedded Planar Digraphs. In: Graph Drawing 15th International Symposium, GD 2007, September 24-26, 2007, Sydney, Australia , pp. 195-206 (Official URL: http://dx.doi.org/10.1007/978-3-540-77537-9_20).

Full text not available from this repository.

Abstract

This paper presents an extensive study on the problem of computing maximum upward planar subgraphs of embedded planar digraphs: Complexity results, algorithms, and experiments are presented. Namely: $(i)$ We prove that the addressed problem is NP-Hard; $(ii)$ A fast heuristic and an exponential-time exact algorithm are described; $(iii)$ A wide experimental analysis is performed to show the effectiveness of our techniques.

Item Type:Conference Paper
Additional Information:10.1007/978-3-540-77537-9_20
Classifications:P Styles > P.840 Upward
ID Code:838

Repository Staff Only: item control page

References

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

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

P. Bertolazzi, G. Di Battista, C. Mannino, and R. Tamassia. Optimal upward planarity testing of single-source diagraphs. SIAM J. Comput., 27:132-169, 1998.

H. Chan. A parameterized algorithm for upward planarity testing. In Proc. ESA '04, volume 3221 of LNCS, pages 157-168, 2004.

G. Di Battista, P. Eades, R. Tamassia, and I. G. Tollis. Graph Drawing. Prentice Hall, Upper Saddle River, NJ, 1999.

G. Di Battista, A. Garg, G. Liotta, R. Tamassia, E. Tassinari, and F. Vargiu. An experimental comparison of four graph drawing algorithms. Computational Geometry: Theory and Applications, 7:303-326, 1997.

W. Didimo. Upward planar drawings and switch-regularity heuristics. Journal of Graph Algorithms and Applications, 10(2):259-285, 2006.

W. Didimo, F. Giordano, and G. Liotta. Upward spirality and upward planarity testing. In Proc. GD'05, volume 3843 of LNCS, pages 117-128, 2005.

M. R. Garey and D. S. Johnson. Comput. and Intract. Freeman and C., 1979.

A. Garg and R. Tamassia. On the computational complexity of upward and rectilinear planarity testing. SIAM J. Comput., 31(2):601-625, 2001.

P. Healy and K. Lynch. Fixed-parameter tractable algorithms for testing upward planarity. International Journal of Foundations of Computer Science, 17(5), 2006.

M. D. Hutton and A. Lubiw. Upward planarity testing of single-source acyclic digraphs. SIAM J. Comput., 25(2):291-311, 1996.

D. Lichtenstein. Planar formulae and their uses. SIAM J. Comput., 11(2):329-343, 1982.

A. Papakostas. Upward planarity testing of outerplanar dags. In proc. GD'94, volume 894 of LNCS, pages 298-306, 1995.