Incorporação de gráficos que maximiza o ângulo mínimo

Dado um gráfico planar, uma lata incorporá-lo em tempo linear passando livre em um grade. Estou interessado em saber se algum algoritmo eficiente é conhecido por incorporar em linha reta um gráfico planar cruzando livremente em uma grade , para alguns pequenos , de modo que o ângulo mínimo entre duas arestas seja maximizado? $n \times n$ $n^c \times n^c$ $c$

reference-request graph-theory graph-drawing Pedro
fonte

Suponho que você esteja interessado em incorporação em linha reta. Caso contrário, a pergunta é trivial ...

Sariel Har-Peled

sim, eu estou interessado em embeddings linha reta

Peter

Respostas:

Eu não acho que esse algoritmo seja conhecido. Os resultados que eu sei sobre maximizar o ângulo mínimo em desenhos de linhas retas de gráficos planares são:

Todo gráfico plano possui um desenho (possivelmente não-plano) no qual o ângulo mínimo é inversamente proporcional ao grau máximo. Para a idéia principal da prova e algumas referências, consulte http://11011110.livejournal.com/230133.html
$O(\sqrt{(\log d)/d^3})$
Todo gráfico plano possui um desenho plano no qual o ângulo mínimo é delimitado por uma função de seu grau. Isso pode ser demonstrado usando o teorema de empacotamento circular de Koebe-Andreev-Thurston. Para uma referência a uma versão um pouco mais forte desse resultado (mostrando que todo gráfico planar de grau delimitado possui um desenho planar com um número limitado de inclinações de arestas), consulte http://11011110.livejournal.com/205447.html

David Eppstein
fonte

α

$\alpha$

α

$\alpha$

Se você ainda não conhece a incorporação, é NP-completo. Especificamente, é difícil determinar se α = π / 2 funcionará. Veja Garg e Tamassia, "Sobre a complexidade computacional dos testes de planaridade para cima e retilíneo", SIAM J. Comput. 2001.

David Eppstein