¿Dibujar gráficos con pocos vértices "afilados"?

Para una incrustación plana de un gráfico plano en un plano con bordes rectos, defina un vértice como un vértice afilado si el ángulo máximo entre dos bordes consecutivos a su alrededor es más de 180. O, en otras palabras, si existe una línea que pase por ese vértice en la incrustación de modo que todos los bordes incidentes en ese vértice se encuentran en un lado de la línea, entonces el vértice está "afilado", de lo contrario no lo es. Además, preocupémonos solo por vértices con un grado de al menos 3.

Quiero dibujar gráficos planos con pocos vértices afilados. ¿Alguien ha estudiado tales dibujos antes?

En particular, quiero dibujar gráficos planos con un grado máximo de 3 de modo que el número de vértices agudos de grado 3 en la incrustación sea y las coordenadas de los vértices se puedan escribir con un número polinómico de bits.$O(\log n)$

Esto es lo que puedo encontrar después de pasar un tiempo en Google Scholar:

Mi medida de nitidez de un vértice está relacionada con un concepto ya estudiado llamado Resolución Angular . De Wikipedia:

La resolución angular de un dibujo de un gráfico se refiere al ángulo más agudo formado por cualquiera de los dos bordes que se encuentran en un vértice común del dibujo.

Por lo tanto, un dibujo plano con resolución angular alrededor de vértices de grado 3 será bueno para mi propósito.$\pi/2$

Para un vértice con grado en el dibujo, la resolución angular a su alrededor puede ser como máximo 2 π / d .$d$$2\pi/d$

La cuestión de si esto es estricto se ha estudiado en el pasado, pero solo puedo encontrar resultados asintóticos. Por ejemplo, Malitz y Papakostas demuestran que cualquier gráfico plano con un grado máximo puede dibujarse con una resolución angular de α d . Pero este resultado no da buenos límites para el caso cuando d = 3 .$d$$\alpha^d$$d=3$

$\Theta(n)$

Por otro lado, si necesita mayores niveles de conectividad, puede evitar tener muchos vértices agudos. En particular, si tiene un gráfico plano conectado a 3, se puede dibujar (por ejemplo, utilizando el teorema de Steinitz para encontrar una representación poliédrica y luego formando una proyección en perspectiva) de tal manera que todas las caras sean convexas, lo que causa solo el cara externa para ser afilada. Pero cada gráfico plano conectado a 3 puede incrustarse de tal manera que la cara externa tenga como máximo cinco vértices (el peor de los casos es un dodecaedro) para que pueda dibujar cada gráfico plano conectado a 3 (3 regulares o no) con La mayoría de los cinco vértices afilados.