Considere el siguiente problema.
Dado: Un gráfico completo con pesos reales no negativos en los bordes.
Tarea: Encuentre un subgrafo plano de peso máximo. ("Máximo" entre todos los subgrafos planos posibles.)
Nota: El subgrafo de peso máximo será una triangulación; Si el gráfico completo está en vértices, tendrá m = 3 n - 6 aristas.
Pregunta: ¿Cuál es el mejor algoritmo disponible para este problema? ¿Cuál es su complejidad temporal?