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

We show that every labelled planar graph G can be assigned a canonical embedding φ(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 φ(G) to φ(G ) is O(log n).

In contrast, there exist embedded graphs where Ω(n) changes are necessary to accommodate one inserted edge. We provide a matching lower bound of Ω(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 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é and Westbrook from 1998.