David Eppstein - Publications

Publications with Timothy Johnson

• Square-contact representations of partial 2-trees and triconnected simply-nested graphs.
  G. Da Lozzo, W. E. Devanny, D. Eppstein, and T. Johnson.
  arXiv:1710.00426.
  Proc. 28th Int. Symp. Algorithms and Computation (ISAAC 2017), Phuket, Thailand, 2017.
  Leibniz International Proceedings in Informatics (LIPIcs) 92, pp. 24:1–24:16.
  

  We show that the K_1,1,3-free partial 2-trees and the Halin graphs other than K₄ can all be represented as proper contact graphs of squares in the plane. Among partial 2-trees and Halin graphs, these are exactly the ones that can be embedded without nonempty triangles, which form an obstacle to the existence of square contact representations. However the graph of a square antiprism has no such representation despite being embeddable without any nonempty triangles.

• Quadratic time algorithms appear to be optimal for sorting evolving data.
  J. Besa, W. E. Devanny, D. Eppstein, M. T. Goodrich, and T. Johnson.
  Proc. Algorithm Engineering & Experiments (ALENEX 2018), New Orleans, 2018, pp. 87–96.
  arXiv:1805.05443.

  We experiment with sorting algorithms in the evolving data model, in which, at the same time as the algorithm compares pairs of elements and possibly chooses a new ordering based on the results of the comparison, an adversary randomly chooses two adjacent elements in the sorted order and swaps them. As we show, bubble sort and its variants appear to maintain an order that is within inversion distance of optimal.

• Optimally sorting evolving data.
  J. Besa, W. E. Devanny, D. Eppstein, M. T. Goodrich, and T. Johnson.
  arXiv:1805.03350
  Proc. 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018), Prague.
  Leibniz International Proceedings in Informatics (LIPIcs) 107, pp. 81:1–81:13.
  

  Suppose that a collection of objects has a linear order that is evolving by swaps of randomly chosen consecutive elements. We would like to maintain an approximation to this order using an algorithm that performs one comparison per swap. We show that repeated insertion sort can maintain linear inversion distance from the underlying order, the best possible.