Embedding grafik yang memaksimalkan sudut minimum

Mengingat grafik planar, satu kaleng menanamkan dalam waktu linier menyeberang bebas ke dalam jaringan. Saya tertarik apakah ada algoritma yang efisien diketahui garis lurus menanamkan grafik planar menyeberang bebas ke dalam n c × n c grid, untuk beberapa c kecil , sehingga sudut minimum antara dua sisi dimaksimalkan?$n \times n$$n^c \times n^c$$c$

Saya tidak berpikir algoritma seperti itu diketahui. Hasil yang saya tahu tentang memaksimalkan sudut minimum dalam gambar garis lurus grafik planar adalah:

1. Setiap grafik planar memiliki gambar (mungkin nonplanar) di mana sudut minimum berbanding terbalik dengan tingkat maksimum. Untuk ide bukti utama dan beberapa referensi, lihat http://11011110.livejournal.com/230133.html

2. Ada grafik planar derajat d sehingga sudut minimum dalam gambar garis planar lurus adalah $O(\sqrt{(\log d)/d^3})$. Hasil ini disebabkan oleh Garg dan Tamassia, "Gambar planar dan resolusi sudut: algoritma dan batas", ESA '94. Mereka juga menunjukkan bahwa mencapai sudut yang hampir optimal dengan gambar kotak mungkin memerlukan kotak area eksponensial.

3. Setiap grafik planar memiliki gambar planar di mana sudut minimum dibatasi oleh fungsi derajatnya. Ini dapat ditunjukkan dengan menggunakan teorema pengepakan lingkaran Koebe-Andreev-Thurston. Untuk referensi ke versi yang sedikit lebih kuat dari hasil ini (menunjukkan bahwa setiap grafik planar derajat terikat memiliki gambar planar dengan jumlah lereng tepi terbatas) lihat http://11011110.livejournal.com/205447.html