maximum average number of neighbors on a manifold

Question

For a finite planar graph (or map in the cartographic sense, since they are equivalent) on a sphere, the maximum average number of neighbors is at least five, because you can tile the sphere with pentagons. On the plane it is at least 6-epsilon for any positive value of epsilon, because a sufficiently big hexagonal partial tiling would do the trick.

Has the general question, "What is the maximum average number of neighbors for a planar graph on a 2-d manifold?" been answered?

Answer 1

Note that the class of graphs that can be embedded without crossing on the surface of a 2d sphere or in the 2d plane are the same (known as the planar graphs).

If you allows multigraphs, obviously, there is no limit on the degree, so we consider simple graphs.

Let $G(V, E)$ be a planar connected simple graph with $n$ vertices, $m$ edges and $f$ faces. It is well known that $$m\leq 3n-6$$ This is a consequence of the Euler formula, which states that $$n-m+f=2$$ Each edge belongs to exactly 2 faces, and each face has at least 3 sides (otherwise, the graph would not be simple) so $3f \leq 2m$. Plugin it in the euler formula, we get $m-n+2\leq \frac{2m}{3}$ yielding $m\leq 3n-6$.

The sum of the degrees of a graph is $$\sum_{v\in E} d(v) = 2m$$ because each edge is counted twice in the sum (once for each extremity).

The average degree of a graph is given by $$\frac{1}{n}\sum_{v\in E} d(v) = \frac{2m}{n} \leq \frac{6n-12}{n} < 6$$

As you noticed, this bound can be reached as close as we want.

However, if you allows the graphs to be drawn on more general manifolds (torus, etc...), there is no bound on the average degree, because any graph can be embedded on surface with sufficiently large genus. (any graph can be embedded on a surface of genus $m$).

For a fixed genus, we can still derive a bound on the average degree. The Euler formula still holds for graph a genus $g$: $$\chi = 2-2g \leq n-m+f$$ and we still have $3f \leq 2m$, so: $$m-n+2-2g\leq \frac{2m}{3}$$ which gives: $$m \leq 3n-6+6g$$ So the average degree is bounded by: $$\frac{2m}{n} \leq \frac{6n-12+12g}{n} \leq 6 + \frac{12g-12}{n}$$ So big graphs will not have an average degree much greater than $6$.