73 citations · 634 across the 97 of their papers we have counts for
7 papers · 1 filter
Low Ply Drawings of Trees and 2-Trees
Michael T. Goodrich, Timothy Johnson
Ply number is a recently developed graph drawing metric inspired by studying road networks. Informally, for each vertex v, which is associated with a point in the plane, a disk is…
Geometric Fingerprint Recognition via Oriented Point-Set Pattern Matching
David Eppstein, Michael T. Goodrich, Jordan Jorgensen +1
Motivated by the problem of fingerprint matching, we present geometric approximation algorithms for matching a pattern point set against a background point set, where the points ha…
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…
Stable-Matching Voronoi Diagrams: Combinatorial Complexity and Algorithms
Gill Barequet, David Eppstein, Michael T. Goodrich +1
We study algorithms and combinatorial complexity bounds for \emph{stable-matching Voronoi diagrams}, where a set, , of point sites in the plane determines a stable matching…
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…