research
∙
03/13/2023
Multilevel Skeletonization Using Local Separators
In this paper we give a new, efficient algorithm for computing curve ske...
share
research
∙
12/14/2022
Data Structures for Approximate Discrete Fréchet Distance
The Fréchet distance is one of the most studied distance measures betwee...
research
∙
11/30/2022
Gapped String Indexing in Subquadratic Space and Sublinear Query Time
In Gapped String Indexing, the goal is to compactly represent a string S...
research
∙
11/13/2022
Improved Dynamic Colouring of Sparse Graphs
Given a dynamic graph subject to edge insertions and deletions, we show ...
research
∙
10/21/2022
Splay Top Trees
The top tree data structure is an important and fundamental tool in dyna...
research
∙
09/28/2022
Dynamic Embeddings of Dynamic Single-Source Upward Planar Graphs
A directed graph G is upward planar if it admits a planar embedding such...
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
∙
03/11/2022
Fully-dynamic α+ 2 Arboricity Decomposition and Implicit Colouring
In the implicit dynamic colouring problem, the task is to maintain a rep...
research
∙
01/06/2022
On the Discrete Fréchet Distance in a Graph
The Fréchet distance is a well-studied similarity measure between curves...
research
∙
12/21/2020
Escaping an Infinitude of Lions
We consider the following game played in the Euclidean plane: There is a...
research
∙
07/08/2020
String Indexing for Top-k Close Consecutive Occurrences
The classic string indexing problem is to preprocess a string S into a c...
research
∙
07/07/2020
Skeletonization via Local Separators
We propose a new algorithm for curve skeleton computation which differs ...
research
∙
11/08/2019
Space Efficient Construction of Lyndon Arrays in Linear Time
We present the first linear time algorithm to construct the 2n-bit versi...
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
∙
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
∙
06/08/2018
Compressed Communication Complexity of Longest Common Prefixes
We consider the communication complexity of fundamental longest common p...
research
∙
03/31/2018
Fast Fencing
We consider very natural "fence enclosure" problems studied by Capoyleas...
research
∙
03/05/2018
String Attractors: Verification and Optimization
String attractors [STOC 2018] are combinatorial objects recently introdu...
research
∙
11/03/2017
The Bane of Low-Dimensionality Clustering
In this paper, we give a conditional lower bound of n^Ω(k) on running ti...
research
∙
08/24/2017