Compatible matchings in geometric graphs

O. Aichholzer, A. García, F. Hurtado, and J. Tejel

Abstract:

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.

Reference: O. Aichholzer, A. García, F. Hurtado, and J. Tejel. Compatible matchings in geometric graphs. In Proc. XIV Encuentros de Geometría Computacional, pages 145-148, Alcalá, Spain, 2011.