Desenha gráficos com poucos vértices "afiados"?

Para uma incorporação planar de um gráfico planar em um plano com arestas retas, defina um vértice como um vértice nítido se o ângulo máximo entre duas arestas consecutivas em torno dele for maior que 180. Ou, em outras palavras, se houver uma linha passando por ele vértice na incorporação, de modo que todas as arestas incidentes nesse vértice estejam em um lado da linha, então o vértice é "agudo", caso contrário, não é. Além disso, vamos nos preocupar apenas com vértices com grau pelo menos 3.

Quero desenhar gráficos planares com poucos vértices afiados. Alguém já estudou esses desenhos antes?

Em particular, quero desenhar gráficos planares com grau máximo 3, de modo que o número de vértices acentuados de grau 3 na incorporação seja e as coordenadas dos vértices possam ser escritas com um número polinomial de bits.$O(\log n)$

Aqui está o que posso encontrar depois de passar algum tempo no Google Scholar:

Minha medida de nitidez de um vértice está relacionada a um conceito já estudado chamado Resolução Angular . Da Wikipedia:

A resolução angular de um desenho de um gráfico refere-se ao ângulo mais nítido formado por duas arestas que se encontram em um vértice comum do desenho.

Assim, um desenho planar com resolução angular torno de vértices de grau 3 será bom para o meu propósito.$\pi/2$

Para um vértice com grau no desenho, a resolução angular ao seu redor pode ser no máximo 2 $d$ .$2\pi/d$

A questão de saber se isso é justo já foi estudada no passado, mas só consigo encontrar resultados assintóticos. Por exemplo, Malitz e Papakostas provam que qualquer gráfico planar com grau máximo pode ser desenhado com uma resolução angular de α d . Mas esse resultado não fornece bons limites para o caso quando d = 3 .$d$$\alpha^d$$d=3$

É possível construir gráficos planares regulares com $\Theta(n)$componentes biconetados (veja, por exemplo, a fig.16 deste documento ), cada um dos quais deve conter pelo menos um vértice acentuado.

Por outro lado, se você precisar de níveis mais altos de conectividade, poderá evitar ter muitos vértices nítidos. Em particular, se você possui um gráfico planar de 3 conexões, ele pode ser desenhado (por exemplo, usando o teorema de Steinitz para encontrar uma representação poliédrica e, em seguida, formando uma projeção em perspectiva) de forma que todas as faces sejam convexas, o que causa apenas a face externa para ser nítida. Porém, todo gráfico planar de 3 conexões pode ser incorporado de tal maneira que a face externa tenha no máximo cinco vértices (o pior caso é um dodecaedro) para que você possa desenhar todos os gráficos planares de 3 conexões (3 regulares ou não) com pelo menos mais cinco vértices afiados.