Låt P vara en ändlig uppsättning punkter i allmän position i planet. Strukturen på den fullständiga grafen K(P ) som en geometrisk graf omfattar, för varje par [a, b], [c, d] av vertexdisfogade kanter, informationen om huruvida de korsar eller inte. De enkla (dvs icke-korsande) spännande träd (SSTs) av K(P ) är hörnen i den så kallade geometriska trädgrafik av P, G(P ). Två sådana hörn är intilliggande i G(P ) om de skiljer sig i exakt två kanter, dvs, om en kan erhållas från den andra genom att ta bort en kant och lägga till en annan kant. I detta papper visar vi hur man rekonstruerar från G(P ) (betraktas som en abstrakt graf) strukturen av K(P ) som en geometrisk graf. Vi identifierar först inom G(P ) hörnen som motsvarar spännande stjärnor. Sedan betraktar vi varje stjärna S(z) med center z som representant i G(P ) av vertex z av K(P ). (Denna korrespondens bestäms endast upp till en automorfism av K(P ) som en geometrisk graf.) Slutligen bestämmer vi för fyra olika stjärnor S(a), S(b), S(c), och S(d), genom att titta på deras relativa positioner i G(P ), om motsvarande segment korsar.
Intressant nog kan ordertypen S rekonstrueras från övergångsdiagrammet för bytestransaktionen REF.
Reconstruction of the geometric structure of a set of points in the plane from its geometric tree graph
{'venue': None, 'journal': 'arXiv: Combinatorics', 'mag_field_of_study': ['Mathematics', 'Computer Science']}