David Eppstein - Publications

Publications with Prosenjit Bose

• Spanning trees in multipartite geometric graphs.
  A. Biniaz, P. Bose, D. Eppstein, A. Maheshwari, P. Morin, and M. Smid.
  arXiv:1611.01661.
  Algorithmica 80 (11): 3177–3191, 2018.

  We provide near-linear-time algorithms for minimum and maximum spanning trees 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.

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

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

Co-authors – Publications – David Eppstein – Theory Group – Inf. & Comp. Sci. – UC Irvine

Semi-automatically filtered from a common source file.