Abstract
In this paper, we present a dynamic algorithm that checks if a single-source embedded digraph is upward planar in the presence of edge insertions and edge deletions without changing the embedding of the digraph. We show that it can be checked in O(log n) amortized time whether the updated graph is a single-source upward planar digraph with a fixed external face.
Original language | English |
---|---|
Pages (from-to) | 45-59 |
Number of pages | 15 |
Journal | Computer Journal |
Volume | 60 |
Issue number | 1 |
DOIs | |
Publication status | Published - Jan 2017 |
Keywords
- Graph drawing algorithms
- Single source digraphs
- Upward planarity