# Graph Isomorphisms, Delaunay Triangulation on a sphere, and Kulikowski's Theorem

Suppose I have a collection of $n$ non-collinear points on a sphere, $\left\lbrace P_i\right\rbrace_{i=1}^n$. And I construct a mapping from this collection of points to the Delaunay Triangulation on the sphere, $\left\lbrace P_i\right\rbrace_{i=1}^n \overset{DT}{\mapsto} \left( \left\lbrace P_i\right\rbrace_{i=1}^n, \mathcal{F}_{\left\lbrace P_i\right\rbrace_{i=1}^n} , \mathcal{E}_{\left\lbrace P_i\right\rbrace_{i=1}^n}\right)$, where

• $\left\lbrace P_i\right\rbrace_{i=1}^n$ is the set of vertices in the delaunay triangulation.
• $\mathcal{F}_{\left\lbrace P_i\right\rbrace_{i=1}^n}$ is the set of faces (lets just say the faces are the interior regions only) on the sphere.
• $\mathcal{E}_{\left\lbrace P_i\right\rbrace_{i=1}^n}$ is the set of edges. Edges are really arc segments on the sphere.

To illustrate the point, here is an example of such a Delaunay triangulation:

Kulikowski's Theorem states, "For every positive integer, $n$, there exists a sphere which has exactly $n$ lattice points on its surface."

So lets call these $n$ lattice points, $\left\lbrace L_i\right\rbrace_{i=1}^n$ and corresponding Delaunay Triangulation mapping as such $\left\lbrace L_i\right\rbrace_{i=1}^n \overset{DT}{\mapsto} \left( \left\lbrace L_i\right\rbrace_{i=1}^n, \mathcal{F}_{\left\lbrace L_i\right\rbrace_{i=1}^n} , \mathcal{E}_{\left\lbrace L_i\right\rbrace_{i=1}^n}\right)$

So, I have some questions, and they are in descending ordered in which I desire an answer for:

• Is there a graph isomorphism from $\left( \left\lbrace P_i\right\rbrace_{i=1}^n, \mathcal{F}_{\left\lbrace P_i\right\rbrace_{i=1}^n} , \mathcal{E}_{\left\lbrace P_i\right\rbrace_{i=1}^n}\right)$ to $\left( \left\lbrace L_i\right\rbrace_{i=1}^n, \mathcal{F}_{\left\lbrace L_i\right\rbrace_{i=1}^n} , \mathcal{E}_{\left\lbrace L_i\right\rbrace_{i=1}^n}\right)$? If so, does it preserve the (Face-Edge) relationships between the graphs?
• If a graph isomorphism exists, is there a way to explicitly define the graph isomorphic mappings?
• What is the basis for this lattice on the sphere for Kulikowski's Theorem? Is it any arbitrary basis?

I'm not really sure how to cite the image. I got it from this paper: http://hal.inria.fr/docs/00/44/19/38/PDF/RR-7004.pdf

-
I'm wondering if this question is more catered to the mathoverflow. Yay? Nay? If not, then which community could best guide me to some answers? –  torrho Oct 2 '12 at 0:49
Okay, I thought about the lattice sphere for a little bit. 1. There are 3 types of faces on the sphere. Because I don't know the basis of the lattice, I assume $\left\lbrace l_1, l_2, l_3 \right\rbrace$ is a basis and that there can be three distinct angles that can be formed, the angle between $l_1$ and $l_2$, the angle between $l_2$ and $l_3$, and the angle between $l_1$ and $l_3$. We construct the equivalence classes of $\mathcal{F}_{\left\lbrace L_i\right\rbrace_{i=1}^n }$ determined by these distinct angles formed. Also, I can think of the lattice points as vertices of a polyhedron –  torrho Oct 2 '12 at 4:04

The answer to your first question is no: no Delaunay triangulation exists for the $n$ lattice points on the sphere from Kulikowski's Theorem, because all $n$ are collinear. (All the points lie in the $x,y$-plane, with the equations as given at Mathworld. The sphere is just constructed so that the circle where it intersects with the $x,y$-plane is the Schinzel Circle with $n$ lattice points, and the rest of it has no lattice points.)
The answer to your third question is that it is, by default, the integer lattice (of all points $(a,b,c) \in \mathbb{R}^3$ such that $a, b, c \in \mathbb{Z}$.) But by applying a linear transformation to get to any lattice you like, you get ellipses (in the plane) or ellipsoids (in 3-space) with the same property; if your lattice has an orthonormal basis, then you'll get spheres again.