If you have played games in the Civilization series, you will have noticed that the Earth is represented in a simplified and profoundly unsatisfying way. It is wrapped around the curve of a cylinder with impenetrable barriers in the north and south. This is appealing in its simplicity, but very much unlike real geography. For example, here is a thread discussing the problem and possible solutions.
Unfortunately, that thread misses the core of the problem. The real world is homeomorphic to a sphere and all places on the globe are pairwise effectively equivalent. If one has that, then any approximation should be good enough, no matter how distorted the globe becomes. In a strategy game, only the graph truly matters.
Therefore, what I think I want are simple finite vertex-transitive planar graphs. It seems to me that any graph that can be embedded in the surface of a 2-sphere can be embedded in a plane, so focusing on planar graphs seems to make my problem easier. Unfortunately, I have some other goals that aren't as easy to define, such as being able to generate a graph for any given number of vertices, and being able to imagine the vertices distributed roughly evenly over the surface of a sphere with edges connecting nearby vertices. Unfortunately I have no precise way to express that second goal, but I imagine it could be captured by some upper bound on the diameter of the graph. At least I know that I prefer small diameter graphs over large diameter graphs.
Here is an excellent article I found: https://eudml.org/doc/29561
It only deals with degrees 4 and 5, but I find it hard to imagine how it could be much easier for other degrees. There is only one way to create finite vertex-transitive planar graphs of arbitrary size in that article, and it is effectively lining up vertices along two parallels and connecting them with triangles spanning the equator. Graphs like that would have diameter proportional to the number of vertices and wouldn't cover a sphere well.
The article also supplies many other graphs, but each one seems to be individual, with no apparent pattern and so unless I am missing something each would need to be treated as a special case when finding a visually appropriate planar embedding. The planar embedding provided in the article are not appropriate because they are roughly circular instead of allowing vertices on the left side to connect to vertices on the right as one expects in most map projections such as those found in an atlas.
So what I would really like is an algorithm with parameter $n$ that produces a planar embedding of some simple vertex-transitive small-diameter graph with $n$ vertices, where $n$ is allowed to be many possible numbers, and where the embedding is suggestive of a map projection in an atlas.
In addition to that, there are some smaller problems that would surely be useful toward the greater goal:
- What is the smallest possible diameter for vertex-transitive planar graphs with $n$ vertices? Or what is the largest diameter known to be smaller than the smallest possible diameter?
- Given $n$, how can one construct a vertex-transitive planar graph with $n$ vertices that has approximately the smallest possible diameter?
- Assuming there is no answer for the second question, how could one construct a list of all finite vertex-transitive planar graphs for the purpose of searching for graphs with desired properties?