David Eppstein - Publications

2020

• Approximate greedy clustering and distance selection for graph metrics.
  D. Eppstein, S. Har-Peled, and A. Sidiropoulos.
  arXiv:1507.01555.
  J. Computational Geometry 11 (1): 629–652, 2020.

  We provide fast approximation algorithms for the farthest-first traversal of graph metrics.

• Treetopes and their graphs.
  D. Eppstein.
  arXiv:1510.03152.
  27th ACM-SIAM Symp. on Discrete Algorithms, Arlington, 2016, pp. 969–984.
  Discrete Comput. Geom. 64 (2), 259–289, 2020 (special issue for Branko Grünbaum).
  

  We describe a class of polytopes of varying dimensions, whose restriction to three dimensions is the class of roofless polyhedra (Halin graphs). We call these polytopes treetopes. We show that the four-dimensional treetopes are closely related to clustered planar graph drawings, and we use this connection to recognize the graphs of four-dimensional treetopes in polynomial time.

  (Slides)

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

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

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

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

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

• Counting polygon triangulations is hard.
  D. Eppstein.
  arXiv:1903.04737.
  Proc. 35th Int. Symp. on Computational Geometry, Portland, Oregon, June 2019.
  Leibniz International Proceedings in Informatics (LIPIcs) 129, 2019, pp. 33:1–33:17.
  Discrete Comput. Geom. 64 (4): 1210–1234, 2020 (special issue for SoCG 2019).

  Given a polygon with holes, it is #P-complete to determine how many triangulations it has.

  (UCLA seminar talk slides — SoCG slides)

• Some polycubes have no edge-unzipping.
  E. Demaine, M. Demaine, D. Eppstein, and J. O'Rourke.
  arXiv:1907.08433.
  Proc. 32nd Canadian Conference on Computational Geometry, 2020, pp. 101–105.
  Geombinatorics 31 (3): 101–109, 2022.
  

  We find polycubes that cannot be cut along a simple path through their vertices and edges and unfolded to form a flat polygon in the plane.

• Existence and hardness of conveyor belts.
  M. Baird, S. C. Billey, E. Demaine, M. Demaine, D. Eppstein, S. P. Fekete, G. Gordon, S. Griffin, J. S. B. Mitchell, and J. P. Swanson.
  arXiv:1908.07668.
  Electronic J. Combinatorics 27 (4), Paper P4.25, 2020.

  A conveyor belt is a tight simple closed curve that touches each of a given set of disjoint disks. We show that certain special families of disks always have a conveyor belt, but that it is NP-complete to tell whether one exists for arbitrary families of disks. It is always possible to add a linear number of "guide disks" to a given set of disks to allow them to be connected by a conveyor belt.

• Face flips in origami tessellations.
  H. A. Akitaya, V. Dujmović, D. Eppstein, T. Hull, K. Jain, and A. Lubiw.
  arXiv:1910.05667.
  J. Computational Geometry 11 (1): 397–417, 2020.

  We study problems in which we are given an origami crease pattern and seek to reconfigure one locally flat foldable mountain-valley assignment into another by a sequence of operations that change the assignment around a single face of the crease pattern.

• Simplifying activity-on-edge graphs.
  D. Eppstein, D. Frishberg, and E. Havvaei.
  arXiv:2002.01610.
  Proc. 17th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2020).
  Leibniz International Proceedings in Informatics (LIPIcs) 162, 2020, pp. 24:1–24:14.

  Given a partially ordered set of activities, we find in polynomial time a directed acyclic graph and a mapping from activities to its edges, such that the sequences of activities along paths in the graph are exactly the totally ordered subsets of activities in the input.

• Low-stretch spanning trees of graphs with bounded width.
  G. Borradaile, E. Chambers, D. Eppstein, W. Maxwell, and A. Nayyeri.
  arXiv:2004.08375.
  Proc. 17th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2020).
  Leibniz International Proceedings in Informatics (LIPIcs) 162, 2020, pp. 15:1–15:19.

  We describe a random distribution on the spanning trees of bounded-bandwidth graphs such that each edge has bounded expected stretch, along with several related results for other kinds of graph widths.

• On the treewidth of Hanoi graphs.
  D. Eppstein, D. Frishberg, and W. Maxwell.
  arXiv:2005.00179.
  Proc. 10th Int. Conf. Fun with Algorithms (FUN 2021).
  Leibniz International Proceedings in Informatics (LIPIcs) 157, 2020, pp. 13:1–13:21.
  Theor. Comput. Sci. 906: 1–17, 2022.

  The n-disc p-peg Hanoi graphs have treewidth within a polynomial factor of n^p − 1.

• On the edge crossings of the greedy spanner.
  D. Eppstein and H. Khodabandeh.
  arXiv:2002.05854.
  Proc. 37th International Symposium on Computational Geometry (SoCG 2021).
  Leibniz International Proceedings in Informatics (LIPIcs) 189, 2021, pp. 33:1–33:17.

  Greedy spanners are graphs formed from sets of geometric points by considering the pairs of points in sorted order by distance and adding an edge whenever a pair cannot be connected by a short path through the previously-added edges. We show that for points in the Euclidean plane, these graphs have linearly many crossings, that the intersection graph of their edges has bounded degeneracy, and that they have separators of square-root size.

• Dynamic products of ranks.
  D. Eppstein.
  arXiv:2007.08123.
  Proc. 32nd Canadian Conference on Computational Geometry, 2020, pp. 199–205.

  We provide data structures for the following problem: maintain a collection of points in the Euclidean plane, subject to insertions or deletions, and after each update find the point whose product of ranks according to the two sorted orders of the points by x- and y-coordinates is as small or as large as possible.

• Acutely triangulated, stacked, and very ununfoldable polyhedra.
  E. Demaine, M. Demaine, and D. Eppstein.
  arXiv:2007.14525.
  Proc. 32nd Canadian Conference on Computational Geometry, 2020, pp. 106–113.

  We construct non-convex but topologically spherical polyhedra in which all faces are acute triangles, with no unfolded net.

• New results in sona drawing: hardness and TSP separation.
  M.-W. Chiu, E. Demaine, M. Demaine, D. Eppstein, R. Hearn, A. Hesterberg, M. Korman, I. Parada, and M. Rudoy.
  arXiv:2007.15784.
  Proc. 32nd Canadian Conference on Computational Geometry, 2020, pp. 63–72.

  A sona drawing is a self-crossing curve in the plane that separates each of a given system of points into its own region. We show that it is hard to find the shortest such curve, and we explore how much shorter than the TSP it can be.

• On polyhedral realization with isosceles triangles.
  D. Eppstein.
  arXiv:2009.00116.
  Graphs and Combinatorics 37 (4): 1247–1269, 2021.
  

  We find convex polyhedra with all faces triangular that cannot be realized with all faces isosceles, and new families of convex polyhedra with congruent isosceles-triangle faces.

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

• Stack-number is not bounded by queue-number.
  V. Dujmović, D. Eppstein, R. Robert Hickingbotham, P. Morin, and D. R. Wood.
  arXiv:2011.04195.
  Combinatorica 42: 151–164, 2022.

  Stack number is also known as page number or book thickness; it is the minimum number of stacks needed so that you can process the vertices of a graph in some sequence, pushing each edge onto one of the stacks when you process its first endpoint and popping it from the same stack when you process its second endpoint. Queue number is defined in the same way using queues instead of stacks. We show that the strong products of triangular grids and high-degree stars have bounded queue number but unbounded stack number. This result disproves the Blankenship–Oporowski conjecture, according to which subdividing edges of a graph a constant number of times cannot decrease its stack number from non-constant to constant, because subdivisions of the same products also have bounded stack number. It also confirms a conjecture of Bonnet et al on the existence of graphs with bounded sparse twin-width and unbounded stack number.