Reconstruction of the geometric structure of a set of points in the plane from its geometric tree graph

DOI10.1007/S00454-015-9750-6zbMATH Open1335.05042arXiv1412.8400OpenAlexW1615545474MaRDI QIDQ282748FDOQ282748

Authors: Chaya Keller, Micha A. Perles 

Publication date: 12 May 2016

Published in: Discrete \& Computational Geometry (Search for Journal in Brave)

Abstract: Let P be a finite set of points in general position in the plane. The structure of the complete graph K(P) as a geometric graph includes, for any pair [a,b],[c,d] of vertex-disjoint edges, the information whether they cross or not. The simple (i.e., non-crossing) spanning trees (SSTs) of K(P) are the vertices of the so-called Geometric Tree Graph of P, G(P). Two such vertices are adjacent in G(P) if they differ in exactly two edges, i.e., if one can be obtained from the other by deleting an edge and adding another edge. In this paper we show how to reconstruct from G(P) (regarded as an abstract graph) the structure of K(P) as a geometric graph. We first identify within G(P) the vertices that correspond to spanning stars. Then we regard each star S(z) with center z as the representative in G(P) of the vertex z of K(P). (This correspondence is determined only up to an automorphism of K(P) as a geometric graph.) Finally we determine for any four distinct stars S(a), S(b), S(c), and S(d), by looking at their relative positions in G(P), whether the corresponding segments cross.

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

Recommendations

• Reconstruction of the crossing type of a point set from the compatible exchange graph of noncrossing spanning trees
• On geometric independency trees for points in the plane
• Reconstruction of the crossing type of a point set from the compatible exchange graph of noncrossing spanning trees
• Publication:4504031
• Compatible spanning trees

zbMATH Keywords

reconstructiongeometric tree graphs

Mathematics Subject Classification ID

Trees (05C05) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Graphs and abstract algebra (groups, rings, fields, etc.) (05C25)

Cites Work

• Title not available (Why is that?)
• On connectivities of tree graphs
• On the Tree Graph of a Matroid
• Geometric tree graphs of points in convex position
• Graph reconstruction -- some new developments
• Reverse search for enumeration
• Title not available (Why is that?)
• Graph reconstruction—a survey
• Title not available (Why is that?)
• A congruence theorem for trees

Cited In (5)

• Reconstruction of the path graph
• Reconstruction of the crossing type of a point set from the compatible exchange graph of noncrossing spanning trees
• Geometric tree graphs of points in convex position
• Reconstruction of the crossing type of a point set from the compatible exchange graph of noncrossing spanning trees
• Recognizing Geometric Trees as Positively Weighted Straight Skeletons and Reconstructing Their Input

This page was built for publication: Reconstruction of the geometric structure of a set of points in the plane from its geometric tree graph

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