A sufficient condition for the existence of plane spanning trees on geometric graphs

DOI10.1016/J.COMGEO.2012.02.006zbMATH Open1251.05040arXiv1202.3385OpenAlexW3123702182MaRDI QIDQ714896FDOQ714896

E. Rivera-Campo, Virginia Urrutia-Galicia

Publication date: 12 October 2012

Published in: Computational Geometry (Search for Journal in Brave)

Abstract: Let P be a set of n > 2 points in general position in the plane and let G be a geometric graph with vertex set P. If the number of empty triangles uvw in P for which the subgraph of G induced by {u,v,w} is not connected is at most n-3, then G contains a non-self intersecting spanning tree.

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

Recommendations

• Publication:4504031
• On geometric independency trees for points in the plane
• Packing plane spanning trees and paths in complete geometric graphs
• Compatible spanning trees
• Graph Drawing

zbMATH Keywords

geometric graphplane treeempty triangle

Mathematics Subject Classification ID

Trees (05C05) Planar graphs; geometric and topological aspects of graph theory (05C10)

Cited In (6)

• Title not available (Why is that?)
• Plane Spanning Trees in Edge-Colored Simple Drawings of $$K_{n}$$
• Plane Geodesic Spanning Trees, Hamiltonian Cycles, and Perfect Matchings in a Simple Polygon
• Algorithms and bounds for drawing non-planar graphs with crossing-free subgraphs
• A necessary and sufficient condition for the existence of a heterochromatic spanning tree in a graph
• On geometric independency trees for points in the plane

This page was built for publication: A sufficient condition for the existence of plane spanning trees on geometric graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q714896)