J. Holm

activity

20032025

most citedMaintaining Information in Fully-Dynamic Trees with Top Trees

5 citations · 22 across the 17 of their papers we have counts for

collaborators

Showing 2019Show all

3 papers · 1 filter

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 $G$ can be assigned a canonical embedding $ϕ (G)$ , such that for any planar $G^{'}$ that differs from $G$ by the insertion or deletion of one e…

cs.DM2019

Random $k$ -out subgraph leaves only $O (n / k)$ inter-component edges

Jacob Holm, Valerie King, Mikkel Thorup +2

Each vertex of an arbitrary simple graph on $n$ vertices chooses $k$ random incident edges. What is the expected number of edges in the original graph that connect different connec…

Fully-dynamic Planarity Testing in Polylogarithmic Time

Worst-Case Polylog Incremental SPQR-trees: Embeddings, Planarity, and Triconnectivity

Random k-out subgraph leaves only O(n/k) inter-component edges

Random $k$ -out subgraph leaves only $O (n / k)$ inter-component edges