Domov > Obvestila > Sergio Cabello: Edge-Removal and Non-Crossing Configurations in Geometric Graphs

Sergio Cabello: Edge-Removal and Non-Crossing Configurations in Geometric Graphs

Datum objave: 25. 2. 2008
Vir: Seminar za teorijo grafov in algoritme
Thursday, February 28, 2008, at 12:15 in room PS, Jadranska 19.

We study the following extremal problem for geometric graphs: Find a tight bound on the number of arbitrary edges that can be removed from any complete geometric graph with 2n vertices such that the remaining graph still contains a non-crossing perfect matching. We also consider the same question when a non-crossing subtree of given size has to remain, instead of a perfect matching.

Joint work with O. Aichholzer, R. Fabila-Monroy, D. Flores-Peñaloza, T. Hackl, C. Huemer, F. Hurtado, and D. R. Wood.