Grafo embebido
en la que sus vértices están asociados con puntos de
y sus lados se asocian con arcos simples (imágenes homeomórficas de
De manera informal, un embebido de un gráfico en una superficie es un dibujo del gráfico en la superficie de tal manera que sus lados se intersequen solo en sus puntos extremos.
Es bien sabido que cualquier gráfico finito se puede incrustar en el espacio euclídeo tridimensional
[1] Por definición, un grafo plano es aquel que se puede incrustar en un espacio euclídeo bidimensional
En tales contextos, la definición más estricta se describe como embebido de grafos sin cruces.
[3] Una incrustación de 2 celdas, incrustación celular o mapa es un embebido en el que cada cara es homeomorfa a un disco abierto.
El género (o también genus) de un Grafo es el número entero mínimo
tal que el gráfico se puede embeber en una superficie de genus
El género no orientable de un grafo es el número entero mínimo
tal que el grafo en cuestión se puede embeber en una superficie no orientable de género (no orientable)
Las incrustaciones con el mismo sistema de rotación se consideran equivalentes y la clase de embebidos de equivalencia correspondiente se denomina embebido combinatorio (a diferencia del término embebido topológico, que se refiere a la definición anterior en términos de puntos y curvas).
A veces, el propio sistema de rotación se denomina embebido combinatorio.
Sin embargo, el manejo de estos órdenes basados en caras es menos sencillo, ya que en algunos casos algunos bordes pueden atravesarse dos veces en un límite de cara.
Para superar este inconveniente combinatorio, se puede considerar que cada lado está dividido longitudinalmente en dos medios lados o bordes.
Según esta convención, en todos los recorridos de límites de caras, cada medio lado se recorre solo una vez y los dos medios lados del mismo lado siempre se recorren en direcciones opuestas.
[8] Al mismo tiempo, el problema del género del gráfico es de complejidad parametrizada, es decir, se sabe que algoritmos de complejidad temporal polinómica verifican si un gráfico se puede embeber en una superficie de un género fijo dado, así como para encontrar la incrustación.
[9] Sin embargo, Wendy Myrvold y William Kocay demostraron en 2011 que el algoritmo propuesto por Filotti, Miller y Reif era incorrecto.
[10] En 1999 se informó que el caso de género fijo se puede resolver en tiempo lineal respecto al tamaño del grafo y en tiempo doble exponencial respecto al género.
[1] Un método para hacerlo es colocar los puntos en cualquier línea recta en el espacio y dibujar los lados como curvas, cada una de las cuales se encuentra en un semiespacio distinto, con todos los semiplanos teniendo esa línea como límite común.
Se observó que, de hecho, se pueden dibujar varios vínculos en la misma "página"; el grosor del libro del grafo es el número mínimo de semiplanos necesarios para tal dibujo.
Alternativamente, cualquier grafo finito se puede dibujar con vínculos rectilíneos en tres dimensiones sin cruces colocando sus vértices en posición general para que no haya cuatro coplanarios.
Un embebidp de un gráfico en un espacio tridimensional en el que dos de los ciclos no están vinculados topológicamente se denomina embebido sin enlaces.
