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 , 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
URI: http://gdea.informatik.uni-koeln.de/id/eprint/686

Actions (login required)

View Item View Item