Resolución angular (dibujo de gráficos)

Formann et al. (1993) observaron que cada dibujo lineal de un grafo con grado máximo d tiene una resolución angular como máximo de 2π/ d : si v es un vértice de grado d , entonces las aristas incidentes a v dividen el espacio alrededor de v en d cuñas con un ángulo total de 2π , y la más pequeña de estas cuñas debe tener un ángulo de como máximo 2π/ d . Más fuertemente, si un grafo es d - regular , debe tener una resolución angular menor que${\displaystyle {\frac {\pi }{d-1}}}$, porque esta es la mejor resolución que se puede lograr para un vértice en la envoltura convexa del dibujo.

Como demostraron Formann et al ^. (1993) , la mayor resolución angular posible de un grafo G está estrechamente relacionada con el número cromático del cuadrado G₂ , el grafo sobre el mismo conjunto ^de vértices en el que pares de vértices están conectados por una arista siempre que su distancia en G sea como máximo dos. Si G₂ se puede colorear con χ colores, entonces G se puede dibujar con una resolución angular π/ χ  −  ε , para cualquier ε > 0 , asignando colores distintos a los vértices de un χ -gono regular y colocando cada vértice de G cerca del vértice del polígono con el mismo color. Usando esta construcción, demostraron que todo grafo con grado máximo d tiene un dibujo con una resolución angular proporcional a 1/ d² ^. Esta cota es casi exacta: utilizaron el método probabilístico para demostrar la existencia de grafos con grado máximo d cuyos dibujos tienen todos una resolución angular${\displaystyle O\left({\frac {\log d}{d^{2}}}\right)}$.

Formann et al. (1993) proporcionaron un ejemplo que muestra que existen grafos que no tienen un dibujo que alcance la máxima resolución angular posible; en cambio, estos grafos tienen una familia de dibujos cuyas resoluciones angulares tienden a algún valor límite sin alcanzarlo. Específicamente, exhibieron un grafo de 11 vértices que tiene dibujos de resolución angular π/3 − ε para cualquier ε > 0 , pero que no tiene un dibujo de resolución angular exactamente π/3 .

Cada árbol puede dibujarse de forma que las aristas estén espaciadas uniformemente alrededor de cada vértice, una propiedad conocida como resolución angular perfecta . Además, si las aristas pueden permutarse libremente alrededor de cada vértice, entonces es posible realizar dicho dibujo sin cruces, con todas las aristas de longitud unitaria o superior, y con todo el dibujo dentro de un cuadro delimitador de área polinómica . Sin embargo, si el orden cíclico de las aristas alrededor de cada vértice ya está determinado como parte de la entrada del problema, entonces lograr una resolución angular perfecta sin cruces puede requerir a veces un área exponencial. ^{[ 1 ]}

La resolución angular perfecta no siempre es posible para los grafos exteriores planares , ya que los vértices en la envoltura convexa del dibujo con grado mayor que uno no pueden tener sus aristas incidentes igualmente espaciadas a su alrededor. No obstante, todo grafo exterior planar de grado máximo d tiene un dibujo exterior planar con resolución angular proporcional a 1/ d . ^{[ 2 ]}

Para grafos planares con grado máximo d , la técnica de coloración de cuadrados de Formann et al. (1993) proporciona un dibujo con resolución angular proporcional a 1/ d , porque el cuadrado de un grafo planar debe tener un número cromático proporcional a d . Más precisamente, Wegner conjeturó en 1977 que el número cromático del cuadrado de un grafo planar es como máximo${\displaystyle \max \left(d+5,{\frac {3d}{2}}+1\right)}$y se sabe que el número cromático es como máximo${\displaystyle {\frac {5d}{3}}+O(1)}$. ^{[ 3 ]} Sin embargo, los dibujos resultantes de esta técnica generalmente no son planos.

^{Para algunos grafos planares, la resolución angular óptima de un dibujo de} línea recta planar es O(1/ d³ ) , donde d es el grado del grafo. ^{[ 4 ]} Además, dicho dibujo puede verse forzado a usar aristas muy largas, más largas por un factor exponencial que las aristas más cortas en el dibujo. Malitz y Papakostas (1994) utilizaron el teorema de empaquetamiento de círculos y el lema del anillo para demostrar que todo grafo planar con grado máximo d tiene un dibujo planar cuya resolución angular es, en el peor de los casos, una función exponencial de d , independiente del número de vértices en el grafo.