Género de celulares gráfico incrustado

Question

Si describo una superficie de género $g$ utilizando un celularmente incrustado gráfico con $n$ vértices, puedo inmediatamente a la conclusión de que $g = O(n)$, por lo que el número de aristas es lineal en $n$? .

También en el otro sentido no es claro para mí, por ejemplo, cada sólido platónico es homeomórficos a la 2-esfera, pero tienen diferente número de vértices. Por lo que hay un teorema que dice que si tengo una superficie de género $g$, entonces necesito al menos $f(g)$ muchos vértices de una poligonal esquema o un celularmente incrustado gráfico para representar la superficie ?

Gracias .

Answer 1

Si $G$ es un plano gráfico con $v\ge 3$ vértices, es bien sabido que el $e \le 3v - 6$ (véase el artículo de Wikipedia sobre grafos planares, por ejemplo). Para superficies de más de un género, no sé si un criterio similar existe, pero es posible que trate de buscar en Mohar y Thomassen el libro de $\textit{Graphs on Surfaces}$.

Answer 2

Depende de lo que quieres decir. Usted siempre puede contratar a un regular barrio de un árbol de expansión en el gráfico para obtener un $1$-vértice de la gráfica que se llena de su superficie, así que yo diría "no". Como para qué tipos de grado de las secuencias son permitidos, creo que esto es algo abierto, excepto para el toro.