En teoría de grafos , una rama de las matemáticas, un grafo de mapa es un grafo no dirigido formado como el grafo de intersección de un número finito de regiones simplemente conectadas e internamente disjuntas del plano euclidiano . Los grafos de mapa incluyen los grafos planares , pero son más generales. Cualquier número de regiones puede encontrarse en una esquina común (como en las Cuatro Esquinas de los Estados Unidos, donde se encuentran cuatro estados), y cuando lo hacen, el grafo de mapa contendrá una camarilla que conecta los vértices correspondientes, a diferencia de los grafos planares en los que las camarillas más grandes tienen solo cuatro vértices. [1] Otro ejemplo de un grafo de mapa es el grafo del rey , un grafo de mapa de los cuadrados del tablero de ajedrez que conecta pares de cuadrados entre los cuales se puede mover el rey del ajedrez.
Los grafos de mapas se pueden representar combinatoriamente como los "semicuadrados de grafos bipartitos planares". Es decir, sea G = ( U , V , E ) un grafo bipartito planar , con bipartición ( U , V ) . El cuadrado de G es otro grafo en el mismo conjunto de vértices, en el que dos vértices son adyacentes en el cuadrado cuando están a lo sumo dos pasos de distancia en G . El medio cuadrado o mitad bipartita es el subgrafo inducido de un lado de la bipartición (digamos V ) en el grafo cuadrado: su conjunto de vértices es V y tiene una arista entre cada dos vértices en V que están a dos pasos de distancia en G . El medio cuadrado es un grafo de mapas. Se puede representar geométricamente encontrando una incrustación plana de G , y expandiendo cada vértice de V y sus aristas adyacentes en una región en forma de estrella, de modo que estas regiones se toquen en los vértices de U . A la inversa, cada grafo de mapas se puede representar como un medio cuadrado de esta manera. [1]
En 1998, Mikkel Thorup afirmó que los gráficos de mapas pueden reconocerse en tiempo polinomial . [2] Sin embargo, el alto exponente del algoritmo que esbozó lo hace poco práctico, y Thorup no ha publicado los detalles de su método y su prueba. [3]
El problema del conjunto independiente máximo tiene un esquema de aproximación en tiempo polinomial para gráficos de mapas, y el número cromático se puede aproximar a un factor de dos en tiempo polinomial. [4] La teoría de la bidimensionalidad conduce a muchos otros algoritmos de aproximación y algoritmos manejables con parámetros fijos para problemas de optimización en gráficos de mapas. [5] [6] [7]
Un grafo k -mapa es un grafo-mapa derivado de un conjunto de regiones en las que, como máximo, k regiones se encuentran en cualquier punto. De manera equivalente, es el medio cuadrado de un grafo bipartito plano en el que el conjunto de vértices U (el lado de la bipartición no utilizado para inducir el medio cuadrado) tiene un grado máximo k . Un grafo 3-mapa es un grafo plano , y cada grafo plano puede representarse como un grafo 3-mapa. Cada grafo 4-mapa es un grafo 1-planar , un grafo que puede dibujarse con, como máximo, un cruce por arista, y cada grafo 1-planar óptimo (un grafo formado a partir de una cuadrangulación plana añadiendo dos diagonales cruzadas a cada cara cuadrilátera) es un grafo 4-mapa. Sin embargo, algunos otros grafos 1-planares no son grafos-mapa, porque (a diferencia de los grafos-mapa) incluyen aristas cruzadas que no son parte de un subgrafo completo de cuatro vértices. [1]