David Eppstein – Publications

Publications with Kimberly Crosbie

• Maximum plane trees in multipartite geometric graphs.
  A. Biniaz, P. Bose, J.-L. De Carufel, K. Crosbie, D. Eppstein, A. Maheshwari, M. Smid.
  15th Algorithms and Data Structures Symp. (WADS 2017), St. John's, Newfoundland.
  Springer, Lecture Notes in Comp. Sci. (2017), pp. 193–204.
  Algorithmica 81 (4): 1512–1534, 2019.

  We consider problems of constructing the maximum-length plane (non-self-crossing) spanning tree on Euclidean graphs given by multicolored point sets, where each point forms a vertex, and each bichromatic pair of points forms an edge with length equal to their Euclidean distance. We show that several such problems can be efficiently approximated.