Osadzanie wykresów, które maksymalizuje minimalny kąt

Biorąc pod uwagę wykres płaski, można go osadzić w liniowym czasie przechodzącym swobodnie w siatkę . Interesuje mnie, czy znane są efektywne algorytmy linii prostej osadzającej płaski wykres przecinający się swobodnie w siatce n c × n c , dla jakiegoś małego c , tak, że minimalny kąt między dwiema krawędziami jest maksymalizowany?$n \times n$$n^c \times n^c$$c$

Nie sądzę, aby taki algorytm był znany. Wyniki, które znam na temat maksymalizacji minimalnego kąta na rysunkach prostych wykresów płaskich:

1. Każdy wykres płaski ma (prawdopodobnie nieplanarny) rysunek, na którym minimalny kąt jest odwrotnie proporcjonalny do maksymalnego stopnia. Aby zapoznać się z głównym pomysłem na dowód i kilkoma referencjami, zobacz http://11011110.livejournal.com/230133.html

2. $O(\sqrt{(\log d)/d^3})$

3. Każdy wykres płaski ma rysunek płaski, na którym minimalny kąt jest ograniczony funkcją jego stopnia. Można to wykazać za pomocą twierdzenia o pakowaniu w koło Koebe-Andreev-Thurston. Odniesienie do nieco silniejszej wersji tego wyniku (pokazującej, że każdy płaski wykres stopnia ograniczonego ma płaski rysunek z ograniczoną liczbą nachyleń krawędzi), patrz http://11011110.livejournal.com/205447.html