Repositorio de producción científica de la Universidad de Sevilla

Triangulations without pointed spanning trees


Advanced Search
Opened Access Triangulations without pointed spanning trees
Show item statistics
Export to
Author: Aichholzer, Oswin
Huemer, Clemens
Krasser, Hannes
Date: 2004
Document type: Presentation
Abstract: Problem 50 in the Open Problems Project asks whether any triangulation on a point set in the plane contains a pointed spanning tree as a subgraph. We provide a counterexample. As a consequence we show that there exist triangulations which require a linear number of edge flips to become Hamiltonian.
Size: 98.41Kb
Format: PDF


This work is under a Creative Commons License: 
Attribution-NonCommercial-NoDerivatives 4.0 Internacional

This item appears in the following Collection(s)