Question: Say I want to play a game like Go or Go Bang or Chess on a the surface of a sphere ([see here for a question about examples](https://boardgames.stackexchange.com/questions/12729/what-are-examples-of-go-played-on-non-flat-surfaces-like-on-a-sphere)).

The grid on the sphere should have the following characterisitcs:

* all nodes more or less equidistant
* each node connected to four neighbors
* connections don't intersect

I've tried around with constructing such a grid by adding nodes on the edges of an octahedron, or by adding nodes to a bucky-ball like grid, both don't work.

Answer: 
A quick calculation using Euler's $V-E+F=2$, and the fact that since each edge joins two vertices and we have four edges at each vertex, $E=2V$ gives $F-V=2$ ie that there are two more faces than vertices.

Now suppose there are $f\_r$ faces with $r$ vertices. We know that each vertex adjoins 4 faces, so that $$\sum\_{r=2}^\infty rf\_r=4V=4F-8$$

Now since $F=\sum f\_r$ we can rewrite this as $$\sum(r-4)f\_r=-8$$

If we disallow faces with two sides we have $$-f\_3+f\_5+2f\_6+3f\_7+\dots=-8$$

So we can have as many quadrilateral faces as we like (they count zero to the sum), but we need at least eight triangles, and for every face with more than $4$ sides we need more triangles.

So you need to work with this constraint. You could, for example put pyramids on two opposite sides of a cube. Then you could divide the other sides in half along the "equator". You can keep on cutting slices off the cube as long as you like.

This doesn't give you a full answer, but it does suggest some ways to go. 

Note: When you have three edges meeting at each vertex, you can just cut off corners. But that is not an option here - you need to keep the corners on and put extra edges/vertices where the cut would go. So another construction would be to draw edges round each vertex of an octahedron to get roughly equal spacing of vertices. Then edges around the vertices of the resulting figure etc.
The general problem of "how do I pack N points on a sphere, where I maximize the minimum distance between any two points" is known as "finding spherical codes".

More info on Spherical Codes from:

[Wikipedia](https://en.wikipedia.org/wiki/Spherical_code)

[Mathworld](http://mathworld.wolfram.com/SphericalCode.html)

[Neil Sloane](http://neilsloane.com/packings/) -- general discussion, plus solved values for values of N up to 130.

Now this approach gives you the POINTS, but getting the "neighbors" is a bit subtle. I assume you'd want to create a set of polyhedral faces as the convex hull of those sets of points, then consider "neighbors" as points that are connected by an edge. I think [qhull](http://www.qhull.org/) (or its wrappers like [pyhull](http://pythonhosted.org/pyhull)) should be able to do this for you.

Alas, this doesn't exactly answer the problem statement, as such collections of points usually have 3 "closest" neighbors (not 4 as the OP requested). And for certain values of N, there are other anomalies that creep in; the OP would have to decide if this is fit for his purpose.

But this sort of "game board" may be of interest to the OP or others looking at this question.