Maximum plane trees in multipartite geometric graphs

DOI10.1007/S00453-018-0482-XMaRDI QIDQ5915987zbMATH OpenOpenAlexFDO

Authors Ahmad Biniaz, Prosenjit Bose, Kimberly Crosbie, Jean-Lou De Carufel, David Eppstein, Anil Maheshwari, Michiel Smid

Publication date 25 April 2019

Published in Algorithmica (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s00453-018-0482-x

zbMATH Keywords

approximation algorithmsmultipartite geometric graphsmaximum spanning treesplane spanning trees

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Approximation algorithms (68W25) Graph representations (geometric and intersection representations, etc.) (05C62)

Recommendations

• Maximum plane trees in multipartite geometric graphs
• Spanning trees in multipartite geometric graphs
• On the Red/Blue Spanning Tree Problem

Cites work

• scientific article; zbMATH DE number 741010 (Why is no real title available?)
• Computing Euclidean maximum spanning trees
• Long non-crossing configurations in the plane
• Planar bichromatic minimum spanning trees
• Spanning trees in multipartite geometric graphs

Cited in

(15)

• Euclidean maximum matchings in the plane -- local to global
• Graph Drawing
• Planar bichromatic bottleneck spanning trees
• Maximum plane trees in multipartite geometric graphs
• Noncrossing longest paths and cycles
• Planar Bichromatic Bottleneck Spanning Trees
• Geometric planar networks on bichromatic points
• Minimum plane bichromatic spanning trees
• Euclidean maximum matchings in the plane -- local to global
• Minimum plane bichromatic spanning trees
• An optimal algorithm for plane matchings in multipartite geometric graphs
• Noncrossing longest paths and cycles
• Long plane trees
• Two trees in maximal planar bipartite graphs
• Plane geodesic spanning trees, Hamiltonian cycles, and perfect matchings in a simple polygon

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

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