TY - CHAP

T1 - Worst-Case Polylog Incremental SPQR-trees

T2 - 2020 ACM-SIAM Symposium on Discrete Algorithms

AU - Holm, Jacob

AU - Rotenberg, Eva

PY - 2020

Y1 - 2020

N2 - 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 (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 (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 (log3 n) time. Using this, we obtain deterministic data structures for incremental planarity testing, incremental planar embedding, and incremental triconnectivity, that each have worst case (log3 n) update and query time, answering an open question by La Poutré and Westbrook from 1998.

AB - 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 (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 (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 (log3 n) time. Using this, we obtain deterministic data structures for incremental planarity testing, incremental planar embedding, and incremental triconnectivity, that each have worst case (log3 n) update and query time, answering an open question by La Poutré and Westbrook from 1998.

U2 - 10.1137/1.9781611975994.146

DO - 10.1137/1.9781611975994.146

M3 - Book chapter

SP - 2378

EP - 2397

BT - Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms

A2 - Chawla, Shuchi

PB - Society for Industrial and Applied Mathematics

Y2 - 5 January 2020 through 8 January 2020

ER -