Ancho de ruta del dibujo planarizado de

El pathwidth del grafo bipartito completo $K_{3,n}$ con conjuntos tripartitos de tamaño $3$ y $n$ es como máximo $3$ . Estoy interesado en planificar este gráfico mediante el siguiente proceso:

1. Dibújalo en el plano de modo que ningún borde contenga un vértice en su interior y que no se crucen más de 2 bordes en ningún punto.
2. Reemplace cada punto de cruce de dos bordes por un nuevo vértice de grado 4.

Entonces el gráfico resultante es claramente plano. Si bien $K_{3,n}$ tiene un ancho de ruta constante, algunas investigaciones preliminares sugieren que, independientemente del dibujo que utilice para planarizar $K_{3,n}$ , no puede garantizar que el gráfico planarizado tenga un ancho de ruta constante independiente de $n$ ; Creo que el ancho de ruta del gráfico planarizado debe crecer con $n$ . ¿Es esto conocido o implicado por algún resultado existente?

Por otro lado, tengo una familia de gráficos de grado constante y ancho de ruta limitado, que puedo planificar sin aumentar el ancho de ruta en más de una constante. ¿Existe un resultado general que indique que esto siempre es posible para gráficos de grado acotado y ancho de ruta?

$K_{3,n}$$O(n)$$\Omega(n)$

$K_{3,n}$$K_{3,3}$$K_{3,n}$$n-2$$K_{3,3}$$\tbinom{n}{3}$ $K_{3,3}$$n^2/6$. (En realidad, se conoce un límite estrecho de aproximadamente 2/4, pero no cambia el resto).$n^2/4$

(2) Establezca como el conjunto de todas las aristas en , y considere cualquier disposición lineal de los cruces en todo el dibujo. Repita los siguientes pasos:$S$$K_{3,n}$

(2a) Considere el punto de que arreglo que biseca los cruces entre pares de bordes en . Defina un borde de para que se "corte" si todos sus puntos de cruce con otros bordes en están en la misma mitad de esta bisección, y "sin cortar" de lo contrario.$S$$S$$S$

(2b) Si hay al menos bordes de corte del dibujo (para alguna constante adecuada ), entonces cada uno de ellos contribuye con un borde de la planarización que también cruza el punto de bisección de la disposición lineal. Esto muestra que la disposición lineal tiene un número de separación de vértices , pero dado que el ancho de ruta es solo el número mínimo de separación de vértices de una disposición lineal, el ancho de ruta también es .$\epsilon n$$\epsilon$$\Omega(n)$$\Omega(n)$

(2c) En el caso restante, hay muy pocos bordes cortados, por lo que la mayoría de los cruces en provienen de pares de bordes sin cortar, que deben estar en el mismo lado de la bisección. Casi la mitad de la - cruces están en cada lado de la bisección, y al menos uno de los dos lados de la bisección tiene menos de la mitad de los bordes en . Reemplace por el subconjunto de bordes en ese lado y repita.$S$$S$$S$$S$$S$

(3) Cada repetición de los pasos (2a) - (2c) duplica aproximadamente la densidad de cruces / pares de bordes en , porque el número de cruces se reduce a la mitad y el número de pares de bordes se divide en cuartos. Esta densidad ya comienza constante y no puede exceder uno. Por lo tanto, después de un número constante de repeticiones, el paso (2b) logrará encontrar un número lineal de bordes cortados, lo que muestra que el ancho de ruta es al menos lineal.$S$

En cuanto a su sugerencia de que los gráficos de ancho limitado de ruta limitada tienen diseños cuya planarización tiene ancho de ruta limitado: esto parece ser cierto.

Encuentre un orden lineal de los vértices del gráfico dado con un número de separación de vértices acotado: es decir, en cada punto de un barrido de izquierda a derecha del orden debería haber finitamente muchos vértices a la izquierda del punto de barrido que tienen vecinos al Derecha. Dibuje el gráfico en un barrido de izquierda a derecha de este orden, con sus bordes colocados en pistas horizontales, con cada uno de los vértices parcialmente completados que tengan un conjunto de pistas para que sus bordes restantes se conecten a la derecha. Por lo tanto, el número total de pistas es el producto del grado con el ancho de ruta,$O(1)$$O(1)$. Cuando alcanza un nuevo vértice, puede agregar conectores casi verticales a las pistas de otros vértices que deberían estar conectados a él, y conexiones más cortas a sus pistas salientes. Aquí hay un ejemplo, con la separación de vértices número tres, grado tres y tres pistas por vértice.

Este diseño también tiene un número de separación acotado, porque los únicos cruces están en las pistas, por lo que puede haber como máximo un vértice con una vecindad incompleta por pista. Por lo tanto, el ancho de ruta de la planarización también es , y más precisamente como máximo proporcional al producto del grado y el ancho de ruta original.$O(1)$