Logo

Login | Create Account

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. [Conference Paper]

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
Classifications:P Styles > P.840 Upward
ID Code:838
Deposited By:GDEA, Administration
Deposited On:24 Jun 2008
Last Modified:18 Sep 2008 13:09
Alternative Locations:http://www.springerlink.com/openurl.asp?genre=article&issn=0302-9743&volume=4875&spage=195

Repository Staff Only: item control page

References

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

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

3. 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.

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

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

6. 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.

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

8. 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.

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

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

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

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

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

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

GDEA is powered by EPrints 3 which is developed by the School of Electronics and Computer Science at the University of Southampton. More information and software credits.