En primer lugar, los gráficos planos constituyen una clase de gráficos bastante simple, mucho más simple que la clase de todos los gráficos. Entonces, como lo hace con frecuencia la ciencia, si algún problema algorítmico no puede resolverse eficientemente para todas las entradas interesantes, al menos podemos esforzarnos por resolverlo para algunas de las entradas. De hecho, muchos problemas que son NP-difíciles para los gráficos generales se vuelven para poseer algoritmos de tiempo polinomial cuando están restringidos a gráficos planos (debido a su escasez y muchas propiedades estructurales interesantes). Un ejemplo de este problema clásico es MAX-CUT. [Por otro lado, algunos problemas siguen siendo NP-hard incluso para gráficos planos, por ejemplo, variantes del problema COLORING.] El Teorema del separador plano debido a Lipton y Tarjan ayuda a diseñar algoritmos de tipo dividir y conquistar para gráficos planos.
En segundo lugar, la planaridad es una de las nociones centrales de toda la teoría de grafos, por lo que solo desde el punto de vista teórico es interesante considerar los grafos planos en el marco algorítmico. Por ejemplo, si bien hay un montón de algoritmos existentes para probar la planaridad del gráfico (con complejidad lineal de tiempo), el tema aún se está investigando y se están descubriendo nuevas optimizaciones y simplificaciones.
Aunque es casi estructuralmente simple, los gráficos planos no deben considerarse no aplicables a la vida real. Por ejemplo, la tarea de un diseño de circuito electrónico grande emplea un diseño de gráfico plano, algoritmos para dividir un gráfico general en componentes planos, etc. Muchos algoritmos para dibujar gráficos, aunque apuntan a gráficos no planos, tienen un núcleo orientado a planos, es decir, intente para hacer un gráfico de entrada plano, luego dibujarlo y luego volver al gráfico original.
- ¿Cuáles son algunos buenos libros sobre arquitectura de computadoras para principiantes?
- ¿De qué maneras puedes representar más de [matemática] 2 ^ n [/ matemática] utilizando solo [matemática] n [/ matemática] bits?
- ¿Cuál es el RPM del esquema de copia de Excel?
- ¿El aprendizaje automático aplicado se convertirá en una víctima de su propio éxito?
- ¿Cómo es tomar 6.253 (Análisis y optimización convexos) en el MIT?
