4 citations · 23 across the 22 of their papers we have counts for
Showing 2019Show all
3 papers · 1 filter
cs.DS2019
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…
cs.DS2019
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…
cs.DS2019
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…