research
∙
10/21/2022
Splay Top Trees
The top tree data structure is an important and fundamental tool in dyna...
share
research
∙
09/28/2022
Adaptive Out-Orientations with Applications
We give simple algorithms for maintaining edge-orientations of a fully-d...
research
∙
09/28/2022
Worst-case Deterministic Fully-Dynamic Planar 2-vertex Connectivity
We study dynamic planar graphs with n vertices, subject to edge deletion...
research
∙
04/19/2022
Massively Parallel Computation and Sublinear-Time Algorithms for Embedded Planar Graphs
While algorithms for planar graphs have received a lot of attention, few...
research
∙
12/21/2020
Escaping an Infinitude of Lions
We consider the following game played in the Euclidean plane: There is a...
research
∙
11/08/2019
Fully-dynamic Planarity Testing in Polylogarithmic Time
Given a dynamic graph subject to insertions and deletions of edges, a na...
research
∙
10/20/2019
Worst-Case Polylog Incremental SPQR-trees: Embeddings, Planarity, and Triconnectivity
We show that every labelled planar graph G can be assigned a canonical e...
research
∙
09/24/2019
Random k-out subgraph leaves only O(n/k) inter-component edges
Each vertex of an arbitrary simple graph on n vertices chooses k random ...
research
∙
08/07/2018
Good r-divisions Imply Optimal Amortised Decremental Biconnectivity
We present a data structure that given a graph G of n vertices and m edg...
research
∙
06/28/2018
Decremental SPQR-trees for Planar Graphs
We present a decremental data structure for maintaining the SPQR-tree of...
research
∙
08/24/2017