Incrustación de gráficos que maximiza el ángulo mínimo

Dado un gráfico plano, uno puede incrustarlo en tiempo lineal cruzando libremente en una cuadrícula . Me interesa saber si se conoce algún algoritmo eficiente para insertar en línea recta un gráfico plano que se cruce libremente en una cuadrícula , para alguna pequeña , de modo que se maximice el ángulo mínimo entre dos bordes. $n \times n$ $n^c \times n^c$ $c$

reference-request graph-theory graph-drawing Peter
fuente

Supongo que está interesado en la inserción en línea recta. De lo contrario, la pregunta es trivial ...

Sariel Har-Peled

sí, estoy interesado en las incrustaciones en línea recta

Peter

Respuestas:

No creo que se conozca tal algoritmo. Los resultados que conozco sobre cómo maximizar el ángulo mínimo en dibujos de líneas rectas de gráficos planos son:

Cada gráfico plano tiene un dibujo (posiblemente no plano) en el que el ángulo mínimo es inversamente proporcional al grado máximo. Para la idea principal de la prueba y algunas referencias, consulte http://11011110.livejournal.com/230133.html
$O(\sqrt{(\log d)/d^3})$
Cada gráfico plano tiene un dibujo plano en el que el ángulo mínimo está delimitado por una función de su grado. Esto se puede mostrar usando el teorema de empaquetamiento circular de Koebe-Andreev-Thurston. Para una referencia a una versión ligeramente más fuerte de este resultado (que muestra que cada gráfico plano de grado acotado tiene un dibujo plano con un número limitado de pendientes de borde) consulte http://11011110.livejournal.com/205447.html

David Eppstein
fuente

α

$\alpha$

α

$\alpha$

Si aún no conoce la incrustación, está completa NP. Específicamente, es difícil determinar si α = π / 2 funcionará. Ver Garg y Tamassia, "Sobre la complejidad computacional de las pruebas de planaridad ascendente y rectilínea", SIAM J. Comput. 2001.

David Eppstein