Jaki jest najprostszy algorytm wielomianowy dla PLANARNOŚCI?

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).$K_5$$K_{3,3}$

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ń.

Opiszę algorytm. Nie jestem pewien, czy kwalifikuje się jako „łatwy”, a niektóre dowody nie są takie łatwe.

Najpierw dzielimy wykres na 3 połączone elementy, jak wspomniała Chandra Chekuri.

1. Podziel wykres na połączone komponenty.
2. Podziel każdy podłączony komponent na 2 połączone elementy. Można tego dokonać podczas sprawdzania czasu wielomianu dla każdego wierzchołka każdego 2 połączonego komponentu G i, czy G i - v jest podłączony.$v$$G_i$$G_i-v$
3. Podziel każdy 2 połączony komponent na 3 połączone komponenty. Można tego dokonać w wielomianowym sprawdzaniu czasu dla dwóch różnych wierzchołków każdego 2 połączonego komponentu G i, czy G i - { v , u } jest połączone.$v,u$$G_i$$G_i-\{ v,u \}$

Problem zredukowaliśmy do sprawdzania, czy 3-połączony element wykresu jest płaski. Niech oznacza 3-połączony komponent.$G$

1. Ponosi żadnej cyklu z G .$C$$G$
2. Przypnij wierzchołki jako wierzchołki wypukłego wielokąta. Umieść każdy z pozostałych wierzchołków w centrum barów sąsiadów. Prowadzi to do układu równań liniowych określających współrzędne każdego wierzchołka. Niech D będzie rysunkiem wynikowym; może mieć skrzyżowania.$C$$D$
3. Jeśli nie ma skrzyżowań, jesteśmy skończeni.$D$
4. Weź wierzchołki w dowolnym podłączonym składniku G - V ( C ) . Ograniczenie D do indukowanego podsgrafu G [ U ∪ V ( C ) ] powinno być płaskie. W przeciwnym razie G nie jest płaskie. Ponosi żadnej twarzy F na rysunku D ograniczony do indukowanego podgrafu G [ U ∪ V ( C ) ] i niech C " jest cykl określenie F . Jeśli $U$$G-V(C)$$D$$G[U\cup V(C)]$$G$$F$$D$$G[U\cup V(C)]$$C'$$F$$G$ma być płaski, wówczas musi być cyklem twarzy. (Gdy C jest cyklem hamiltonowskim, wówczas C ' należy skonstruować za pomocą krawędzi.)$C'$$C$$C'$
5. Powtórz krok 2, używając C 'zamiast C. Jeśli wynikowy rysunek jest płaski, wówczas jest płaski. W przeciwnym razie G nie jest planarna.$G$$G$

Uwagi:

• Twierdzenie, że osadzenie sprężynowe Tutte daje osadzenie planarne, nie jest proste. Podobała mi się prezentacja w książce Edelsbrunner and Harer, Computational Topology, ale dotyczy to tylko triangulacji. Colin de Verdiere omawia wiosenne osadzanie w http://www.di.ens.fr/~colin/cours/algo-graphs-surfaces.pdf , sekcja 1.4. Ogólnym odniesieniem są Linial, Lovász, Wigderson: Gumki, wypukłe osadzenia i łączność graficzna. Combinatorica 8 (1): 91-102 (1988).
• Rozwiązanie liniowego układu równań w wielomianowej liczbie operacji arytmetycznych jest łatwe dzięki eliminacji Gaussa. Rozwiązanie go za pomocą wielomianowej liczby bitów nie jest takie łatwe.

Algorytm Boyera i Myrvolda zaliczany jest do najnowocześniejszych algorytmów testowania płaskości

W czołówce: Uproszczona O (n) Planarność dzięki dodaniu krawędzi przez Boyera i Myrvolda.

Ten rozdział książki analizuje wiele algorytmów testowania płaskości i mam nadzieję, że znajdziesz wystarczająco prosty algorytm.

Co z algorytmem Hopcroft i Tarjana z 1974 r. {1} ?

{1} Hopcroft, John i Robert Tarjan. „Skuteczne testowanie płaskości”. Journal of the ACM (JACM) 21.4 (1974): 549-568.

Dwa algorytmy, oba w LogSpace

1. Eric Allender i Meena Mahajan - Złożoność testowania planarności
2. Samir Datta i Gautam Prakriya - Ponownie testowanie planarności

Drugi jest o wiele prostszy niż pierwszy.