Spanning trees in multipartite geometric graphs

DOI10.1007/s00453-017-0375-4zbMath1410.68280arXiv1611.01661OpenAlexW2555258613WikidataQ102071120 ScholiaQ102071120MaRDI QIDQ1755734

David Eppstein, Ahmad Biniaz, Prosenjit Bose, Pat Morin, Anil Maheshwari, Michiel H. M. Smid

Publication date: 11 January 2019

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1611.01661

zbMATH Keywords

minimum spanning treemaximum spanning treemultipartite geometric graphs

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (4)

Geometric planar networks on bichromatic collinear points ⋮ Planar Bichromatic Bottleneck Spanning Trees ⋮ Maximum plane trees in multipartite geometric graphs ⋮ Multi-colored spanning graphs

Cites Work

• Unnamed Item
• A linear-time algorithm for computing the Voronoi diagram of a convex polygon
• Computing Euclidean maximum spanning trees
• Optimal time bounds for some proximity problems in the plane
• Splitting a Delaunay triangulation in linear time
• Triangulating the Square and Squaring the Triangle: Quadtrees and Delaunay Triangulations are Equivalent
• Computing the extreme distances between two convex polygons
• Buckets, Heaps, Lists, and Monotone Priority Queues
• Dynamic Planar Voronoi Diagrams for General Distance Functions and their Algorithmic Applications

This page was built for publication: Spanning trees in multipartite geometric graphs