Dessiner des graphiques avec quelques sommets «nets»?

Pour une incorporation plane d'un graphique plan sur un plan à bords droits, définissez un sommet comme un sommet net si l'angle maximum entre deux bords consécutifs autour de lui est supérieur à 180. Ou en d'autres termes, s'il existe une ligne passant par ce sommet dans l'incorporation de telle sorte que toutes les arêtes incidentes sur ce sommet se trouvent sur un côté de la ligne, alors le sommet est "net" sinon il ne l'est pas. Aussi, ne nous inquiétons que des sommets de degré au moins 3.

Je veux dessiner des graphiques plans avec quelques sommets nets. Quelqu'un a-t-il déjà étudié de tels dessins?

En particulier, je veux dessiner des graphes planaires avec un degré 3 maximum de telle sorte que le nombre de sommets nets de degré 3 dans l'incorporation soit et que les coordonnées des sommets puissent être écrites avec un nombre polynomial de bits.$O(\log n)$

Voici ce que je peux trouver après avoir passé du temps sur Google Scholar:

Ma mesure de la netteté d'un sommet est liée à un concept déjà étudié appelé la résolution angulaire . De Wikipédia:

La résolution angulaire d'un dessin d'un graphique se réfère à l'angle le plus net formé par deux arêtes qui se rencontrent à un sommet commun du dessin.

Ainsi, un dessin planaire avec une résolution angulaire autour des sommets de degré 3 sera bon pour mon but.$\pi/2$

Pour un sommet de degré sur le dessin, la résolution angulaire autour peut être au maximum de .$d$$2\pi/d$

La question de savoir si cela est serré a été étudiée dans le passé, mais je ne peux trouver que des résultats asymptotiques. Par exemple, Malitz et Papakostas prouvent que tout graphe planaire avec un degré maximum peut être tracé avec une résolution angulaire de . Mais ce résultat ne donne pas de bonnes limites pour le cas où .$d$$\alpha^d$$d=3$

$\Theta(n)$

En revanche, si vous avez besoin de niveaux de connectivité plus élevés, vous pouvez éviter d'avoir de nombreux sommets nets. En particulier, si vous avez un graphe planaire à 3 connexions, il peut être dessiné (par exemple en utilisant le théorème de Steinitz pour trouver une représentation polyédrique puis en formant une projection en perspective) de telle sorte que toutes les faces soient convexes, ce qui ne provoque que la la face externe doit être nette. Mais chaque graphe planaire à 3 connexions peut être intégré de manière à ce que la face externe ait au plus cinq sommets (le pire des cas étant un dodécaèdre), vous pouvez donc dessiner chaque graphe planaire à 3 connexions (3 régulières ou non) avec au moins cinq sommets nets.