La conjetura de Harborth

En matemáticas , la conjetura de Harborth afirma que todo grafo planar tiene un dibujo planar en el que cada arista es un segmento recto de longitud entera . ^{[ 1 ] [ 2 ] [ 3 ]} Esta conjetura lleva el nombre de Heiko Harborth y (de ser cierta) fortalecería el teorema de Fáry sobre la existencia de dibujos de líneas rectas para todo grafo planar. Por esta razón, un dibujo con longitudes de arista enteras también se conoce como incrustación de Fáry integral . ^{[ 4 ]} A pesar de las numerosas investigaciones posteriores, la conjetura de Harborth sigue sin resolverse . ^{[ 5 ]}

Aunque no se sabe con certeza si la conjetura de Harborth es cierta para todos los grafos planares, se ha demostrado para varios tipos especiales de grafos planares.

Una clase de grafos que tienen incrustaciones de Fáry enteras son los grafos que se pueden reducir al grafo vacío mediante una secuencia de operaciones de dos tipos:

• Eliminar un vértice de grado como máximo dos.
• Reemplazar un vértice de grado tres por una arista entre dos de sus vecinos . (Si ya existe dicha arista, el vértice de grado tres puede eliminarse sin añadir otra arista entre sus vecinos).

Para un grafo de este tipo, se puede construir una incrustación de Fáry racional de forma incremental revirtiendo este proceso de eliminación y reinsertando los vértices que se eliminaron. La reinserción de un vértice de grado dos utiliza el hecho de que el conjunto de puntos que están a una distancia racional de dos puntos dados son densos en el plano. La reinserción de un vértice de grado tres utiliza el hecho de que, si tres puntos tienen una distancia racional entre un par y una distancia de raíz cuadrada de la distancia racional entre los otros dos pares, entonces los puntos a distancias racionales de los tres son nuevamente densos en el plano. ^{[ 6 ] [ 7 ]} Las distancias en dicha incrustación se pueden convertir en enteros escalando la incrustación por un factor apropiado. Basándose en esta construcción, los grafos que se sabe que tienen incrustaciones de Fáry integrales incluyen los grafos planares bipartitos , los grafos planares (2,1)-dispersos , los grafos planares de ancho de árbol como máximo  3 y los grafos de grado como máximo cuatro que contienen un subgrafo diamante o no son 4-aristas-conectados . ^{[ 4 ] [ 8 ] [ 9 ]}

En particular, los grafos que pueden reducirse al grafo vacío eliminando únicamente vértices de grado como máximo dos (los grafos planares 2-degenerados ) incluyen tanto los grafos exteriores planares como los grafos serie-paralelo . Sin embargo, para los grafos exteriores planares es posible una construcción más directa de incrustaciones de Fáry integrales, basada en la existencia de subconjuntos infinitos del círculo unitario en los que todas las distancias son racionales. ^{[ 10 ]}

Además, se conocen incrustaciones de Fáry integrales para cada uno de los cinco sólidos platónicos . ^{[ 3 ]}

Una versión más fuerte de la conjetura de Harborth, planteada por Kleber (2008) , pregunta si todo grafo planar tiene un dibujo planar en el que las coordenadas de los vértices y las longitudes de las aristas son todas enteras. ^{[ 11 ]} Se sabe que es cierto para grafos 3-regulares , ^{[ 12 ]} para grafos que tienen grado máximo  4 pero no son 4-regulares, ^{[ 13 ]} y para 3-árboles planares . ^{[ 13 ]}

Otro problema sin resolver en geometría , el problema de Erdős-Ulam , se refiere a la existencia de subconjuntos densos del plano en los que todas las distancias son números racionales. Si existiera tal subconjunto, formaría un conjunto de puntos universal que podría usarse para dibujar todos los grafos planares con longitudes de arista racionales (y, por lo tanto, después de escalarlos adecuadamente, con longitudes de arista enteras). Sin embargo, Ulam conjeturó que no existen conjuntos densos de distancias racionales. ^{[ 14 ]} Según el teorema de Erdős-Anning , no pueden existir conjuntos de puntos infinitos no colineales con todas las distancias siendo enteras. Esto no descarta la existencia de conjuntos con todas las distancias racionales, pero sí implica que en cualquier conjunto de este tipo los denominadores de las distancias racionales deben crecer arbitrariamente grandes.

• Triángulo entero , una incrustación de Fáry integral del grafo triangular
• Gráfico de cerillas , un gráfico que se puede dibujar en un plano con todas las longitudes de los bordes iguales a  1.
• Grafo de Erdős-Diofántico , un grafo completo con distancias enteras que no puede extenderse a un grafo completo mayor con la misma propiedad.
• Ladrillo de Euler , un problema de realización de distancia entera en tres dimensiones.