Sergio Cabello: Edge-Removal and Non-Crossing Configurations in Geometric Graphs
Vir: Seminar za teorijo grafov in algoritme
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.