Upward Spirality and Upward Planarity Testing

Didimo, Walter and Giordano, Francesco and Liotta, Giuseppe (2006) Upward Spirality and Upward Planarity Testing. In: Graph Drawing 13th International Symposium, GD 2005, September 12-14, 2005, Limerick, Ireland , pp. 117-128 (Official URL: http://dx.doi.org/10.1007/11618058_12).

Full text not available from this repository.

Abstract

Let G be a digraph whose SPQR-tree does not have any R-node. The main result of this paper is a polynomial-time algorithm that tests whether G is upward planar and, if so, returns an upward planar representation of G. As an application of this result, a new FPT algorithm is presented that solves the upward planarity testing problem for general digraphs. Our results use the new notion of upward spirality that, informally speaking, is a measure of the "level of winding" that a triconnected component of G can have in an upward pla nar representation of G.

Item Type:Conference Paper
Additional Information:10.1007/11618058_12
Classifications:P Styles > P.840 Upward
G Algorithms and Complexity > G.490 Embeddings
G Algorithms and Complexity > G.770 Planarity Testing
ID Code:686

Repository Staff Only: item control page

References

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

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

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

H. Chan.: A parameterized algorithm for upward planarity testing. 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, G. Liotta, and F. Vargiu.: Spirality and optimal orthogonal drawings. SIAM J. Comput., 27(6):275-298, 1998.

G. Di Battista and R.Tamassia. On-line planarity testing. SIAM J. Comput., 25:956-997, 1996.

W. Didimo, F. Giordano, and G. Liotta.: Upward spirality and upward planarity testing. Technical report, 2005. RT-006-05, DIEI - Universita di Perugia, Italy.

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.: Building blocks of upward planar digraphs.Proc. GD '04, volume 3383 of LNCS, pages 296-306, 2004.

P. Healy and K. Lynch.: Building blocks of upward planar digraphs. Technical report, 2005. TR UL-CSIS-05-2.

P. Healy and K. Lynch.: Fixed-parameter tractable algorithms for testing upward planarity. Proc. SOFSEM '05, volume 3381 of LNCS, pages 199-208, 2005.

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

A. Papakostas.: Upward planarity testing of outerplanar dags. Proc. GD '95, volume 894 of LNCS, pages 7298-306, 1995.