Istnieje kilka algorytmów, które decydują w czasie wielomianowym, czy wykres może być narysowany w płaszczyźnie, czy nie, nawet wiele z czasem liniowym. Jednak nie mogłem znaleźć bardzo prostego algorytmu, który można łatwo i szybko wyjaśnić na zajęciach i pokazać, że PLANARNOŚĆ znajduje się w P. Czy znasz jakiś?
Jeśli to konieczne, możesz użyć twierdzenia Kuratowskiego lub Fary'ego, ale nie głębokich rzeczy, takich jak twierdzenie o grafie mniejszym. Zauważ też, że nie dbam o czas działania, chcę tylko coś wielomianowego.
Poniżej znajdują się 3 najlepsze jak dotąd algorytmy, pokazujące kompromis pomiędzy prostotą / brakiem głębokiej teorii.
Algorytm 1: Korzystając z tego, możemy sprawdzić, czy wykres zawiera lub K 3 , 3 jako niewielki w czasie wielomianowym, otrzymujemy bardzo prosty algorytm wykorzystujący głęboką teorię. (Zauważ, że teoria ta już wykorzystuje osadzanie grafów, jak wskazał Saeed, więc nie jest to prawdziwe podejście algorytmiczne, po prostu coś prostego do powiedzenia uczniom, którzy już znali / przyjęli twierdzenie o grafie mniejszym).
Algorytm 2 [na podstawie czyjejś odpowiedzi]: Łatwo zauważyć, że wystarczy poradzić sobie z 3-połączonymi wykresami. W tym celu znajdź twarz, a następnie zastosuj wiosenne twierdzenie Tutte'a.
Algorytm 3 [zalecany przez Juho]: algorytm Demoucron, Malgrange i Pertuiset (DMP). Narysuj cykl, składniki pozostałego wykresu nazywamy fragmentami, osadzamy je w odpowiedni sposób (tymczasem tworząc nowe fragmenty). Podejście to nie wykorzystuje innych twierdzeń.