Gráfico de mapa

Los Cuatro Rincones de los Estados Unidos. Aunque estos cuatro estados se encuentran en un punto, en lugar de compartir una frontera de longitud distinta de cero, forman vértices adyacentes en el grafo del mapa correspondiente.

El grafo del rey es el grafo que representa las casillas del tablero de ajedrez. Un rey de ajedrez puede moverse entre dos vértices adyacentes cualesquiera de este grafo.

En la 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 conexas 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 las casillas del tablero de ajedrez que conecta pares de casillas entre las cuales el rey de ajedrez puede moverse.

Los grafos de mapas pueden representarse 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 sobre el mismo conjunto de vértices, en el que dos vértices son adyacentes en el cuadrado cuando están separados como máximo por dos pasos en G . El semicuadrado 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 par de vértices en V que están separados por dos pasos en G . El semicuadrado es un grafo de mapas. Puede representarse geométricamente encontrando una incrustación planar 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 . Recíprocamente, todo grafo de mapas puede representarse como un semicuadrado de esta manera. ^{[ 1 ]}

En 1998, Mikkel Thorup afirmó que los grafos de mapas pueden reconocerse en tiempo polinomial . ^{[ 2 ]} Sin embargo, el alto exponente del algoritmo que esbozó lo hace impracticable, y Thorup no ha publicado los detalles de su método ni su demostración. ^{[ 3 ]}

El problema del conjunto independiente máximo tiene un esquema de aproximación en tiempo polinomial para grafos de mapas, y el número cromático puede aproximarse con un factor de dos en tiempo polinomial. ^{[ 4 ]} La teoría de la bidimensionalidad conduce a muchos otros algoritmos de aproximación y algoritmos tratables de parámetros fijos para problemas de optimización en grafos de mapas. ^{[ 5 ] [ 6 ] [ 7 ]}

Un grafo k -mapa es un grafo de mapa derivado de un conjunto de regiones en el que como máximo k regiones se encuentran en cualquier punto. Equivalentemente, es el semicuadrado de un grafo bipartito planar en el que el conjunto de vértices U (el lado de la bipartición no utilizado para inducir el semicuadrado) tiene grado máximo k . Un grafo 3-mapa es un grafo planar , y todo grafo planar puede representarse como un grafo 3-mapa. Todo grafo 4-mapa es un grafo 1-planar , un grafo que puede dibujarse con como máximo un cruce por arista, y todo grafo 1-planar óptimo (un grafo formado a partir de una cuadrangulación planar añadiendo dos diagonales que se cruzan a cada cara cuadrilátera) es un grafo 4-mapa. Sin embargo, algunos otros grafos 1-planares no son grafos de mapa, porque (a diferencia de los grafos de mapa) sus dibujos 1-planares incluyen aristas que se cruzan que no forman parte de un subgrafo completo de cuatro vértices. Como ejemplo, el grafo de utilidad .${\displaystyle K_{3,3}}$es 1-planar, pero no tiene un subgrafo completo de cuatro vértices, por lo que no es un grafo de 4-mapas. ^{[ 1 ]}