David Eppstein - Publications

Matching

• Fast optimal parallel algorithms for maximal matching in sparse graphs.
  H. Asuri, M. Dillencourt, D. Eppstein, G. Lueker, and M. Molodowitch.
  Tech. Rep. 92-01, ICS, UCI, 1992.

  We later discovered that the same results were published in a SPAA paper by Greg Shannon.

• Worst-case bounds for subadditive geometric graphs.
  M. Bern and D. Eppstein.
  9th ACM Symp. Comp. Geom., San Diego, 1993, pp. 183–188.

  For many geometric graph problems for points in the unit square, such as minimum spanning trees, matching, and traveling salesmen, the sum of edge lengths is O(sqrt n) and the sum of dth powers of edge lengths is O(log n). We provide a "gap theorem" showing that if these bounds do not hold for a class of graphs, both sums will instead be Omega(n). For traveling salesmen the O(log n) bound is tight but for some other graphs the sum of dth powers of edge lengths is O(1).

  (Preprint of SCG version)

• Representing all minimum spanning trees with applications to counting and generation.
  D. Eppstein.
  Tech. Rep. 95-50, ICS, UCI, 1995.

  Shows how to find for any edge weighted graph G an equivalent graph EG such that the minimum spanning trees of G correspond one-for-one with the spanning trees of EG. The equivalent graph can be constructed in time O(m+n log n) given a single minimum spanning tree of G. As a consequence one can find fast algorithms for counting, listing, and randomly generating MSTs. Also discusses similar equivalent graph constructions for shortest paths, minimum cost flows, and bipartite matching.

• Fast hierarchical clustering and other applications of dynamic closest pairs.
  D. Eppstein.
  9th ACM-SIAM Symp. Discrete Algorithms, San Francisco, 1998, pp. 619–628.
  arXiv:cs.DS/9912014.
  J. Experimental Algorithmics 5 (1): 1–23, 2000.

  This paper shows how to use my dynamic closest pair data structure from "Dynamic Euclidean minimum spanning trees" for some non-geometric problems including hierarchical clustering, greedy matching, and TSP heuristics. Experiments show variants of my data structures to be faster than previously used heuristics.

  (Source code and experimental data – SODA paper – JEA home page)

• Single-strip triangulation of manifolds with arbitrary topology.
  D. Eppstein and M. Gopi.
  13th Video Review of Computational Geometry, 2004.
  20th ACM Symp. Comp. Geom., Brooklyn, 2004, pp. 455–456 (abstract for video).
  25th Conf. Eur. Assoc. for Computer Graphics (EuroGraphics '04), Grenoble, 2004 (2nd best paper award).
  Eurographics Forum 23 (3): 371–379, 2004.
  arXiv:cs.CG/0405036.

  We describe a new algorithm, based on graph matching, for subdividing a triangle mesh (without boundary) so that it has a Hamiltonian cycle of triangles, and prove that this subdivision process increases the total number of triangles in the mesh by at most a factor of 3/2. We also prove lower bounds on the increase needed for meshes with and without boundary.

  (Graphics lab pubs page)

• The lattice dimension of a graph.
  D. Eppstein.
  arXiv:cs.DS/0402028.
  Eur. J. Combinatorics 26 (6): 585–592, 2005.

  Describes a polynomial time algorithm for isometrically embedding graphs into an integer lattice of the smallest possible dimension. The technique involves maximum matching in an auxiliary graph derived from a partial cube representation of the input.

• Single triangle strip and loop on manifolds with boundaries.
  A. Bushan, P. Diaz-Gutierrez, D. Eppstein, and M. Gopi.
  Tech. Rep. 05-11, UC Irvine, School of Information and Computer Science, 2005.
  Proc. 19th Brazilian Symp. Computer Graphics and Image Processing (SIBGRAPI 2006), pp. 221–228.

  This follows on to our previous paper on using graph matching to cover a triangulated polyhedral model with a single triangle strip by extending the algorithms to models with boundaries. We provide two methods: one is based on using an algorithm for the Chinese Postman problem to find a small set of triangles to split in order to find a perfect matching in the dual mesh, while the other augments the model with virtual triangles to remove the boundaries and merges the strips formed by our previous algorithm on this augmented model. We implement the algorithms and report some preliminary experimental results.

  (Graphics lab pubs page)

• Algorithms for stable matching and clustering in a grid.
  D. Eppstein, M. T. Goodrich, and N. Mamano.
  arXiv:1704.02303
  Proc. 18th International Workshop on Combinatorial Image Analysis (IWCIA 2017), Plovdiv, Bulgaria, 2017.
  Springer, Lecture Notes in Comp. Sci. 10256 (2017), pp. 117–131.

  Motivated by redistricting, we consider geometric variants of the stable matching problem in which points (such as the pixels of a discretization of the unit square) are to be matched to a smaller number of centers such that each center has the same number of matches and no match is unstable with respect to Euclidean distances. We show how to solve such problems in polylogarithmic time per matched point, experiment with practical heuristics for solving these problems, and test methods for moving the centers to improve the shape of the matched regions.

• Defining equitable geographic districts in road networks via stable matching.
  D. Eppstein, M. T. Goodrich, D. Korkmaz, and N. Mamano.
  arXiv:1706.09593
  Proc. 25th ACM SIGSPATIAL Int. Conf. Advances in Geographic Information Systems (ACM SIGSPATIAL 2017), Redondo Beach, California, pp. 52:1–52:4.
  

  We cluster road networks (modeled as planar graphs, or more generally as graphs obeying a separator theorem) with a given set of cluster centers, by matching graph vertices to centers stably according to distance: no unmatched vertex and center should have smaller distances than the matched pairs for the same points. We provide a separator-based data structure for dynamic nearest neighbor queries in planar or separated graphs, which allows the optimal stable clustering to be constructed in time O(n^3/2log n). We also experiment with heuristics for fast practical construction of this clustering.

• NC algorithms for perfect matching and maximum flow in one-crossing-minor-free graphs.
  D. Eppstein and V. V. Vazirani.
  arXiv:1802.00084.
  Proc. 30th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA 2019), Phoenix, Arizona, 2019, pp. 23–30.
  SIAM J. Computing 50 (3): 1014–1033, 2021.

  We extend Anari and Vazirani's parallel algorithm for perfect matching in planar graphs to the graph families with a forbidden minor with crossing number one, by developing a concept of mimicking networks for perfect matching.

  (Slides)

• The graphs of stably matchable pairs.
  D. Eppstein.
  arXiv:2010.09230.
  47th International Workshop on Graph-Theoretic Concepts in Computer Science (WG 2021).
  Springer, Lecture Notes in Comp. Sci. 12911 (2021), pp. 349–360.
  

  If you form a bipartite graph from a stable matching instance, with an edge for each pair that can participate in a stable matching, what graphs can you get? They are matching-covered, but NP-hard to recognize, and their structure is related to the structure of the lattice of stable matchings of the same instance.

  (Slides)