Fully-dynamic planarity testing in polylogarithmic time
Speaker: Eva Rotenberg (Technical University of Denmark)
Abstract: Given a dynamic graph subject to insertions and deletions of edges, a natural question is whether the graph presently admits a planar embedding. We give a deterministic fully-dynamic algorithm for general graphs, running in amortised O((log n)^3) time per edge insertion or deletion, that maintains a bit indicating whether or not the graph is presently planar. The algorithmic result hinges on the existence of balanced embeddings, and our understanding of these. Namely: 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, that hold in the amortised case as well.
Joint work with Jacob Holm, University of Copenhagen, jaho@di.ku.dk
Based on the following two papers:
- Fully-dynamic planarity testing in polylogarithmic time. STOC 2020
- Worst-Case Polylog Incremental SPQR-trees: Embeddings, Planarity, and Triconnectivity. SODA 2020
Date and time: 17/06/2021 at 14:30 (Paris time)
Link to the talk: https://bbb-temp.grenet.fr/b/lou-9x7-69p