4 citations · 23 across the 22 of their papers we have counts for
8 papers · 1 filter
Data Structures for Approximate Discrete Fréchet Distance
Ivor van der Hoog, Eva Rotenberg, Sampson Wong
The Fréchet distance is a popular distance measure between curves and . Conditional lower bounds prohibit -approximate Fréchet distance computations in st…
Improved Dynamic Colouring of Sparse Graphs
Aleksander B. G. Christiansen, Krzysztof D. Nowicki, Eva Rotenberg
Given a dynamic graph subject to edge insertions and deletions, we show how to update an implicit representation of a proper vertex colouring, such that colours of vertices are com…
Gapped String Indexing in Subquadratic Space and Sublinear Query Time
Philip Bille, Inge Li Gørtz, Moshe Lewenstein +3
In Gapped String Indexing, the goal is to compactly represent a string of length such that for any query consisting of two strings and , called patterns, and an…
Splay Top Trees
Jacob Holm, Eva Rotenberg, Alice Ryhl
The top tree data structure is an important and fundamental tool in dynamic graph algorithms. Top trees have existed for decades, and today serve as an ingredient in many state-of-…
Dynamic Embeddings of Dynamic Single-Source Upward Planar Graphs
Ivor van der Hoog, Irene Parada, Eva Rotenberg
A directed graph is upward planar if it admits a planar embedding such that each edge is -monotone. Unlike planarity testing, upward planarity testing is NP-hard except in r…
Worst-case Deterministic Fully-Dynamic Planar 2-vertex Connectivity
Jacob Holm, Ivor van der Hoog, Eva Rotenberg
We study dynamic planar graphs with vertices, subject to edge deletion, edge contraction, edge insertion across a face, and the splitting of a vertex in specified corners. We d…