grafo embebido

En teoría de grafos topológica, un embebido (o también incrustación) de un grafo en una superficie es una representación de sobre 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 , de tal forma que: * Los extremos del arco asociado a un lado son los puntos asociados a los vértices extremos de * Ningún arco incluye puntos asociados a otros vértices * Dos arcos nunca se cortan en un punto interior a cualquiera de los arcos Aquí se entiende por superficie una variedad de orden compacta y conexa. 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 .​ Por definición, un grafo plano es aquel que se puede incrustar en un espacio euclídeo bidimensional A menudo, un embebido se considera una clase de equivalencia (bajo homeomorfismos de ) de las representaciones del tipo que se acaba de describir. Algunos autores definen una versión más débil de la definición de "embebido de grafos" al omitir la condición de no intersección para los lados. En tales contextos, la definición más estricta se describe como embebido de grafos sin cruces.​ Este artículo trata solo de la definición estricta de embebido de grafos. La definición más débil se discute en los artículos "dibujo de grafos" y "número de cruce".