Loading...
Loading...

Go to the content (press return)

Compatible matchings in geometric graphs

Author
Aichholzer, O.; Garcia, A.; Hurtado, F.; Tejel, F. J.
Type of activity
Presentation of work at congresses
Name of edition
XIV Encuentros de Geometría Computacional
Date of publication
2011
Presentation's date
2011-06-27
Book of congress proceedings
Actas de los XIV Encuentros de Geometría Computacional
First page
145
Last page
148
Publisher
Centre de Recerca Matemàtica
Repository
http://hdl.handle.net/2117/15075 Open in new window
URL
http://www.crm.es/Publications/Documents/Documents_8.pdf Open in new window
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 compatib...
Citation
Aichholzer, O. [et al.]. Compatible matchings in geometric graphs. A: Encuentros de Geometría Computacional. "Actas de los XIV Encuentros de Geometría Computacional". Alcalá de Henares: Centre de Recerca Matemàtica, 2011, p. 145-148.
Group of research
DCG - Discrete and Combinatorial Geometry

Participants

  • Aichholzer, Oswin  (author and speaker )
  • Garcia Olaverri, Alfredo Martin  (author and speaker )
  • Hurtado Diaz, Fernando Alfredo  (author and speaker )
  • Tejel Altarriba, F. Javier  (author and speaker )

Attachments