¿Se puede construir un grafo 3-regular no-1-planar?

Question

A $1$ -Un grafo plano es un grafo que tiene un dibujo en el plano tal que cada arista tiene a lo sumo un cruce.

Utilicé nauty para generar todos los grafos 3-regulares hasta el orden 12, y comprobó cada uno de ellos individualmente. Todos resultaron ser grafos 1-planares.

Mi pregunta es si es posible construir un grafo 3-regular no-1-planar.

Creo que sin duda existe.

También realicé experimentos con grafos con un número de cruces relativamente grande, pero, por desgracia, todos eran grafos de 1 plano. Por ejemplo: El grafo cúbico de 6 cruces más pequeño es el Gráfico de Desargues con 20 vértices.

O ver este enlace para el gráfico hexagonal.

Este problema está relacionado con la pregunta ¿Por qué el número de cruce de Tutte de 12 jaulas es 170? porque sabemos que el número de cruce de un $n$ -grafo plano de orden 1 es menor o igual que $n-2$ (véase [1]).

• [1] Czap J, Hudák D. On drawings and decompositions of 1-planar graphs[J]. the electronic journal of combinatorics, 2013: P54-P54.

Si el número de cruces de la jaula Tutte 12 (126 vértices) es mayor o igual que $125$ entonces es el grafo 3-regular no 1-planar que estamos buscando. Desgraciadamente, parece que el número de cruce de la jaula 12 de Tutte es desconocido. Todavía sería útil si supiéramos un buen límite inferior de Tutte 12-jaula.

---

Edición 1 Como recuerda Joseph O'Rourke, el gráfico de Coxeter es un candidato. La siguiente incrustación es de Wikipedia y casi tiene una incrustación 1-planar , excepto una arista que se cruzará dos veces.

Edita 2: Gracias a Sam Hopkins por el recordatorio, la frase anterior en Edit 1 debe corregirse a: 3 de las aristas se cruzarán dos veces (no sólo una arista).

Answer 1

Para cada $t$ hay $3$ -grafos regulares que no son $t$ -planar. De hecho, un $3$ -regular $n$ -de vértices, para grandes $n$ tiene esta propiedad. Como veremos en la demostración, se puede tomar $n=Ct(\log t)^6$ para una constante absoluta adecuada $C$ .

En efecto, dejemos que $G$ sea un grafo de este tipo y supongamos que admite un $t$ -dibujo plano. Elija un dibujo en el que no haya tres aristas que se crucen en el mismo punto. Añadiendo un vértice en los puntos de intersección, obtenemos un grafo plano $G'$ con un máximo de $3tn$ vértices y como máximo $3tn$ bordes. Grado máximo de $G'$ es como máximo $4$ . Por el teorema del separador Ungar--Lipton--Tarjan, existe un conjunto $S_1$ de $O(\sqrt{tn})$ vértices cuya eliminación divide $G'$ en dos conjuntos de vértices desconectados $V_1$ y $V_2$ de tamaño máximo $2|V(G')|/3$ cada uno.

Supongamos que ambos $|V_1\cap V(G)|$ y $|V_2\cap V(G)|$ son como mínimo $n/r$ (donde $r$ se elegirá más adelante). En este caso, el dibujo de cada arista de $G$ de $V_1\cap V(G)$ a $V_2\cap V(G)$ pasa a través de $S_1$ y hay $\Omega(n/r^2)$ tales bordes en vista de $G$ siendo un gráfico expansivo. Dado que el trazado de cada uno de estos caminos pasa por $S_1$ y ningún vértice de $S_1$ tiene más grado que $4$ se deduce que $n/r^2\leq O(\sqrt{tn})$ es decir, $n=O(r^4 t)$ .

Esto deja el caso cuando uno de $|V_1\cap V(G)|$ o $|V_2\cap V(G)|$ es menor que $n/r$ . Di, $|V_1\cap V(G)|\leq n/100$ . Entonces $|V_2\cap V(G)\geq (1-2/r)n$ . Podemos entonces aplicar el teorema del separador al subgrafo de $G'$ inducida por $V_2$ para encontrar un subconjunto $S_2$ separándolo en $V_2'$ y $V_3$ . De nuevo, si ambos $V_2'$ y $V_3$ contienen $n/r$ vértices de $G$ entonces encontramos $\Omega(n)$ bordes de $G$ cuyo dibujo pasa por $S_1\cup S_2$ . Por lo tanto, podemos suponer que una de las partes, digamos $V_2'$ satisface $|V_2\cap V(G)|\leq n/r$ . A continuación, repetimos el argumento en $V_3$ etc.

En la secuencia anidada $V(G')\supset V_2\supset V_3\supset\dotsb$ cada conjunto siguiente es $\tfrac{2}{3}$ del tamaño del precedente. Así que.., $|V_{\ell}|=O\bigl( (\tfrac{2}{3})^\ell tn\bigr)$ que contradice $|V_{\ell}\cap V(G)|\geq (1-2\ell/r)n$ si $\ell=r/4$ y $r=20\log t$ . Por lo tanto, en algún paso debemos tener $\Omega(n/r^2)\leq |S_1|+\dotsb+|S_i|\leq O(i\sqrt{tn})$ es decir, $n=O(r^6 t)=O\bigl(t(\log t)^6\bigr)$ .

El poder de $\log t$ es probablemente mejorable con una elección más cuidadosa de los parámetros y de los separadores.

Answer 2

Lo que sigue es exagerado comparado con la respuesta de Boris Bukh, pero te dará un ejemplo más determinista.

Lo ha demostrado Bonamy et al. que 1-planar (más aún, (g,k)-planar para cualquier género $g$ y $k\in \mathbb{N}$ ) los gráficos tienen dimensión asintótica como máximo 2 (Corolario 1.6). Por otro lado, conocemos multitud de grafos 3-regulares con dimensión asintótica >2. Para un ejemplo concreto, tomemos la red cúbica $\mathbb{Z^3}$ . Es 6-regular, pero se puede inflar cada vértice en un árbol subcúbico para hacerlo 3-regular sin afectar a su dimensión asintótica, que es 3. Este gráfico $G$ es infinito, pero se puede utilizar un argumento de compacidad para deducir que para un tamaño suficientemente grande $n$ la bola de radio $n$ en $G$ no es $k$ -planar.

Se podría intentar demostrar esto directamente, descomponiendo una porción de $G$ en "rebanadas" planas, cada una de las cuales está conectada por 3 y, por lo tanto, se incrusta de forma esencialmente única en $\mathbb{S}^2$ . Así, cada corte se cruzará mucho con otros cortes.

Answer 3

¿Ha comprobado el Gráfico de Coxeter ?