Another proof of polynomial-time recognizability of Delaunay graphs

This paper presents a new proof to polynomial-time algorithm for determinin g whether a given embedded graph is a Delaunay graph, i.e., whether it is t opologically equivalent to a Delaunay triangulation. The problem of recogni zing the Delaunay graph had long been open. Recently Hodgson et al. gave a combinatorial characterization of the Delaunay graph, and thus constructed the polynomial-time algorithm for recognizing the Delaunay graphs. Their pr oof is based on sophisticated discussions on hyperbolic geometry. On the ot her hand, this paper gives another and simpler proof based on primitive arg uments on Euclidean geometry. Moreover, the algorithm is applied to study t he distribution of non-Delaunay graphs.