Minimum plane bichromatic spanning trees

DOI10.1145/3747591MaRDI QIDQ6907338zbMATH OpenFDO

Authors Hugo A. Akitaya, Ahmad Biniaz, Erik D. Demaine, Linda Kleist, Frederick Stock, Csaba D. Tóth

Publication date 3 November 2025

Published in ACM Transactions on Algorithms (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1145/3747591

zbMATH Keywords

bichromatic spanning treeminimum spanning treeplane tree

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Approximation algorithms (68W25) Programming involving graphs or networks (90C35)

Cites work

• A Turán-type theorem on chords of a convex polygon
• Applications of a semi-dynamic convex hull algorithm
• Applications of the crossing number
• Approximation schemes for degree-restricted MST and red-blue separation problems
• Bipartite embeddings of trees in the plane
• Computational geometry. Algorithms and applications.
• Crossing families
• Dynamic minimum bichromatic separating circle
• Edge partitions of complete geometric graphs
• Encompassing colored planar straight line graphs
• Euclidean maximum matchings in the plane -- local to global
• Generalizing ham sandwich cuts to equitable subdivisions
• Geometric planar networks on bichromatic collinear points
• scientific article; zbMATH DE number 1507297 (Why is no real title available?)
• scientific article; zbMATH DE number 2209732 (Why is no real title available?)
• Maximum plane trees in multipartite geometric graphs
• On the bichromatic k-set problem
• On the maximum number of edges in topological graphs with no four pairwise crossing edges
• On the shortest spanning subtree of a graph and the traveling salesman problem
• Partitioning arrangements of lines. I: An efficient deterministic algorithm
• Planar bichromatic bottleneck spanning trees
• Planar bichromatic minimum spanning trees
• Planar point sets determine many pairwise crossing segments
• Plane bichromatic trees of low degree
• Pointed binary encompassing trees: simple and optimal
• Polynomial time approximation schemes for Euclidean traveling salesman and other geometric problems
• Properly colored geometric matchings and 3-trees without crossings on multicolored points in the plane
• Quasi-planar graphs have a linear number of edges
• Quasiplanar graphs, string graphs, and the Erdős-Gallai problem
• Separating bichromatic point sets in the plane by restricted orientation convex hulls
• SEPARATING POINT SETS IN POLYGONAL ENVIRONMENTS
• Simple \(k\)-planar graphs are simple \((k + 1)\)-quasiplanar
• Simple alternating path problem
• Spanning trees in multipartite geometric graphs
• Vertex-colored encompassing graphs
• Über ein Minimalproblem.

This page was built for publication: Minimum plane bichromatic spanning trees

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6907338)