David Eppstein – Publications

Publications with Daniel Frishberg

• Applications of nearest-neighbor chains: Euclidean TSP and motorcycle graphs.
  N. Mamano, A. Efrat, D. Eppstein, D. Frishberg, M. T. Goodrich, and S. G. Kobourov, P. Matias, and V. Polishchuk.
  arXiv:1902.06875.
  Computational Geometry: Young Researchers Forum, 2019.
  Proc. 30th International Symposium on Algorithms and Computation (ISAAC 2019), Shanghai, China, 2019.
  Leibniz International Proceedings in Informatics (LIPIcs) 149, 2019, pp. 51:1–51:21.

  We apply the nearest-neighbor chain algorithm to repeatedly find pairs of mutual nearest neighbors for different distances, speeding up the times for the multi-fragment TSP heuristic, motorcycle graphs, straight skeletons, and other problems.

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

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

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

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

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