David Eppstein - Publications

2017

• Rooted cycle bases.
  D. Eppstein, J. M. McCarthy, and B. E. Parrish.
  arXiv:1504.04931.
  14th Algorithms and Data Structures Symp. (WADS 2015), Victoria, BC.
  Springer, Lecture Notes in Comp. Sci. 9214 (2015), pp. 339–350.
  J. Graph Algorithms & Applications 21 (4): 663–686, 2017.

  We consider the problem of finding a cycle basis for a graph in which all basis cycles contain a specified edge. We characterize the graphs having such a basis in terms of their vertex connectivity, we show that the minimum weight cycle basis with this constraint can be found in polynomial time and is weakly fundamental, and we show that finding a fundamental cycle basis with this constraint is NP-hard but fixed-parameter tractable.

  (Slides)

• Folding polyominoes into (poly)cubes.
  O. Aichholzer, M. Biro, E. Demaine, M. Demaine, D. Eppstein, S. P. Fekete, A. Hesterberg, I. Kostitsyna, and C. Schmidt.
  27th Canadian Conference on Computational Geometry, Kingston, Ontario, Canada, 2015, pp. 101–106.
  arXiv:1712.09317.
  Int. J. Comp. Geom. & Appl. 28 (3): 197–226, 2018.

  We classify the polyominoes that can be folded to form the surface of a cube or polycube, in multiple different folding models that incorporate the type of fold (mountain or valley), the location of a fold (edges of the polycube only, or elsewhere such as along diagonals), and whether the folded polyomino is allowed to pass through the interior of the polycube or must stay on its surface.

• Structure of graphs with locally restricted crossings.
  V. Dujmović, D. Eppstein, and D. R. Wood.
  arXiv:1506.04380.
  23rd Int. Symp. Graph Drawing, Los Angeles, California, 2015.
  Springer, Lecture Notes in Comp. Sci. 9411 (2015), pp. 87–98.
  SIAM J. Discrete Math. 31 (2): 805–824, 2017.

  The Graph Drawing version used the alternative title "Genus, treewidth, and local crossing number". We prove tight bounds on the treewidth of graphs embedded on low-genus surfaces with few crossings per edge, and nearly tight bounds on the number of crossings per edge for graphs with a given number of edges embedded on low-genus surfaces.

  (Slides — local copy of final version)

• Maximizing the sum of radii of disjoint balls or disks.
  D. Eppstein.
  arXiv:1607.02184.
  Proc. 28th Canadian Conference on Computational Geometry, Vancouver, BC, Canada, 2016, pp. 260–265.
  J. Computational Geometry 8 (1): 316–339, 2017.
  

  We show how to find a system of disjoint balls with given centers, maximizing the sum of radius of the balls. Our algorithm takes cubic time in arbitrary metric spaces and can be sped up to subquadratic time in Euclidean spaces of any bounded dimension.

  (Slides)

• K-best solutions of MSO problems on tree-decomposable graphs.
  D. Eppstein and D. Kurz.
  arXiv:1703.02784.
  Proc. 12th International Symposium on Parameterized and Exact Computation (IPEC 2017), Vienna, Austria, 2017.
  Leibniz International Proceedings in Informatics (LIPIcs) 89, pp. 16.1–16.13

  We show that, on graphs of bounded treewidth, for any optimization problem definable in monadic second-order logic, we can find the k best solutions in logarithmic time per solution.

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

• 2-3 cuckoo filters for faster triangle listing and set intersection.
  D. Eppstein, M. T. Goodrich, M. Mitzenmacher, and M. Torres.
  Proc. 36th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems (PODS 2017), Chicago, 2017, pp. 247–260.
  

  We show that bit-parallel algorithm design techniques, on a machine of word size w, can speed up the time for sparse set intersection by a factor of log w/w. The main data structure underlying our algorithms is the cuckoo filter, a variant of cuckoo hash tables that has operations similar to a Bloom filter but outperforms Bloom filters in several respects.

• Maximum plane trees in multipartite geometric graphs.
  A. Biniaz, P. Bose, J.-L. De Carufel, K. Crosbie, D. Eppstein, A. Maheshwari, M. Smid.
  15th Algorithms and Data Structures Symp. (WADS 2017), St. John's, Newfoundland.
  Springer, Lecture Notes in Comp. Sci. (2017), pp. 193–204.
  Algorithmica 81 (4): 1512–1534, 2019.

  We consider problems of constructing the maximum-length plane (non-self-crossing) spanning tree on Euclidean graphs given by multicolored point sets, where each point forms a vertex, and each bichromatic pair of points forms an edge with length equal to their Euclidean distance. We show that several such problems can be efficiently approximated.

• Using multi-level parallelism and 2-3 cuckoo filters for faster set intersection queries and sparse boolean matrix multiplication.
  D. Eppstein and M. T. Goodrich.
  Brief announcement, Proc. 29th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), Washington, DC, 2017, pp. 137–139.
  

  We provide parallel versions of our bit-parallel algorithms from PODS 2017 for sparse set intersection.

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

• Forbidden configurations in discrete geometry.
  D. Eppstein.
  Paul Erdős Memorial Lecture, 29th Canadian Conference on Computational Geometry, Ottawa, Canada, 2017.
  Invited talk, 20th Japan Conference on Discrete and Computational Geometry, Graphs, and Games, Tokyo, 2017.
  Invited talk, 5th International Combinatorics Conference, Melbourne, Australia, 2017.
  Invited talk, Southern California Theory Day, Irvine, California, 2018.
  Cambridge University Press, 2018.

  We survey problems on finite sets of points in the Euclidean plane that are monotone under removal of points and depend only on the order-type of the points, and the subsets of points (forbidden configurations) that prevent a point set from having a given monotone property.

  (CCCG talk slides – CCCG talk video – SCTD talk slides – Updates, errata, and reviews)

• Triangle-free penny graphs: degeneracy, choosability, and edge count.
  D. Eppstein.
  arXiv:1708.05152.
  Proc. 25th Int. Symp. Graph Drawing, Boston, Massachusetts, 2017.
  Springer, Lecture Notes in Comp. Sci. 10692 (2018), pp. 506–513.
  J. Graph Algorithms & Applications 22 (3): 483–499 (special issue for GD 2017), 2018.

  A penny graph is the contact graph of unit disks: each disk represents a vertex of the graph, no two disks can overlap, and each tangency between two disks represents an edge in the graph. We prove that, when this graph is triangle free, its degeneracy is at most two. As a consequence, triangle-free penny graphs have list chromatic number at most three. We also show that the number of edges in any such graph is at most 2n − Ω(√n). The journal version uses the alternative title "Edge Bounds and Degeneracy of Triangle-Free Penny Graphs and Squaregraphs".

  (Slides)

• The effect of planarization on width.
  D. Eppstein.
  arXiv:1708.05155.
  Proc. 25th Int. Symp. Graph Drawing, Boston, Massachusetts, 2017.
  Springer, Lecture Notes in Comp. Sci. 10692 (2018), pp. 560–572.
  J. Graph Algorithms & Applications 22 (3): 461–481 (special issue for GD 2017), 2018.

  We study what happens to nonplanar graphs of low width (for various width measures) when they are made planar by replacing crossings by vertices. For treewidth, pathwidth, branchwidth, clique-width, and tree-depth, this replacement can blow up the width from constant to linear. However, for bandwidth, cutwidth, and carving width, graphs of bounded width stay bounded when we planarize them.

  (Slides)

• Crossing patterns in nonplanar road networks.
  D. Eppstein and S. Gupta.
  arXiv:1709.06113.
  Proc. 25th ACM SIGSPATIAL Int. Conf. Advances in Geographic Information Systems (ACM SIGSPATIAL 2017), Redondo Beach, California, pp. 40:1–40:9.
  

  We show that, although an individual edge in a road network can have many crossings, real-world road networks have the property that the crossing graph of their edges is sparse. We prove that networks with this property are themselves sparse and have small separators, allowing many fast algorithms to be generalized from planar graphs to these networks.

• Square-contact representations of partial 2-trees and triconnected simply-nested graphs.
  G. Da Lozzo, W. E. Devanny, D. Eppstein, and T. Johnson.
  arXiv:1710.00426.
  Proc. 28th Int. Symp. Algorithms and Computation (ISAAC 2017), Phuket, Thailand, 2017.
  Leibniz International Proceedings in Informatics (LIPIcs) 92, pp. 24:1–24:16.
  

  We show that the K_1,1,3-free partial 2-trees and the Halin graphs other than K₄ can all be represented as proper contact graphs of squares in the plane. Among partial 2-trees and Halin graphs, these are exactly the ones that can be embedded without nonempty triangles, which form an obstacle to the existence of square contact representations. However the graph of a square antiprism has no such representation despite being embeddable without any nonempty triangles.