En la teoría de grafos geométricos , una rama de las matemáticas, un grafo de cerillas es un grafo que se puede dibujar en el plano de tal manera que sus aristas sean segmentos de línea con longitud uno que no se cruzan entre sí. Es decir, es un grafo que tiene una incrustación que es simultáneamente un grafo de distancia unitaria y un grafo plano . Por esta razón, los grafos de cerillas también se han llamado grafos de distancia unitaria plana . [1] De manera informal, los grafos de cerillas se pueden hacer colocando cerillas que no se cruzan sobre una superficie plana, de ahí el nombre. [2]
Gran parte de la investigación sobre los grafos de cerillas se ha centrado en los grafos regulares , en los que cada vértice tiene el mismo número de vecinos. Este número se denomina grado del grafo.
Los grafos de cerillas regulares pueden tener grado 0, 1, 2, 3 o 4. Los grafos completos con uno, dos y tres vértices (un único vértice, una única arista y un triángulo) son todos grafos de cerillas y son 0-, 1- y 2-regulares respectivamente. El grafo de cerillas 3-regular más pequeño se forma a partir de dos copias del grafo de diamante colocadas de tal manera que los vértices correspondientes estén a una distancia unitaria entre sí; su doble cubierta bipartita es el grafo de prisma de 8 cruces. [2]
En 1986, Heiko Harborth presentó el grafo que se conocería como el grafo de Harborth . Tiene 104 aristas y 52 vértices y es actualmente el ejemplo más pequeño conocido de un grafo de cerillas regular de 4. [3] Es un grafo rígido . [4]
Cada grafo de cerillas regular de 4 elementos contiene al menos 20 vértices. [5] Actualmente se conocen ejemplos de grafos de cerillas regulares de 4 elementos para todos los números de vértices ≥ 52, excepto para 53, 55, 56, 58, 59, 61 y 62. Los grafos con 54, 57, 65, 67, 73, 74, 77 y 85 vértices se publicaron por primera vez en 2016. Para 52, 54, 57, 60 y 64 vértices solo se conoce un ejemplo. De estos cinco grafos, solo el que tiene 60 vértices es flexible, los otros cuatro son rígidos. [6] [7]
No es posible que un grafo de cerillas regular tenga un grado mayor que cuatro. [5] Más fuertemente, cada grafo de cerillas de 3 vértices tiene vértices de grado cuatro o menos. [8] El grafo de cerillas 3-regular más pequeño sin triángulos (circunferencia ≥ 4) tiene 20 vértices, como lo demostraron Kurz y Mazzuoccolo. [9] El ejemplo más pequeño conocido de un grafo de cerillas 3-regular de circunferencia 5 tiene 54 vértices y fue presentado por primera vez por Mike Winkler en 2019. [10]
El número máximo de aristas que puede tener un gráfico de cerillas en los vértices es . [11]
Es NP-difícil probar si un gráfico plano no dirigido dado puede realizarse como un gráfico de cerillas. [12] [13] Más precisamente, este problema está completo para la teoría existencial de los reales . [14] Kurz (2011) proporciona algunos criterios necesarios fácilmente comprobables para que un gráfico sea un gráfico de cerillas, pero estos tampoco son criterios suficientes: un gráfico puede pasar las pruebas de Kurz y aún así no ser un gráfico de cerillas. [15]
También es NP-completo determinar si un gráfico de cerillas tiene un ciclo hamiltoniano , incluso cuando todos los vértices del gráfico tienen coordenadas enteras que se dan como parte de la entrada del problema. [16]
Se conocen los números de grafos de cerillas distintos (no isomorfos) para 1, 2, 3, ... hasta trece aristas; son:
Por ejemplo, los tres gráficos diferentes que se pueden hacer con tres cerillas son un gráfico de garra , un gráfico de triángulo y un gráfico de trayectoria de tres aristas .
La uniformidad de las longitudes de los bordes se ha considerado durante mucho tiempo una cualidad deseable en el dibujo de gráficos , [19] y algunas clases específicas de gráficos planos siempre se pueden dibujar con bordes completamente uniformes.
Todo árbol puede dibujarse de tal manera que, si las aristas de las hojas del árbol se sustituyeran por rayos infinitos, el dibujo dividiría el plano en regiones poligonales convexas, sin ningún cruce. Para un dibujo de este tipo, si las longitudes de cada arista se modifican arbitrariamente, sin cambiar la pendiente de la arista, el dibujo seguirá siendo plano. En particular, es posible elegir que todas las aristas tengan la misma longitud, lo que da como resultado una realización de un árbol arbitrario como un gráfico de cerillas. [20]
Una propiedad similar es válida para los grafos cuadrados , los grafos planares que se pueden dibujar en el plano de tal manera que cada cara acotada es un cuadrilátero y cada vértice se encuentra en la cara no acotada o tiene al menos cuatro vecinos. Estos grafos se pueden dibujar con todas las caras como paralelogramos, de tal manera que si un subconjunto de aristas que son todas paralelas entre sí se alargan o acortan simultáneamente de modo que sigan teniendo todas la misma longitud, entonces no se puede introducir ningún cruce. Esto hace posible normalizar las aristas de modo que todas tengan la misma longitud y obtener una realización de cualquier grafo cuadrado como un grafo de cerillas. [21]
Cada gráfico de cerillas es un gráfico de distancia unitaria . Los gráficos de centavos son los gráficos que se pueden representar mediante tangencias de círculos unitarios no superpuestos. Todo gráfico de centavos es un gráfico de cerillas. Sin embargo, algunos gráficos de cerillas (como el gráfico de cerillas cúbico de ocho vértices de la primera ilustración) no son gráficos de centavos, porque realizarlos como un gráfico de cerillas hace que algunos vértices no adyacentes estén más cerca que la distancia unitaria entre sí.
