2019/10/20 by Jacob Holm, Holm, Jacob, Eva Rotenberg +1
Biochemistry, Genetics and Molecular Biology · Computer Science · #Advanced Graph Theory Research #Advanced biosensing and bioanalysis techniques #Complexity and Algorithms in Graphs #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences
paper · pdf · doi:10.48550/arxiv.1910.09005
openalex publication_date 2019/10/20 · openalex created_date 2022/07/28 · openalex updated_date 2026/07/28
We show that every labelled planar graph G can be assigned a canonical\nembedding \φ(G), such that for any planar G' that differs from G by the\ninsertion or deletion of one edge, the number of local changes to the\ncombinatorial embedding needed to get from \φ(G) to \φ(G') is O(\log\nn).\n In contrast, there exist embedded graphs where \Ω(n) changes are\nnecessary to accommodate one inserted edge. We provide a matching lower bound\nof \Ω(\log n) local changes, and although our upper bound is worst-case,\nour lower bound hold in the amortized case as well.\n Our proof is based on BC trees and SPQR trees, and we develop\n\pre-split variants of these for general graphs, based on a novel biased\nheavy-path decomposition, where the structural changes corresponding to edge\ninsertions and deletions in the underlying graph consist of at most O(\log n)\nbasic operations of a particularly simple form.\n As a secondary result, we show how to maintain the pre-split trees under edge\ninsertions in the underlying graph deterministically in worst case O(\log3\nn) time. Using this, we obtain deterministic data structures for incremental\nplanarity testing, incremental planar embedding, and incremental\ntriconnectivity, that each have worst case O(\log3 n) update and query time,\nanswering an open question by La Poutr 'e and Westbrook from 1998.\n