Abstract
We show that every labelled planar graph $G$ can be assigned a canonical
embedding $\phi(G)$, such that for any planar $G'$ that differs from $G$ by the
insertion or deletion of one edge, the number of local changes to the
combinatorial embedding needed to get from $\phi(G)$ to $\phi(G')$ is $O(\log
n)$.
In contrast, there exist embedded graphs where $\Omega(n)$ changes are
necessary to accommodate one inserted edge. We provide a matching lower bound
of $\Omega(\log n)$ local changes, and although our upper bound is worst-case,
our lower bound hold in the amortized case as well.
Our proof is based on BC trees and SPQR trees, and we develop
\emph{pre-split} variants of these for general graphs, based on a novel biased
heavy-path decomposition, where the structural changes corresponding to edge
insertions and deletions in the underlying graph consist of at most $O(\log n)$
basic operations of a particularly simple form.
As a secondary result, we show how to maintain the pre-split trees under edge
insertions in the underlying graph deterministically in worst case $O(\log^3
n)$ time. Using this, we obtain deterministic data structures for incremental
planarity testing, incremental planar embedding, and incremental
triconnectivity, that each have worst case $O(\log^3 n)$ update and query time,
answering an open question by La Poutr\'e and Westbrook from 1998.
Original language | English |
---|---|
Title of host publication | Proceedings of ACM-SIAM Symposium on Discrete Algorithms |
Publisher | Association for Computing Machinery |
Publication date | 2020 |
Pages | 2378-2397 |
ISBN (Electronic) | 978-1-61197-599-4 |
DOIs | |
Publication status | Published - 2020 |
Event | ACM-SIAM Symposium on Discrete Algorithms - Hilton Salt Lake City Center, Salt Lake City, United States Duration: 5 Jan 2020 → 8 Jan 2020 https://www.siam.org/conferences/cm/conference/soda20 |
Conference
Conference | ACM-SIAM Symposium on Discrete Algorithms |
---|---|
Location | Hilton Salt Lake City Center |
Country/Territory | United States |
City | Salt Lake City |
Period | 05/01/2020 → 08/01/2020 |
Internet address |