5
$\begingroup$

If I describe a surface of genus $g$ using a cellularly embedded graph with $n$ vertices, can I immediately conclude that $g = O(n)$ and thus the number of edges is linear in $n$? .

Also the other direction is not clear to me, for example every platonic solid is homeomorphic to the 2-sphere, but they have different number of vertices. So is there a theorem which states that if I have a surface of genus $g$ then I need at least $f(g)$ many vertices for a polygonal schema or a cellularly embedded graph to represent the surface ?

Thank you .

2 Answers 2

1

If $G$ is a planar graph with $v\ge 3$ vertices, it is well-known that $e \le 3v - 6$ (see Wikipedia's article on planar graphs, for instance). For surfaces of higher genus, I don't know if a similar criterion exists, but you might try looking in Mohar and Thomassen's book $\textit{Graphs on Surfaces}$.

  • 1
    The platonic solids have different girths (size of the smallest cycle/face) which is why they have different numbers of vertices. If the girth of the graph is $h$ then the number of edges in a graph on a surface of genus $g$ is at most the following: $\frac{h}{h-2} (n+2g-2)$2012-01-23
0

It depends what you mean. You can always contract a regular neighborhood of a spanning tree in your graph to get a $1$-vertex graph that fills up your surface, so I would say "no". As for what kinds of degree sequences are allowed, I think this is still somewhat open, except for the torus.