2023
- Geometric dominating sets – A minimum version of the
no-three-in-line problem.
O. Aichholzer, D. Eppstein, and E.-M. Hainzl.
37th European Workshop on Computational Geometry (EuroCG 2021), pp. 17:1–17:7.
arXiv:2203.13170.
Comp. Geom. Theory & Applications 108: 101913, 2023 (special issue for EuroCG).
We study how few points can be placed in a grid so that all remaining grid points are collinear with two of the placed points.
- A stronger lower bound on parametric minimum spanning trees.
D. Eppstein.
arXiv:2105.05371.
17th Algorithms and Data Structures Symp. (WADS 2021).
Springer, Lecture Notes in Comp. Sci. 12808 (2021), pp. 343–356.
Algorithmica 85: 1738–1753, 2023 (special issue for WADS 2021).
There exist graphs with edges labeled by linear real functions, such that the number of different minimum spanning trees obtained for different choices of the function argument is \(\Omega(m\log n)\).
(Slides)
- Angles of arc-polygons and Lombardi drawings of cacti.
D. Eppstein, D. Frishberg, and M. Osegueda.
arXiv:2107.03615.
Proc. 33rd Canadian Conference on Computational Geometry, 2021, pp. 56–64.
Comp. Geom. Theory & Applications 112: 101982, 2023 (special issue for CCCG 2021).
We precisely characterize the triples vertex angles that are possible for arc-triangles (curved triangles made from circular arcs), and prove an existence theorem for a large class of sets of angles for arc-polygons. Our characterization allows us to prove that every cactus graph has a planar Lombardi drawing for its natural planar embedding (the embedding in which each cycle is a bounded face), but that there exist other embeddings of cacti that have no Lombardi drawing.
- Multifold tiles of polyominoes and convex lattice polygons.
K. Chida, E. Demaine, M. Demaine, D. Eppstein, A. Hesterberg, T. Horiyama, J. Iacono, H. Ito, S. Langerman, R. Uehara, and Y. Uno.
23rd Thailand-Japan Conference on Discrete and Computational Geometry, Graphs, and Games, 2021, pp. 28–29.
Thai Journal of Mathematics 21 (4): 957–978, 2023.We investigate shapes whose congruent copies can cover the plane exactly \(k\) times per point, but not a number of times that is a nonzero integer smaller than \(k\). We find polyominoes with this property for all \(k\ge 2\), and convex integer-coordinate polygons with this property for \(k=5\) and for all \(k\ge 7\).
- Rapid mixing of the hardcore Glauber dynamics and other Markov chains in bounded-treewidth graphs.
D. Eppstein and D. Frishberg.
arXiv:2111.03898.
Proc 34th International Symposium on Algorithms and Computation (ISAAC 2023).
Leibniz International Proceedings in Informatics (LIPIcs) 283, 2022, pp. 30:1–30:13.A random walk on the independent sets or dominating sets of a graph mixes rapidly for graphs of bounded treewidth, and a random walk on maximal independent sets mixes rapidly for graphs of bounded carving width.
- The complexity of iterated reversible computation.
D. Eppstein.
arXiv:2112.11607.
Invited talk at 15th Latin American Theoretical Informatics Symposium, Guanajuato, Mexico, November 2022.
TheoretiCS 2: A10:1–A10:41, 2023.
We study a class of problems involving computing a value \(f^{(n)}(x)\), the \(n\)th iterate of a function \(f\), for polynomial time bijections. We prove that these problems are complete for \(\mathsf{P}^{\mathsf{PSPACE}}\), and include hard problems in circuit complexity, graph algorithms, the simulation of one- and two-dimensional automata, and dynamical systems. We also provide a polynomial time algorithm for the special case where the bijection is an interval exchange transformation.
- Locked and unlocked smooth embeddings of surfaces.
D. Eppstein.
arXiv:2206.12989.
34th Canadian Conference on Computational Geometry, 2022, pp. 135–142.
Computing in Geometry and Topology 2 (2): 5.1–5.20, 2023.If a subset of the plane has a continuous shrinking motion of itself, then every smooth isometric embedding of that subset into 3d can be smoothly flattened. However, there exist subsets of the plane with holes, for which some smooth embeddings that are topologically equivalent to a flat embedding cannot be smoothly flattened.
(Slides)
- Improved mixing for the convex polygon triangulation flip walk.
D. Eppstein and D. Frishberg.
arXiv:2207.09972.
Proc. 50th EATCS International Colloquium on Automata, Languages, and Programming (ICALP 2023).
Leibniz International Proceedings in Informatics (LIPIcs) 261, 2023, pp. 56:1–56:17.
The associahedron is a polytope whose vertices represent the triangulations of a convex polygon, and whose edges represent flips connecting one triangulation to another. We show that a random walk on the edges of this polytope rapidly converges to the uniform distribution on triangulations. However, we also show that the associahedron does not have constant expansion.
- Non-crossing Hamiltonian paths and cycles in output-polynomial time.
D. Eppstein.
arXiv:2303.00147.
Proc. 39th International Symposium on Computational Geometry (SoCG 2023).
Leibniz International Proceedings in Informatics (LIPIcs) 258, 2023, pp. 29:1–29:16.
Algorithmica 86: 3027–3053, 2024.For any point set, the numbers of non-crossing paths, non-crossing Hamiltonian paths, non-crossing surrounding polygons, and non-crossing Hamiltonian cycles can be bounded above and below by functions of two simple parameters: the minimum number of points whose deletion leaves a collinear subset, and the number of points interior to the convex hull. Because their bounds have the same form, the numbers of the two types of paths are bounded by polynomials of each other, as are the numbers of the two types of polygons. We use these relations to list non-crossing Hamiltonian paths and polygonalizations in time polynomial in the number of outputs.
- 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.
- Lower bounds for non-adaptive shortest path relaxation.
D. Eppstein.
arXiv:2305.09230.
Proc. 18th Algorithms and Data Structures Symposium (WADS 2023).
Springer, Lecture Notes in Computer Science 13079 (2023), pp. 416–429.The Bellman–Ford algorithm for single-source shortest paths operates by relaxation steps, in which it checks for a given edge whether the best path it knows to the start of the edge, plus the edge itself, is better than the path it already knows to the end of the edge. We prove that, up to constant factors, Bellman–Ford is optimal among algorithms that use relaxation in an edge ordering that does not depend on the results of earlier relaxation steps.
- Widths of geometric graphs.
D. Eppstein.
Invited talk, Workshop on Parameterized Algorithms for Geometric Problems, CG Week 2023.
Many computational geometry problems can be solved by transforming them into a graph problem on a geometric graph. When the graph has low width, for some form of graph width, this can often lead to efficient classical or parameterized algorithms. We survey the geometric graphs that always have low width, the geometric graphs that can have high width, and the opportunities for parameterization obtained by studying low-width instances of graphs that sometimes have high width.
- A parameterized algorithm for flat folding.
D. Eppstein.
arXiv:2306.11939.
Proc. 35th Canadian Conference on Computational Geometry, 2023, pp. 35–42.
Testing whether an origami folding pattern can be folded flat is fixed-parameter tractable when parameterized by two parameters: the ply (maximum number of layers) of the folding, and the treewidth of a planar graph describing the arrangement of polygons in the flat-folded result. The dependence on treewidth is optimal under the exponential-time hypothesis.
Merged into "Computational complexities of folding" for journal submission.
- Geometric graphs with unbounded flip-width.
D. Eppstein and R. McCarty.
arXiv:2306.12611.
Proc. 35th Canadian Conference on Computational Geometry, 2023, pp. 197–208.We show that many constructions for dense geometric graphs produce graphs of unbounded flip-width, frustrating the search for natural classes of graphs that have bounded flip-width but unbounded twin-width.
- Quasipolynomiality of the smallest missing induced subgraph.
D. Eppstein, A. Lincoln, and V. V. Williams.
arXiv:2306.11185.
J. Graph Algorithms & Applications 27 (5): 329–339, 2023.The smallest graph that is not an induced subgraph of a given graph can be found in time \(n^{O(\log n)}\). The exponent is optimal, up to constant factors, under the exponential time hypothesis.
- Manipulating weights to improve stress-graph drawings of 3-connected planar graphs.
A. Chiu, D. Eppstein, and M. T. Goodrich.
arXiv:2307.10527.
Proc. 31st Int. Symp. Graph Drawing and Network Visualization, Palermo, Italy, 2023.
Springer, Lecture Notes in Computer Science 14466 (part II), pp. 141–149.In Tutte spring embeddings for planar graphs, it is possible to adjust the strengths of the springs and the fixed positions of the vertices on the outer face to obtain an infinite continuous family of straight-line planar embeddings. We experiment with making those adjustments to spread out the features of the drawing to better positions than they would have in the unweighted case.
- The widths of strict outerconfluent graphs.
D. Eppstein.
arXiv:2308.03967.
Proc. 31st Int. Symp. Graph Drawing and Network Visualization, Palermo, Italy, 2023 (poster session).
Springer, Lecture Notes in Computer Science 14466 (part II), pp. 244–247.
Discrete Mathematics & Theoretical Computer Science 26 (3) 20:1–20:17, 2024.We construct a family of strict outerconfluent graphs with unbounded clique-width. In contrast, we use a counting argument to prove that strict outerconfluent graphs have bounded twin-width.
- Uniqueness in puzzles and puzzle solving.
D. Eppstein.
Minisymposium on Mathematical Puzzles and Games in Theoretical Computer Science, ICIAM, Waseda Univ., Tokyo, Japan, 2023.
In puzzles such as Sudoku, one can often make use of an assumption that the solution is unique, in deduction rules that eliminate alternatives that would lead to a non-unique solution. However, these rules can lack the monotonicity properties of other deduction rules, under which a conclusion that can be deduced from some partially-solved state of the puzzle remains available to be deduced until it actually is deduced. I discuss a method of obtaining monotonic deductions in a planar precoloring extension puzzle, and ask whether there is some more general method for obtaining monotonicity in this way.