Worst-Case Polylog Incremental SPQR-trees: Embeddings, Planarity, and Triconnectivity

Jacob Holm, Eva Rotenberg

Research output: Chapter in Book/Report/Conference proceedingArticle in proceedingsResearchpeer-review

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 languageEnglish
Title of host publicationProceedings of ACM-SIAM Symposium on Discrete Algorithms
PublisherAssociation for Computing Machinery
Publication date2020
Pages2378-2397
ISBN (Electronic)978-1-61197-599-4
DOIs
Publication statusPublished - 2020
EventACM-SIAM Symposium on Discrete Algorithms - Hilton Salt Lake City Center, Salt Lake City, United States
Duration: 5 Jan 20208 Jan 2020
https://www.siam.org/conferences/cm/conference/soda20

Conference

ConferenceACM-SIAM Symposium on Discrete Algorithms
LocationHilton Salt Lake City Center
CountryUnited States
CitySalt Lake City
Period05/01/202008/01/2020
Internet address

Fingerprint

Dive into the research topics of 'Worst-Case Polylog Incremental SPQR-trees: Embeddings, Planarity, and Triconnectivity'. Together they form a unique fingerprint.

Cite this