Plane bichromatic trees of low degree

DOI10.1007/s00454-017-9881-zzbMath1395.05035arXiv1512.02730OpenAlexW2593486311MaRDI QIDQ1650794

Prosenjit Bose, Anil Maheshwari, Ahmad Biniaz, Michiel H. M. Smid

Publication date: 13 July 2018

Published in: Lecture Notes in Computer Science, Discrete \& Computational Geometry (Search for Journal in Brave)

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

zbMATH Keywords

bichromatic planar treeslow-degree trees

Mathematics Subject Classification ID

Trees (05C05) Planar graphs; geometric and topological aspects of graph theory (05C10) Coloring of graphs and hypergraphs (05C15)

Related Items

Plane bichromatic trees of low degree, Discrete geometry on colored point sets in the plane -- a survey, Geometric planar networks on bichromatic collinear points, Polynomial Time Algorithms for Bichromatic Problems, Rainbow polygons for colored point sets in the plane

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Spanning \(k\)-trees of bipartite graphs
• Plane geodesic spanning trees, Hamiltonian cycles, and perfect matchings in a simple polygon
• Vertex-colored encompassing graphs
• Partitioning arrangements of lines. I: An efficient deterministic algorithm
• Planar bichromatic minimum spanning trees
• Euclidean minimum spanning trees and bichromatic closest pairs
• Degree constrained tree embedding into points in the plane
• Bipartite embeddings of trees in the plane
• The rooted tree embedding problem into points in the plane
• Generalizing ham sandwich cuts to equitable subdivisions
• Plane bichromatic trees of low degree
• Approximation schemes for degree-restricted MST and red-blue separation problems
• Encompassing colored planar straight line graphs
• Plane Geodesic Spanning Trees, Hamiltonian Cycles, and Perfect Matchings in a Simple Polygon
• Properly Colored Geometric Matchings and 3-Trees Without Crossings on Multicolored Points in the Plane
• General Balanced Subdivision of Two Sets of Points in the Plane
• Optimal Algorithms to Embed Trees in a Point Set
• ON CONNECTING RED AND BLUE RECTILINEAR POLYGONAL OBSTACLES WITH NONINTERSECTING MONOTONE RECTILINEAR PATHS
• COMPUTING LARGEST CIRCLES SEPARATING TWO SETS OF SEGMENTS
• AN OPTIMAL ALGORITHM FOR COMPUTING (≤K)-LEVELS, WITH APPLICATIONS
• SEPARATING POINT SETS IN POLYGONAL ENVIRONMENTS
• Separating objects in the plane by wedges and strips