**Spanning trees in multipartite geometric graphs**.

A. Biniaz, P. Bose, D. Eppstein, A. Maheshwari, P. Morin, and M. Smid.

arXiv:1611.01661.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.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.

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

Semi-automatically filtered from a common source file.