David Eppstein - Publications

2018

• Planar and poly-arc Lombardi drawings.
  C. Duncan, D. Eppstein, M. T. Goodrich, S. Kobourov, and M. Löffler, and M. Nöllenburg.
  Proc. 19th Int. Symp. Graph Drawing, Eindhoven, The Netherlands, 2011.
  Springer, Lecture Notes in Comp. Sci. 7034, 2012, pp. 308–319.
  arXiv:1109.0345.
  J. Computational Geometry 9 (1): 328–355, 2018.

  We extend Lombardi drawing (in which each edge is a circular arc and the edges incident to a vertex must be equally spaced around it) to drawings in which edges are composed of multiple arcs, and we investigate the graphs that can be drawn in this more relaxed framework.

• Parameterized complexity of 1-planarity.
  M. J. Bannister, S. Cabello, and D. Eppstein.
  arXiv:1304.5591.
  13th Int. Symp. Algorithms and Data Structures (WADS 2013), London, Ontario
  Springer, Lecture Notes in Comp. Sci. 8037, 2013, pp. 97–108.
  J. Graph Algorithms and Applications 22 (1): 23–49, 2018. (Special issue on Graph Drawing Beyond Planarity.)
  

  We show that testing whether a graph is 1-planar (drawable with at most one crossing per edge) may be performed in polynomial and fixed-parameter tractable time for graphs of bounded circuit rank, vertex cover number, or tree-depth. However, it is NP-complete for graphs of bounded treewidth, pathwidth, or bandwidth.

  (Slides)

• Crossing minimization for 1-page and 2-page drawings of graphs with bounded treewidth.
  M. J. Bannister and D. Eppstein.
  arXiv:1408.6321.
  22nd Int. Symp. Graph Drawing, Würzburg, Germany, 2014.
  Springer, Lecture Notes in Comp. Sci. 8871, 2014, pp. 210–221.
  J. Graph Algorithms & Applications 22 (4): 577–606, 2018.

  We show how to express in monadic second-order logic the problems of drawing a graph with a fixed number of crossings on a one or two page book layout. By applying Courcelle's theorem, we obtain fixed-parameter tractable algorithms for these problems, parameterized by treewidth.

• Flat foldings of plane graphs with prescribed angles and edge lengths.
  Z. Abel, E. Demaine, M. Demaine, D. Eppstein, A. Lubiw, and R. Uehara.
  arXiv:1408.6771.
  22nd Int. Symp. Graph Drawing, Würzburg, Germany, 2014.
  Springer, Lecture Notes in Comp. Sci. 8871, 2014, pp. 272–283.
  J. Computational Geometry 9 (1): 74–93, 2018.

  Given a plane graph with fixed edge lengths, and an assignment of the angles 0, 180, and 360 to the angles between adjacent edges, we show how to test whether the angle assignment can be realized by an embedding of the graph as a flat folding on a line. As a consequence, we can determine whether two-dimensional cell complexes with one vertex can be flattened. The main idea behind the result is to show that each face of the graph can be folded independently of the other faces.

• The parametric closure problem.
  D. Eppstein.
  arXiv:1504.04073.
  14th Algorithms and Data Structures Symp. (WADS 2015), Victoria, BC.
  Springer, Lecture Notes in Comp. Sci. 9214 (2015), pp. 327–338.
  ACM Trans. Algorithms 14 (1): Article 2, 2018.

  We consider the minimum weight closure problem for a partially ordered set whose elements have weights that vary linearly as a function of a parameter. For several important classes of partial orders the number of changes to the optimal solution as the parameter varies is near-linear, and the sequence of optimal solutions can be found in near-linear time.

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

• On the planar split thickness of graphs.
  D. Eppstein, P. Kindermann, S. G. Kobourov, G. Liotta, A. Lubiw, A. Maignan, D. Mondal, H. Vosoughpour, S. Whitesides, and S. Wismath.
  arXiv:1512.04839.
  Proc. 12th Latin American Theoretical Informatics Symposium (LATIN 2016), Ensenada, Mexico.
  Springer, Lecture Notes in Comp. Sci. 9644 (2016), pp. 403–415.
  Algorithmica 80 (3): 977–994 (special issue for LATIN), 2018.

  We study the problem of splitting the vertices of a given graph into a bounded number of sub-vertices (with each edge attaching to one of the sub-vertices) in order to make the resulting graph planar. It is NP-complete, but can be approximated to within a constant factor, and is fixed-parameter tractable in the treewidth.

  (Slides)

• From discrepancy to majority.
  D. Eppstein and D. S. Hirschberg.
  arXiv:1512.06488.
  Proc. 12th Latin American Theoretical Informatics Symposium (LATIN 2016), Ensenada, Mexico.
  Springer, Lecture Notes in Comp. Sci. 9644 (2016), pp. 390–402.
  Algorithmica 80 (4): 1278–1297, 2018.

  We provide upper and lower bounds on the query complexity of a problem in which the input is a collection of two-colored items, and the problem is to either find an item of the majority color or to determine that there is no majority, by performing queries that determine the discrepancy of fixed-size subsets of the items.

  (Slides)

• Spanning trees in multipartite geometric graphs.
  A. Biniaz, P. Bose, D. Eppstein, A. Maheshwari, P. Morin, and M. Smid.
  arXiv:1611.01661.
  Algorithmica 80 (11): 3177–3191, 2018.

  We provide near-linear-time algorithms for minimum and maximum spanning trees 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.

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

• Quadratic time algorithms appear to be optimal for sorting evolving data.
  J. Besa, W. E. Devanny, D. Eppstein, M. T. Goodrich, and T. Johnson.
  Proc. Algorithm Engineering & Experiments (ALENEX 2018), New Orleans, 2018, pp. 87–96.
  arXiv:1805.05443.

  We experiment with sorting algorithms in the evolving data model, in which, at the same time as the algorithm compares pairs of elements and possibly chooses a new ordering based on the results of the comparison, an adversary randomly chooses two adjacent elements in the sorted order and swaps them. As we show, bubble sort and its variants appear to maintain an order that is within inversion distance of optimal.

• Grid peeling and the affine curve-shortening flow.
  D. Eppstein, S. Har-Peled, and G. Nivasch.
  arXiv:1710.03960.
  Proc. Algorithm Engineering & Experiments (ALENEX 2018), New Orleans, 2018, pp. 109–116.
  Experimental Mathematics 29 (3): 306–316, 2020.

  We conjecture, based on experiments, that approximating a convex shape by the set of grid points inside it, for a fine enough grid, and then finding the convex layers of the resulting point set, produces curves that are close to those produced by affine curve-shortening, a continuous process on smooth curves.

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

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

• Subexponential-time and FPT algorithms for embedded flat clustered planarity.
  G. Da Lozzo, D. Eppstein, M. T. Goodrich, and S. Gupta.
  arXiv:1803.05465
  Proc. 44th International Workshop on Graph-Theoretic Concepts in Computer Science (WG 2018), Lübbenau, Germany.
  Springer, Lecture Notes in Comp. Sci. 11159 (2018), pp. 111–124.

  Clustered planarity is the problem of simultaneously drawing a planar graph and a clustering of its vertices (as Jordan curves surrounding the cluster) with no unnecessary crossings between edges or cluster boundaries; it remains unknown whether it can be solved in polynomial time. We provide parameterized and subexponential exact algorithms for the case where the planar embedding is fixed and the clusters form a partition of the vertices.

• Faster evaluation of subtraction games.
  D. Eppstein.
  arXiv:1804.06515.
  Proc. 9th Int. Conf. Fun with Algorithms (FUN 2018), La Maddalena, Italy.
  Leibniz International Proceedings in Informatics (LIPIcs) 100, pp. 20:1–20:12.
  

  We show how to evaluate the set of winning heap sizes in subtraction games like subtract-a-square in near-linear time, and how to compute the nim-values more quickly than naive dynamic programming. Additionally we perform computational experiments showing that the set of winning positions forms an unexpectedly dense square-difference-free set.

  (Slides)

• Making change in 2048.
  D. Eppstein.
  arXiv:1804.07396.
  Proc. 9th Int. Conf. Fun with Algorithms (FUN 2018), La Maddalena, Italy.
  Leibniz International Proceedings in Informatics (LIPIcs) 100, pp. 21:1–21:13.
  

  The 2048 puzzle, modified to use any sequence of integer tile values that has arbitrarily large gaps, always terminates. The proof relates the puzzle to the greedy algorithm for making change (suboptimally) using a given system of coins.

  (Slides)

• Stable-matching Voronoi diagrams: combinatorial complexity and algorithms.
  G. Barequet, D. Eppstein, M. T. Goodrich, and N. Mamano.
  arXiv:1804.09411
  Proc. 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018), Prague.
  Leibniz International Proceedings in Informatics (LIPIcs) 107, pp. 89:1–89:14.
  J. Computational Geometry 11 (1): 26–59, 2020.

  The stable-matching Voronoi diagram of a collection of point sites in the plane, each with a specified area, is a collection of disjoint regions of the plane, one for each site and having the specified area, so that no pair of a point and a site are closer to each other than to the farthest other site and point that they may be matched to. We prove nearly-matching upper and lower bounds on the combinatorial complexity of these diagrams and provide algorithms that can compute them in a polynomial number of primitive steps.

• Optimally sorting evolving data.
  J. Besa, W. E. Devanny, D. Eppstein, M. T. Goodrich, and T. Johnson.
  arXiv:1805.03350
  Proc. 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018), Prague.
  Leibniz International Proceedings in Informatics (LIPIcs) 107, pp. 81:1–81:13.
  

  Suppose that a collection of objects has a linear order that is evolving by swaps of randomly chosen consecutive elements. We would like to maintain an approximation to this order using an algorithm that performs one comparison per swap. We show that repeated insertion sort can maintain linear inversion distance from the underlying order, the best possible.

• Reconfiguration of satisfying assignments and subset sums: Easy to find, hard to connect.
  J. Cardinal, E. Demaine, D. Eppstein, R. Hearn, and A. Winslow.
  arXiv:1805.04055
  Proc. 24th International Computing and Combinatorics Conference (COCOON 2018), Qingdao, China.
  Springer, Lecture Notes in Comp. Sci. 10976 (2018), pp. 365–377.
  Theor. Comput. Sci. 806: 332–343, 2020.

  For several problems with polynomial-time solutions, we show that finding a sequence of steps that converts one solution into another (maintaining a valid solution at each step) is hard. These include planar monotone not-all-equal 3-sat, subset sum on integers of polynomial magnitude, and 0-1 integer programming with a constant number of linear inequality constraints.

  (Slides)

• Geometric fingerprint matching via oriented point-set pattern matching.
  D. Eppstein, M. T. Goodrich, J. Jorgensen, and M. Torres.
  arXiv:1808.00561
  Proc. 30th Canadian Conference on Computational Geometry, Winnepeg, Canada, 2018, pp. 98–113.
  

  When matching fingerprints, the data involves planar points each of which has an associated direction. Motivated by this application, we consider point matching problems in which the distance between points combines both their translational distance and the rotation needed to make their directions align. We provide fast and simple approximation schemes for matching oriented point sets under the directed Hausdorff distance with different allowed groups of transformations.

• Which women mathematicians get written about on Wikipedia, and why.
  D. Eppstein.
  AWM Newsletter 48 (4): 12–14, July–August 2018.

  This short opinion piece explains Wikipedia's guidelines for inclusion of articles on academics, and outlines steps to help improve Wikipedia's coverage of women in mathematics.

• Parameterized leaf power recognition via embedding into graph products.
  D. Eppstein and E. Havvaei.
  arXiv:1810.02452.
  Proc. 13th International Symposium on Parameterized and Exact Computation (IPEC 2018), Helsinki, Finland, 2018.
  Leibniz International Proceedings in Informatics (LIPIcs) 115, 2018, pp. 16:1–16:14.
  Algorithmica 82 (8): 2337–2359, 2020 (special issue for IPEC 2018).

  A leaf power graph is the graph formed from the leaves of a tree by making two leaves adjacent when their tree distance is at most k. We show that recognizing these graphs is fixed-parameter tractable in a combination of two parameters: k and the degeneracy of the graph.

  (James Nastos has pointed out a minor error in our statement of known prior results: the figure depicting chordal graphs that are not 4-leaf powers is labeled as a complete set of forbidden subgraphs, but it is only the complete set among graphs without true twin vertices.)

• The parameterized complexity of finding point sets with hereditary properties.
  D. Eppstein and D. Lokshtanov.
  arXiv:1808.02162
  Proc. 13th International Symposium on Parameterized and Exact Computation (IPEC 2018), Helsinki, Finland, 2018.
  Leibniz International Proceedings in Informatics (LIPIcs) 115, 2018, pp. 11:1–11:14.

  We exhibit a hereditary property of planar point sets (depending only on the order type of a point set) such that under standard assumptions there is no fixed-parameter-tractable algorithm to find a k-point subset with the property. On the other hand, several natural classes of properties have FPT algorithms for this problem, including the properties that are true for all collinear point sets or false for at least one convex polygon.

  (Slides)

• Realization and connectivity of the graphs of origami flat foldings.
  D. Eppstein.
  arXiv:1808.06013.
  Proc. 26th Int. Symp. Graph Drawing, Barcelona, 2018.
  Springer, Lecture Notes in Comp. Sci. 11282 (2018), pp. 541–554.
  J. Computational Geometry 10 (1): 257–280, 2019.

  If you fold a piece of paper flat and unfold it again, the resulting crease pattern forms a planar graph. We prove that a tree can be realized in this way (with its leaves as diverging rays that reach the boundary of the paper) if and only if all internal vertices have odd degree greater than two. On the other hand, for a folding pattern on an infinite sheet of paper with an added vertex at infinity as the endpoint of all its rays, the resulting graph must be 2-vertex-connected and 4-edge-connected.

  (Slides)

• Stable-matching Voronoi diagrams.
  D. Eppstein.
  Invited talk at 21st Japan Conference on Discrete and Computational Geometry, Graphs, and Games (JCDCG³), Manila, Philippines, 2018.
  

  We survey the results from several of my earlier papers: Algorithms for stable matching and clustering in a grid, Defining equitable geographic districts in road networks via stable matching, Reactive proximity data structures for graphs, and Stable-matching Voronoi diagrams: combinatorial complexity and algorithms.

  (Slides)

• Finding maximal sets of laminar 3-separators in planar graphs in linear time.
  D. Eppstein and B. Reed.
  arXiv:1810.07825.
  30th ACM-SIAM Symp. on Discrete Algorithms, San Diego, 2019, pp. 589–605.
  

  Given a 3-vertex-connected planar graph, we find a hierarchical decomposition of the graph by 3-vertex separators, such that each piece of the decomposition is 4-vertex-connected, in linear time. The result has applications to an algorithm of Kawarabayashi, Li, and Reed for finding disjoint paths in nonplanar graphs.

  (Slides)

• Minor-closed graph classes with bounded layered pathwidth.
  V. Dujmović, D. Eppstein, G. Joret, P. Morin, and D. R. Wood.
  arXiv:1810.08314.
  SIAM J. Discrete Math 34 (3): 1693–1709, 2020.

  A minor-closed graph family has a functional relation between diameter and path width (bounded local pathwidth) if and only if it excludes an apex-tree. The same graph families are also the ones with bounded layered pathwidth: a simultaneous path decomposition and layering (sequence of subsets of vertices with all edges connecting the same subset or consecutive subsets) so that the intersection of a bag and a layer has constant size.