A uniqueness theorem for Delaunay graphs

DOI10.1134/S0037446613030105MaRDI QIDQ359369zbMATH OpenFDO

Authors A. M. Gurin

Publication date 12 August 2013

Published in Siberian Mathematical Journal (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1134/S0037446613030105

zbMATH Keywords

combinatorial structureDelaunay domainDelaunay graphisomorphic graphsVoronoi domain

Mathematics Subject Classification ID

Polytopes and polyhedra (52B99) Arrangements of points, flats, hyperplanes (aspects of discrete geometry) (52C35) Graph theory (including graph drawing) in computer science (68R10)

Review text

A graph is called a Delauney graph if its edges are segments whose orthogonal hyperplanes through their midpoints form the faces of a Voronoi domain. The author proves a necessary and sufficient condition for two isomoprphic Delauney graphs to be congruent. The proof uses an inductive argument on the congruence of isomorphic pairs of Delauney polyhedra of the two isomorphic Delauney graphs.

Recommendations

• Characterizing Delaunay graphs via fixed point theorem: a simple proof
• Toughness and Delaunay triangulations
• Delaunay graphs are almost as good as complete graphs
• An upper bound for conforming Delaunay triangulations
• Generalized Delaunay triangulation for planar graphs

Cites work

• On the history of the study of convex polyhedra with regular faces and faces composed of regular ones

Cited in

(4)

• Uniqueness in Harper's vertex-isoperimetric theorem
• Characterizing Delaunay graphs via fixed point theorem: a simple proof
• Uniqueness theorem for locally antipodal Delaunay sets
• Toughness and Delaunay triangulations

This page was built for publication: A uniqueness theorem for Delaunay graphs

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