A Fully Dynamic Algorithm to Test the Upward Planarity of Single-Source Embedded Digraphs

Rextin, Aimal and Healy, Patrick (2009) A Fully Dynamic Algorithm to Test the Upward Planarity of Single-Source Embedded Digraphs. In: Graph Drawing 16th International Symposium, GD 2008, September 21- 24, 2008 , pp. 254-265(Official URL: http://dx.doi.org/10.1007/978-3-642-00219-9_24).

Full text not available from this repository.

Abstract

In this chapter, we present a dynamic algorithm that checks if a singlesource embedded digraph is upward planar in the presence of edge insertions and edge deletions. Let Gφ be an upward planar single-source embedded digraph and ′ let Gφ ′ be a single-source embedded digraph obtained by updating Gφ . We show ′ that the upward planarity of Gφ ′ can be checked in O(log n) amortized time when the external face is fixed.

Item Type: Conference Paper
Additional Information: 10.1007/978-3-642-00219-9_24
Classifications: P Styles > P.840 Upward
M Methods > M.300 Dynamic / Incremental / Online
G Algorithms and Complexity > G.770 Planarity Testing
URI: http://gdea.informatik.uni-koeln.de/id/eprint/911

Actions (login required)

View Item View Item