David Eppstein - Publications

Minimum spanning trees

• Maintenance of a minimum spanning forest in a dynamic plane graph.
  D. Eppstein, G.F. Italiano, R. Tamassia, R.E. Tarjan, J. Westbrook, and M. Yung.
  1st ACM-SIAM Symp. Discrete Algorithms, San Francisco, 1990, pp. 1–11.
  J. Algorithms 13 (1): 33–54, 1992 (special issue for 1st Symp. Discrete Algorithms).
  Corrigendum, J. Algorithms 15: 173, 1993.

  The complement of a minimum spanning tree is a maximum spanning tree in the dual graph. By applying this fact we can use a modified form of Sleator and Tarjan's dynamic tree data structure to update the MST in logarithmic time per update.

• Approximating the minimum weight Steiner triangulation.
  D. Eppstein.
  Tech. Rep. 91-55, ICS, UCI, 1991.
  3rd ACM-SIAM Symp. Discrete Algorithms, Orlando, 1992, pp. 48–57.
  Disc. Comp. Geom. 11: 163–191, 1994.

  Quadtree based triangulation gives a large but constant factor approximation to the minimum weight triangulation of a point set or convex polygon, allowing extra Steiner points to be added as vertices. Includes proofs of several bounds on triangulation weight relative to the minimum spanning tree or non-Steiner triangulation, and a conjecture that for convex polygons the only points that need to be added are on the polygon boundary.

• Tree-weighted neighbors and geometric k smallest spanning trees.
  D. Eppstein.
  Tech. Rep. 92-77, ICS, UCI, 1992.
  Int. J. Comp. Geom. & Appl. 4: 229–238, 1994.

  "Finding the k smallest spanning trees" used higher order Voronoi diagrams to reduce the geometric k smallest spanning tree problem to the graph problem. Here I instead use nearest neighbors for a modified distance function where the bottleneck shortest path length is subtracted from the true distance between points. The result improves the planar time bounds and extends more easily to higher dimensions.

• On the number of minimal 1-Steiner trees.
  B. Aronov, M. Bern, and D. Eppstein.
  Disc. & Comp. Geom. 12: 29–34, 1994.

  Given a d-dimensional set of n points, the number of combinatorially different minimum spanning trees that can be formed by adding one more point is within a polylogarithmic factor of n^d.

• Dynamic Euclidean minimum spanning trees and extrema of binary functions.
  D. Eppstein.
  Tech. Rep. 92-05, ICS, UCI, 1992.
  Tech. Rep. 92-88, ICS, UCI, 1992.
  Disc. Comp. Geom. 13: 111–122, 1995.

  Shows that bichromatic nearest neighbors can be maintained under point insertion and deletion essentially as quickly as known solutions to the post office problem, and that the minimum spanning tree can be maintained in the same time except for an additive O(sqrt n) needed for solving the corresponding graph problem. TR 92-88's title was actually "Fully dynamic maintenance of Euclidean minimum spanning trees and maxima of decomposable functions". TR 92-05's title left out the part about maxima; that version gave a slower algorithm superseded by the result in 92-88.

• Dynamic algorithms for half-space reporting, proximity problems, and geometric minimum spanning trees.
  P.K. Agarwal, D. Eppstein, and J. Matoušek.
  33rd IEEE Symp. Foundations of Comp. Sci., Pittsburgh, 1992, pp. 80–89.

  This conference paper merged my results from "Dynamic Euclidean minimum spanning trees" with results of my co-authors on nearest neighbors and halfspace range searching.

• Sparsification—A technique for speeding up dynamic graph algorithms.
  D. Eppstein, Z. Galil, G.F. Italiano, and A. Nissenzweig.
  33rd IEEE Symp. Foundations of Comp. Sci., Pittsburgh, 1992, pp. 60–69.
  Tech. Rep. RC 19272 (83907), IBM, 1993.
  Tech. Rep. CS96-11, Univ. Ca' Foscari di Venezia, Oct. 1996.
  J. ACM 44 (5): 669–696, 1997.

  Uses a divide and conquer on the edge set of a graph, together with the idea of replacing subgraphs by sparser certificates, to make various dynamic algorithms as fast on dense graphs as they are on sparse graphs. Applications include random generation of spanning trees as well as finding the \(k\) minimum weight spanning trees for a given parameter \(k\).

• Improved sparsification.
  D. Eppstein, Z. Galil, and G.F. Italiano.
  Tech. Rep. 93-20, ICS, UCI, 1993.

  Saves a log factor over dynamic graph algorithms in "Sparsification" and their applications, by dividing vertices instead of edges. Merged into the journal version of "Sparsification".

• Separator based sparsification for dynamic planar graph algorithms.
  D. Eppstein, Z. Galil, G.F. Italiano, and T. Spencer.
  25th ACM Symp. Theory of Computing, San Diego, 1993, pp. 208–217.

  Replaces portions of a hierarchical separator decomposition with smaller certificates to achieve fast update times for various dynamic planar graph problems. Applications include finding the k best spanning trees of a planar graph.

• Separator based sparsification I: planarity testing and minimum spanning trees.
  D. Eppstein, Z. Galil, G.F. Italiano, and T. Spencer.
  J. Comp. Sys. Sci. 52: 3–27, 1996 (special issue for 25th STOC).

  First half of journal version of Separator based sparsification for dynamic planar graph algorithms.

• Average case analysis of dynamic geometric optimization.
  D. Eppstein.
  Tech. Rep. 93-18, ICS, UCI, 1993.
  5th ACM-SIAM Symp. Discrete Algorithms, Arlington, 1994, pp. 77–86.
  Comp. Geom. Theory & Applications 6: 45–68, 1996.

  The Tech. Report used the more informative title "Updating widths and maximum spanning trees using the rotating caliper graph", which I also used for the journal submission, but the referees made me change it back. Dynamic geometry in a model of Mulmuley and Schwarzkopf in which insertions and deletions are chosen randomly among a worst-case pool of points. This paper introduces several fundamental techniques including the rotating caliper graph of a point set and a method for performing decomposible range queries in the average case setting. It has also since inspired the use of a similar model in dynamic graph algorithms.

  (SODA paper – Full paper)

• Faster circle packing with application to nonobtuse triangulation.
  D. Eppstein.
  Tech. Rep. 94-33, ICS, UCI 1994.
  Int. J. Comp. Geom. & Appl. 7 (5): 485–491, 1997.

  Speeds up a triangulation algorithm of Bern et al. ["Linear-Size Nonobtuse Triangulation of Polygons"] by finding a collection of disjoint circles which connect up the holes in a non-simple polygon. The method is to use a minimum spanning tree to find a collection of overlapping circles, then shrink them one by one to reduce the number of overlaps, using Sleator and Tarjan's dynamic tree data structure to keep track of the connectivity of the shrunken circles.

• 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)

• Geometric lower bounds for parametric matroid optimization.
  D. Eppstein.
  Tech. Rep. 95-11, ICS, UCI, 1995.
  27th ACM Symp. Theory of Computing, Las Vegas, 1995, pp. 662–671.
  Disc. Comp. Geom. 20: 463–476, 1998.

  Considers graphs in which edge weights are linear functions of time. Shows nonlinear lower bounds on the number of different minimum spanning trees appearing over time by translation from geometric problem of lower envelopes of line segments. A matroid generalization has a better lower bound coming from many faces in line arrangements, and the uniform matroid problem is equivalent to the geometric k-set problem.

• Faster geometric k-point MST approximation.
  D. Eppstein.
  Tech. Rep. 95-13, ICS, UCI, 1995.
  Comp. Geom. Theory & Applications 8: 231–240, 1997.

  Various authors have looked at a variant of geometric clustering in which one must select k points that can be connected by a small spanning tree. The problem is NP-complete (for variable k); good approximations are known based on dynamic programming techniques but the time dependence on n is high. This paper describes a faster approximation algorithm based on dynamic programming in quadtrees, and a general technique based on that in "Iterated nearest neighbors" for reducing the dependence on n in any approximation algorithm.

• 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.

• Using sparsification for parametric minimum spanning tree problems.
  D. Fernández-Baca, G. Slutzki, and D. Eppstein.
  5th Scand. Worksh. Algorithm Theory, Reykjavik, 1996.
  Springer, Lecture Notes in Comp. Sci. 1097, 1996, pp. 149–160.
  Nordic J. Computing 3 (4): 352–366, 1996 (special issue for 5th SWAT).

  Given a graph with edge weights that are linear functions of a parameter, finds the sequence of minimum spanning trees produced as the parameter varies, in total time O(mn log n), by combining ideas from "Sparsification" and "Geometric lower bounds". Also solves various problems of optimizing the parameter value, including one closely related to that in "Choosing subsets with maximum weighted average".

• On the parity of graph spanning tree numbers.
  D. Eppstein.
  Tech. Rep. 96-14, ICS, UCI, 1996.

  Any bipartite Eulerian graph, any Eulerian graph with evenly many vertices, and any bipartite graph with evenly many vertices and edges, has an even number of spanning trees. More generally, a graph has evenly many spanning trees if and only if it has an Eulerian edge cut.

• Parametric and kinetic minimum spanning trees.
  P. K. Agarwal, D. Eppstein, L. J. Guibas, and M. R. Henzinger.
  39th IEEE Symp. Foundations of Comp. Sci., 1998, pp. 596–605..

  We describe algorithms for maintaining the minimum spanning tree in a graph in which the edge weights are piecewise linear functions of time that may change unpredictably. We solve the problem in time O(n^2/3 polylog n) per combinatorial change to the tree for general graphs, and in time O(n^1/4 polylog n) per combinatorial change to the tree for planar graphs.

  (FOCS '98 talk slides)

• Setting parameters by example.
  D. Eppstein.
  arXiv:cs.DS/9907001.
  40th IEEE Symp. Foundations of Comp. Sci., 1999, pp. 309–318.
  SIAM J. Computing 32 (3): 643–653, 2003.

  We introduce a class of "inverse parametric optimization" problems, in which one is given both a parametric optimization problem and a desired optimal solution; the task is to determine parameter values that lead to the given solution. We use low-dimensional linear programming and geometric sampling techniques to solve such problems for minimum spanning trees, shortest paths, and other optimal subgraph problems, and discuss applications in multicast routing, vehicle path planning, resource allocation, and board game programming.

• Testing bipartiteness of geometric intersection graphs.
  D. Eppstein.
  arXiv:cs.CG/0307023.
  15th ACM-SIAM Symp. Discrete Algorithms, New Orleans, 2004, pp. 853–861.
  ACM Trans. Algorithms 5(2):15, 2009.

  We consider problems of partitioning sets of geometric objects into two subsets, such that no two objects within the same subset intersect each other. Typically, such problems can be solved in quadratic time by constructing the intersection graph and then applying a graph bipartiteness testing algorithm; we achieve subquadratic times for general objects, and O(n log n) times for balls in R^d or simple polygons in the plane, by using geometric data structures, separator based divide and conquer, and plane sweep techniques, respectively. We also contrast the complexity of bipartiteness testing with that of connectivity testing, and provide evidence that for some classes of object, connectivity is strictly harder due to a computational equivalence with Euclidean minimum spanning trees.

  (SODA talk slides)

• A stronger lower bound on parametric minimum spanning trees.
  D. Eppstein.
  arXiv:2105.05371.
  17th Algorithms and Data Structures Symp. (WADS 2021).
  Springer, Lecture Notes in Comp. Sci. 12808 (2021), pp. 343–356.
  Algorithmica 85: 1738–1753, 2023 (special issue for WADS 2021).
  

  There exist graphs with edges labeled by linear real functions, such that the number of different minimum spanning trees obtained for different choices of the function argument is \(\Omega(m\log n)\).

  (Slides)