321 citations · 2k across the 200 of their papers we have counts for
8 papers · 2 filters
Finding Maximal Sets of Laminar 3-Separators in Planar Graphs in Linear Time
David Eppstein, Bruce Reed
We consider decomposing a 3-connected planar graph using laminar separators of size three. We show how to find a maximal set of laminar 3-separators in such a graph in linear t…
Parameterized Leaf Power Recognition via Embedding into Graph Products
David Eppstein, Elham Havvaei
The -leaf power graph of a tree is a graph whose vertices are the leaves of and whose edges connect pairs of leaves at unweighted distance at most~ in . Recogn…
Quadratic Time Algorithms Appear to be Optimal for Sorting Evolving Data
Juan Jose Besa, William E. Devanny, David Eppstein +2
We empirically study sorting in the evolving data model. In this model, a sorting algorithm maintains an approximation to the sorted order of a list of data items while simultaneou…
Optimally Sorting Evolving Data
Juan Jose Besa, William E. Devanny, David Eppstein +2
We give optimal sorting algorithms in the evolving data framework, where an algorithm's input data is changing while the algorithm is executing. In this framework, instead of produ…
Faster Evaluation of Subtraction Games
David Eppstein
Subtraction games are played with one or more heaps of tokens, with players taking turns removing from a single heap a number of tokens belonging to a specified subtraction set; th…
Subexponential-Time and FPT Algorithms for Embedded Flat Clustered Planarity
Giordano Da Lozzo, David Eppstein, Michael T. Goodrich +1
The C-Planarity problem asks for a drawing of a , i.e., a graph whose vertices belong to properly nested clusters, in which each cluster is represented by…