Packing plane spanning trees and paths in complete geometric graphs

DOI10.1016/j.ipl.2017.04.006zbMath1416.05219arXiv1707.05440WikidataQ54308471 ScholiaQ54308471MaRDI QIDQ2628273

Alexander Pilz, Matias Korman, Maarten Löffler, Bettina Speckmann, Thomas Hackl, Ermo Welzl, Marc J. van Kreveld, Oswin Aichholzer

Publication date: 13 June 2017

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1707.05440

zbMATH Keywords

combinatorial problems; spanning tree; geometric graph; edge-disjoint graphs

Mathematics Subject Classification ID

05C05: Trees

05C38: Paths and cycles

05C70: Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)

Related Items

Packing 1-plane Hamiltonian cycles in complete geometric graphs, On asymptotic packing of convex geometric and ordered graphs, k-Planar Placement and Packing of Δ-Regular Caterpillars, Order on order types, Coloring drawings of graphs, On asymptotic packing of geometric graphs, On crossing-families in planar point sets, Packing plane spanning trees into a point set, Packing plane spanning graphs with short edges in complete geometric graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Geometric graphs with no three disjoint edges
• Noncrossing Hamiltonian paths in geometric graphs
• The book thickness of a graph
• Applications of a semi-dynamic convex hull algorithm
• Bipartite embeddings of trees in the plane
• Crossing families
• Ramsey-type results for geometric graphs. I
• Geometric graphs with few disjoint edges
• Bounds of the number of disjoint spanning trees
• Enumerating order types for small point sets with applications
• Partitions of complete geometric graphs into plane trees
• Blockers for Noncrossing Spanning Trees in Complete Geometric Graphs
• On the Problem of Decomposing a Graph into n Connected Factors
• Edge-Disjoint Spanning Trees of Finite Graphs
• Geometric Thickness of Complete Graphs
• Order on Order Types