David Eppstein - Publications

Publications with Pavel Valtr

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