Packing plane spanning trees and paths in complete geometric graphs

Oswin Aichholzer, Thomas Hackl, Matias Korman, Marc van Kreveld, Maarten Löffler, Alexander Pilz*, Bettina Speckmann, Emo Welzl

*Korrespondierende/r Autor/-in für diese Arbeit

Publikation: Beitrag in einer FachzeitschriftArtikelBegutachtung

Abstract

We consider the following question: How many edge-disjoint plane spanning trees are contained in a complete geometric graph GKn on any set S of n points in general position in the plane? We show that this number is in Ω(n). Further, we consider variants of this problem by bounding the diameter and the degree of the trees (in particular considering spanning paths).

Originalspracheenglisch
Seiten (von - bis)35-41
Seitenumfang7
FachzeitschriftInformation Processing Letters
Jahrgang124
DOIs
PublikationsstatusVeröffentlicht - 1 Aug. 2017

ASJC Scopus subject areas

  • Theoretische Informatik
  • Signalverarbeitung
  • Information systems
  • Angewandte Informatik

Fingerprint

Untersuchen Sie die Forschungsthemen von „Packing plane spanning trees and paths in complete geometric graphs“. Zusammen bilden sie einen einzigartigen Fingerprint.

Dieses zitieren