Compatible matchings in geometric graphs
Oswin Aichholzer, Alfredo García Olaverri, Fernando Alfredo Hurtado Díaz, Francisco Javier Tejel Altarriba · RECERCAT (Consorci de Serveis Universitaris de Catalunya) · 2011
Two non-crossing geometric graphs on the same set of points are compatible if their union is also non-crossing. In this paper, we prove that every graph G that has an outerplanar embedding admits a non-crossing perfect matching compatible with G. Moreover, for non-crossing geometric trees and simple polygons, we study bounds on the minimum number of edges that a compatible non-crossing perfect matching must share with the tree or the polygon. We also give bounds on the maximal size of a compatible matching (not necessarily perfect) that is disjoint from the tree or the polygon.