BARC talk by Ivor van der Hoog

Wednesday, 15 June 2022, Ivor van der Hoog, postdoc at Technical University of Denmark, will give a talk on "Worst-case deterministic fully-dynamic biconnectivity in planar embedded graph".

Title:
Worst-case deterministic fully-dynamic biconnectivity in planar embedded graph.

Abstract:
Two points (u, v) in a graph G are connected whenever there exists an undirected path from u to v. Two points (u, v) are biconnected, or two-vertex connected, whenever for all vertices s not equal to u and v, the vertices (u, v) are still connected in G \ {s}. A biconnectivity query returns for any two vertices (u, v) whether they are biconnected (or, returns a witness s for whenever they are not biconnected).
We present a data structure that supports biconnectivity for planar embedded graphs. We  support edge insertion (as long as some face contains both endpoints), edge deletion, edge contraction, and the splitting of a vertex in specified corners, in O(log^2 n ) worst-case time per operation, while answering biconnectivity queries in O(\log^2 n) worst-case time. In case a pair of connected vertices are not biconnected, we may find the first and last cutvertex separating them in worst-case O(log^2 n) time. Additionally, we allow local changes to the embedding by flipping the embedding of a subgraph that is connected by at most two vertices to the rest of the graph, and we support these changes in O(log^2 n) time.

Bio:
Ivor studied math and computer science in Utrecht, the Netherlands, before starting his PhD studies in Utrecht, under the supervision of Maarten Löffler and Marc van Kreveld. His dissertation focusses on algorithms within computational geometry: studying its theoretical model of computation, geometric models for (arithmetic or computational) imprecision and data structures.
Since January 2022 he is a postdoc in the group of Eva Rotenberg at the Technical University of Denmark. He continues to work on algorithmic problems in a planar setting, expanding his interests towards other areas within theoretical computer science such as graph theory and fine-grained complexity.