Published March 20, 2017 | Version v1
Publication

Triangulations without pointed spanning trees

Description

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.

Abstract

Acciones Integradas 2003-2004

Abstract

Austrian Fonds zur Förderung der Wissenschaftlichen Forschung

Additional details

Identifiers

URL
https://idus.us.es/handle/11441/56020
URN
urn:oai:idus.us.es:11441/56020

Origin repository

Origin repository
USE