Planar bichromatic minimum spanning trees

DOI10.1016/j.jda.2008.08.001zbMath1176.90597OpenAlexW1967661673MaRDI QIDQ1044035

Damian Merrick, Jun Luo, Magdalene G. Borgelt, Maarten Löffler, Rodrigo I. Silveira, Mostafa Vahedi, Marc J. van Kreveld

Publication date: 10 December 2009

Published in: Journal of Discrete Algorithms (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.jda.2008.08.001

zbMATH Keywords

planaritycomputational geometryminimum spanning treebichromatic point set

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Combinatorial optimization (90C27)

Related Items

Plane bichromatic trees of low degree, Geometric planar networks on bichromatic collinear points, Colored spanning graphs for set visualization, Planar Bichromatic Bottleneck Spanning Trees, On the red/blue spanning tree problem, Maximum plane trees in multipartite geometric graphs, The balanced connected subgraph problem, Vertex-colored encompassing graphs, Planar bichromatic minimum spanning trees

Cites Work

• Unnamed Item
• On the shortest spanning subtree of a graph and the traveling salesman problem
• Partitioning arrangements of lines. II: Applications
• Planar bichromatic minimum spanning trees
• Euclidean minimum spanning trees and bichromatic closest pairs
• Bipartite embeddings of trees in the plane
• Approximation schemes for degree-restricted MST and red-blue separation problems
• Encompassing colored planar straight line graphs
• Planar Formulae and Their Uses
• Dynamic Point Location in General Subdivisions
• ON CONNECTING RED AND BLUE RECTILINEAR POLYGONAL OBSTACLES WITH NONINTERSECTING MONOTONE RECTILINEAR PATHS
• COMPUTING LARGEST CIRCLES SEPARATING TWO SETS OF SEGMENTS
• Growing a Tree from Its Branches
• Pointed and colored binary encompassing trees
• AN OPTIMAL ALGORITHM FOR COMPUTING (≤K)-LEVELS, WITH APPLICATIONS
• SEPARATING POINT SETS IN POLYGONAL ENVIRONMENTS
• Separating objects in the plane by wedges and strips