David Eppstein - Publications

Dynamic graph algorithms

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

• Offline algorithms for dynamic minimum spanning tree problems.
  D. Eppstein.
  2nd Worksh. Algorithms and Data Structures, Ottawa, Canada, 1991.
  Springer, Lecture Notes in Comp. Sci. 519, 1991, pp. 392–399.
  Tech. Rep. 92-04, ICS, UCI, 1992.
  J. Algorithms 17: 237–250, 1994.

  Given a sequence of edge insertions and deletions in a graph, finds the corresponding sequence of minimum spanning tree changes, in logarithmic time per update. Similarly solves the planar geometric version of the problem (using a novel "mixed MST" formulation in which part of the input is a graph and part is a point set) in time \(O(\log^2 n)\) for the Euclidean metric and \(O(\log n\log\log n)\) for the rectilinear metric.

• Asymptotic speed-ups in constructive solid geometry.
  D. Eppstein.
  Tech. Rep. 92-87, ICS, UCI, 1992.
  Algorithmica 13: 462–471, 1995.

  Finds boundary representations of CSG objects. Uses techniques from dynamic graph algorithms, including a tree partitioning technique of Frederickson and a new data structure for maintaining the value of a Boolean expression with changing variables in time O(log n / log log n) per update.

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

• Separator based sparsification II: edge and vertex connectivity.
  D. Eppstein, Z. Galil, G.F. Italiano, and T. Spencer.
  Tech. Rep. CS96-13, Univ. Ca' Foscari di Venezia, Oct. 1996.
  SIAM J. Computing 28 (1): 341–381, 1999.

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

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

• Clustering for faster network simplex pivots.
  D. Eppstein.
  Tech. Rep. 93-19, ICS, UCI, 1993.
  5th ACM-SIAM Symp. Discrete Algorithms, Arlington, 1994, pp. 160–166.
  Networks 35 (3): 173–180, 2000.

  Speeds up the worst case time per pivot for various versions of the network simplex algorithm for minimum cost flow problems. Uses techniques from dynamic graph algorithms as well as some simple geometric data structures.

• Dynamic connectivity in digital images.
  D. Eppstein.
  Tech. Rep. 96-13, ICS, UCI, 1996.
  Inf. Proc. Lett. 62: 121–126, 1997.

  Any algorithm that maintains the connected components of a bitmap image must take Omega(log n / log log n) time per change to the image. The problem can be solved in O(log n) time per change using dynamic planar graph techniques. We discuss applications to computer Go and other games.

• Dynamic graph algorithms.
  D. Eppstein, Z. Galil, and G.F. Italiano.
  Tech. Rep. CS96-11, Univ. Ca' Foscari di Venezia, Oct. 1996.
  Algorithms and Theoretical Computing Handbook, M. J. Atallah, ed., CRC Press, 1999, chapter 8.
  2nd. ed., CRC Press, 2010, Vol. I: General Concepts and Techniques, chapter 9, pp. 9–1 - 9-28.
  
• Guest editor's forward to special issue on dynamic graph algorithms.
  D. Eppstein.
  Algorithmica 22 (3): 233–234, 1998.
  
• Graphs for dynamic geometry.
  D. Eppstein.
  Invited talk, Worksh. Dynamic Graph Algorithms, Victoria, Canada, 2000.

  This talk surveys work on computational geometry algorithms that use dynamic graph data structures, and the different kinds of geometric graph arising in this work.

• Dynamic generators of topologically embedded graphs.
  D. Eppstein.
  arXiv:cs.DS/0207082.
  14th ACM-SIAM Symp. Discrete Algorithms, Baltimore, 2003, pp. 599–608.

  We describe a decomposition of graphs embedded on 2-dimensional manifolds into three subgraphs: a spanning tree, a dual spanning tree, and a set of leftover edges with cardinality determined by the genus of the manifold. This tree-cotree decomposition allows us to find efficient data structures for dynamic graphs (allowing updates that change the surface), better constants in bounded-genus graph separators, and efficient algorithms for tree-decomposition of bounded-genus bounded-diameter graphs.

  (SODA talk slides)

• All maximal independent sets and dynamic dominance for sparse graphs.
  D. Eppstein.
  arXiv:cs.DS/0407036.
  16th ACM-SIAM Symp. Discrete Algorithms, Vancouver, 2005, pp. 451–459.
  ACM Trans. Algorithms 5(4):A38, 2009.

  We show how to apply reverse search to list all maximal independent sets in bounded-degree graphs in constant time per set, in graphs from minor closed families in linear time per set, and in sparse graphs in subquadratic time per set. The latter two results rely on new data structures for maintaining a dynamic vertex set in a graph and quickly testing whether the set dominates all other vertices.

  (SODA05 talk slides)

• The h-index of a graph and its application to dynamic subgraph statistics.
  D. Eppstein and E. S. Spiro.
  arXiv:0904.3741.
  Algorithms and Data Structures Symposium (WADS), Banff, Canada.
  Springer, Lecture Notes in Comp. Sci. 5664, 2009, pp. 278–289.
  J. Graph Algorithms and Applications 16 (2): 543–567, 2012.

  We define the h-index of a graph to be the maximum h such that the graph has h vertices each of which has degree at least h. We show that the h-index, and a partition of the graph into high and low degree vertices, may be maintained in constant time per update. Based on this technique, we show how to maintain the number of triangles in a dynamic graph in time O(h) per update; this problem is motivated by Markov Chain Monte Caro simulation of the Exponential Random Graph Model used for simulation of social networks. We also prove bounds on the h-index for scale-free graphs and investigate the behavior of the h-index on a corpus of real social networks.

  (Slides)

• Extended dynamic subgraph statistics using h-index parameterized data structures.
  D. Eppstein, M. T. Goodrich, D. Strash, and L. Trott.
  Proc. 4th Int. Conf. on Combinatorial Optimization and Applications (COCOA 2010), Hawaii, 2010.
  Springer, Lecture Notes in Comp. Sci. 6508, 2010, pp. 128–141.
  arXiv:1009.0783.
  Theor. Comput. Sci. 447: 44–52, 2012 (special issue for COCOA 2010).

  An earlier paper with Spiro at WADS 2009 provided dynamic graph algorithms for counting how many copies of each possible type of subgraph there are in a larger undirected graph, when the subgraphs have at most three vertices. This paper extends the method to directed graphs and to larger numbers of vertices per subgraph.

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

• Reactive proximity data structures for graphs.
  D. Eppstein, M. T. Goodrich, and N. Mamano.
  arXiv:1803.04555.
  Proc. 13th Latin American Theoretical Informatics Symposium (LATIN 2018), Buenos Aires, Argentina.
  Springer, Lecture Notes in Comp. Sci. 10807 (2018), pp. 777–789.

  We develop data structures for solving nearest neighbor queries for dynamic subsets of vertices in a planar graph, or more generally for a graph in any graph class with small separators (polynomial expansion).