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

DOI10.1016/J.COMGEO.2012.02.006MaRDI QIDQ714896zbMATH OpenOpenAlexFDO

Authors E. Rivera-Campo, Virginia Urrutia-Galicia

Publication date 12 October 2012

Published in Computational Geometry (Search for Journal in Brave)

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

zbMATH Keywords

geometric graphplane treeempty triangle

Mathematics Subject Classification ID

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

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.

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

Cited in

(7)

• Compatible spanning trees
• scientific article; zbMATH DE number 1507305 (Why is no real title available?)
• 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)