12 citations · 59 across the 19 of their papers we have counts for
Showing 2017Show all
2 papers · 1 filter
cs.DS2017
Contracting a Planar Graph Efficiently
Jacob Holm, Giuseppe F. Italiano, Adam Karczmarz +3
We present a data structure that can maintain a simple planar graph under edge contractions in linear total time. The data structure supports adjacency queries and provides access…
cs.DS2017
Decremental Single-Source Reachability in Planar Digraphs
Giuseppe F. Italiano, Adam Karczmarz, Jakub Łącki +1
In this paper we show a new algorithm for the decremental single-source reachability problem in directed planar graphs. It processes any sequence of edge deletions in $O(n\log^2{n}…