4 citations · 7 across the 4 of their papers we have counts for
13 papers · 1 filter
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…
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…
Space Efficient Construction of Lyndon Arrays in Linear Time
Philip Bille, Jonas Ellert, Johannes Fischer +4
We present the first linear time algorithm to construct the -bit version of the Lyndon array for a string of length using only bits of working space. A simpler varia…
Fully-dynamic Planarity Testing in Polylogarithmic Time
Jacob Holm, Eva Rotenberg
Given a dynamic graph subject to insertions and deletions of edges, a natural question is whether the graph presently admits a planar embedding. We give a deterministic fully-dynam…
Worst-Case Polylog Incremental SPQR-trees: Embeddings, Planarity, and Triconnectivity
Jacob Holm, Eva Rotenberg
We show that every labelled planar graph can be assigned a canonical embedding , such that for any planar that differs from by the insertion or deletion of one e…