Grafikeinbettung, die den minimalen Winkel maximiert

Bei einem ebenen Graphen kann man ihn in linearen Zeitübergängen frei in ein Gitter einbetten . Ich bin interessiert , ob irgendwelche effiziente Algorithmen zur geraden Linie einzubetten frei in eine Kreuzung mit einer ebenen Graphen bekannt sind N c × n c Gitter, für einige kleine c , so dass der minimale Winkel zwischen zwei Kanten maximiert wird?$n \times n$$n^c \times n^c$$c$

Ich glaube nicht, dass ein solcher Algorithmus bekannt ist. Die Ergebnisse, die ich über das Maximieren des Mindestwinkels in geraden Linienzeichnungen von ebenen Graphen weiß, sind:

1. Jeder ebene Graph hat eine (möglicherweise nicht ebene) Zeichnung, in der der minimale Winkel umgekehrt proportional zum maximalen Grad ist. Die wichtigsten Beweise und einige Referenzen finden Sie unter http://11011110.livejournal.com/230133.html

2. Es gibt ebene Graphen des Grades d, so dass der minimale Winkel in jeder ebenen Geradenzeichnung . Dieses Ergebnis geht auf Garg und Tamassia, "Planare Zeichnungen und Winkelauflösung: Algorithmen und Grenzen", ESA '94, zurück. Sie zeigen auch, dass für das Erreichen nahezu optimaler Winkel mit einer Rasterzeichnung ein Raster mit exponentieller Fläche erforderlich sein kann.$O(\sqrt{(\log d)/d^3})$

3. Jeder ebene Graph hat eine ebene Zeichnung, in der der minimale Winkel durch eine Funktion seines Grades begrenzt ist. Dies kann mit dem Koebe-Andreev-Thurston-Kreispackungssatz gezeigt werden. Eine Referenz zu einer etwas stärkeren Version dieses Ergebnisses (die zeigt, dass jedes ebene Diagramm mit begrenztem Grad eine ebene Zeichnung mit einer begrenzten Anzahl von Kantensteigungen hat) finden Sie unter http://11011110.livejournal.com/205447.html