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, Heraklion, Crete, Greece , pp. 254-265 (Official URL: http://dx.doi.org/10.1007/978-3-642-00219-9_24).
Full text not available from this repository.
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 ﬁxed.
Repository Staff Only: item control page