David Eppstein - Publications

2025

• Orthogonal dissection into few rectangles.
  D. Eppstein.
  arXiv:2206.10675.
  34th Canadian Conference on Computational Geometry, 2022, pp. 143–150.
  Discrete Comput. Geom. 73 (1): 129–148, 2025.
  

  The rank of the Dehn invariant of an orthogonal polygon equals the minimum number of rectangles into which it can be transformed by axis-parallel cuts, translation, and gluing. This allows the minimum number of rectangles to be calculated in polynomial time.

  (Slides)

• On the complexity of embedding in graph products.
  T. Biedl, D. Eppstein, and T. Ueckerdt.
  arXiv:2303.17028.
  Proc. 35th Canadian Conference on Computational Geometry, 2023, pp. 77–88.
  Computing in Geometry and Topology 4 (2): 5:1–5:18, 2025.

  Row treewidth (embedding a graph as a subgraph of a strong product of a path with a low treewidth graph), row pathwidth, and row tree-depth are all NP-hard.

• Non-Euclidean Erdős–Anning theorems.
  D. Eppstein.
  arXiv:2401.06328.
  41st International Symposium on Computational Geometry (SoCG 2025), Kanazawa, Japan.
  Leibniz International Proceedings in Informatics (LIPIcs) 332, 2025, pp. 46:1–46:15.
  

  Non-collinear point sets with integer distances must be finite, for strictly convex distance functions on the plane, for two-dimensional complete Riemannian manifolds of bounded genus, and for geodesic distance on convex surfaces in 3d.

  (SoCG talk slides)

• What is ... treewidth?.
  D. Eppstein.
  Notices of the American Mathematical Society 72 (2): 172–175, 2025.

  We survey graph treewidth at a high level. The focus is on applications of treewidth to various areas of mathematics.

• Computational complexities of folding.
  D. Eppstein.
  Invited talk, 8th International Meeting on Origami in Science, Mathematics and Education, Melbourne, Australia, 2024.
  Invited talk, 26th Japan Conference on Discrete and Computational Geometry, Graphs, and Games, Tokyo, 2024.
  arXiv:2410.07666.
  Journal of Information Processing 33: 954–973, 2025.

  We survey known hardness results on folding origami and prove several new ones: finding a flat-folded state is \(\mathsf{NP}\)-hard, but fixed-parameter tractable in a combination of ply and the treewidth of an associated graph. Finding a 3d-folded state cannot be expressed in closed form and cannot be computed by bounded-degree algebraic-root primitives. Reconfiguring certain systems of overlapping origami squares, hinged to a table at one edge, is \(\mathsf{PSPACE}\)-complete, and counting the number of configurations is \(\#\mathsf{P}\)-complete. Testing flat-foldability of infinite fractal folding patterns (even on normal square origami paper) is undecidable.

• Noncrossing longest paths and cycles.
  G. Aloupis, A. Biniaz, P. Bose, J.-L. De Carufel, D. Eppstein, A. Maheshwari, S. Odak, M. Smid, C. Tóth, and P. Valtr.
  32nd International Symposium on Graph Drawing and Network Visualization.
  Leibniz International Proceedings in Informatics (LIPIcs) 320, 2024, pp. 36:1–36:17.
  arXiv:2410.05580.
  Graphs and Combinatorics 41, article 122 (25pp), 2025.

  The shortest path or cycle through given planar points (the solution to the traveling salesperson problem) never crosses itself: any crossing can be eliminated by a local move that shortens the tour. One might think that, correspondingly, the longest path or cycle through enough planar points always crosses itself. We show that this is not the case: there exist arbitrarily large point sets for which the longest path or cycle has no crossing.

• Princ-wiki-a mathematica: Wikipedia editing and mathematics.
  D. Eppstein, J. B. Lewis, R. Woodroofe, and X. Easter.
  arXiv:2412.20419.
  Notices of the AMS 72 (1): 65–73, 2025.
  

  We describe the experience of editing mathematics articles on Wikipedia, with the aim of providing helpful advice for new editors and encouraging mathematicians to become Wikipedia editors.

• Computational geometry with probabilistically noisy primitive operations.
  D. Eppstein, M. T. Goodrich, and V. Sridhar.
  arXiv:2501.07707.
  Proc. 19th Algorithms and Data Structures Symposium (WADS 2025).
  Leibniz International Proceedings in Informatics (LIPIcs) 349, 2025, pp. 24:1–24:20.
  

  An algorithm that uses Boolean primitive operations, like comparisons, that may be erroneous with some small independent probability per call, may be made to run correctly with high probability by repeating each primitive enough times to be sure its majority result is correct, but this incurs a logarithmic time penalty. Prior work avoids this penalty for sorting; we extend this speedup to algorithms in computational geometry that can be formulated using path search in DAGs. Applications of our "path-guided pushdown random walk" technique include point location, plane sweep, convex hulls, and Delaunay triangulation.

• Zip-tries: simple dynamic data structures for strings.
  D. Eppstein, O. Gila, M. T. Goodrich, and R. Kitagawa.
  SIAM Conference on Applied and Computational Discrete Algorithms (ACDA25), Montreal, Canada, 2025, pp. 130–143.
  arXiv:2505.04953.
  

  We provide fast parallel and bit-parallel data structures for string search in a dynamic set of strings, with few bits of metadata per node.

• Better late than never: the complexity of arrangements of polyhedra.
  B. Aronov, S. W. Bae, O. Cheong, D. Eppstein, C. Knauer, and R. Seidel.
  41st European Workshop on Computational Geometry (EuroCG 2025), Liblice, Czech Republic, pp. 62:1–62:4.
  arXiv:2506.03960.
  

  My 1994 paper "On the number of minimal 1-Steiner trees" with Aronov and Bern, in some preliminary manuscript versions, included a bound of \(O(m^{\lceil d/2\rceil}n^{\lfloor d/2\rfloor})\) on the complexity of an arrangement of \(m\) convex polytopes given as intersections of a total of \(n\) halfspaces, interpolating between the upper bound theorem for polytopes and the complexity of hyperplane arrangements. However, the manuscript and the proof were lost. This paper re-proves the result, with better care for the degenerate cases.

• Bandwidth vs BFS width in matrix reordering, graph reconstruction, and graph drawing.
  D. Eppstein, M. T. Goodrich, and S. Liu.
  arXiv:2505.10789.
  Proc. 33rd Annual European Symposium on Algorithms (ESA 2025).
  Leibniz International Proceedings in Informatics (LIPIcs) 351, 2025, pp. 69:1–69:17.
  

  In graphs of bounded bandwidth, the number of vertices per level of a breadth-first search tree is at most polylogarithmic, with the exponent of the polylogarithm both upper and lower bounded by functions of the bandwidth. This has applications to the Cuthull-McKee heuristic and reverse Cuthull-McKee heuristic in sparse numerical algebra, to reconstructing an unknown graph by shortest distance queries, and to drawing graphs as arc diagrams of small height.

• Decremental greedy polygons and polyhedra without sharp angles.
  D. Eppstein.
  arXiv:2507.04538.
  Proc. 37th Canadian Conference on Computational Geometry, 2025, pp. 85–91.
  

  For given elements and a quality function of an element in a subset, monotonically non-increasing with respect to removals of other elements, we can find the max-min-quality subset by a decremental greedy algorithm that repeatedly removes low-quality subsets. We apply this method to find the max-min-angle polygon for points in the plane, the max-min-weight cycle in a directed graph, and several generalizations of both problems.

• Entropy-bounded computational geometry made easier and sensitive to sortedness.
  D. Eppstein, M. T. Goodrich, A. M. Illickan, and C. A. To.
  arXiv:2508.20489.
  Proc. 37th Canadian Conference on Computational Geometry, 2025, pp. 53–61.
  

  We define a notion of structural entropy of point sets under which a set has low entropy when it can be covered by few disjoint triangles that are either entirely under the hull of the input or presorted, and show that we can find the hull in time sensitive to this entropy. Generalizations of the same technique apply to geometric maxima, lower envelopes, and visibility polygons.

• Stabbing faces by a convex curve.
  D. Eppstein.
  arXiv:2508.17549.
  33rd International Symposium on Graph Drawing and Network Visualization.
  Leibniz International Proceedings in Informatics (LIPIcs) 357, 2025, pp. 29:1–29:8.
  

  For each smooth convex curve \(C\), and each planar graph \(G\), there exists a straight-line drawing of \(G\) all of whose faces are crossed by \(C\). This result serves as a counterexample to an argument that universal point sets for planar graph drawing cannot be covered by few convex polygons.

  (Slides)

• String graph obstacles of high girth and of bounded degree.
  M. Chudnovsky, D. Eppstein, and D. Fischer.
  arXiv:2509.00278.
  33rd International Symposium on Graph Drawing and Network Visualization.
  Leibniz International Proceedings in Informatics (LIPIcs) 357, 2025, pp. 24:1–24:18.
  
• Visualizing treewidth.
  A. Chiu, T. Depian, D. Eppstein, M. T. Goodrich, and M. Nöllenburg.
  arXiv:2508.19935.
  33rd International Symposium on Graph Drawing and Network Visualization.
  Leibniz International Proceedings in Informatics (LIPIcs) 357, 2025, pp. 17:1–17:20.
  
• Bicriteria polygon aggregation with arbitrary shapes.
  L. Blank, D. Eppstein, J.-H. Haunert, H. Haverkort, B. Kolbe, P. Mayer, P. Mutzel, A. Naumann, and J. Sauer.
  arXiv:2507.11212.
  
• Hamiltonian cycles in subdivided doubles.
  D. Eppstein.
  arXiv:2510.18359.
  Ars Mathematica Contemporanea, to appear.
  

  The subdivided double construction turns a 4-regular graph into a bigger 4-regular graph, by subdividing each edge and doubling each vertex. We prove that the resulting graphs, which include the Folkman graph, have the following curious property: every Hamiltonian cycle (of which there are exponentially many) is complementary to another Hamiltonian cycle.