Jaki jest najprostszy algorytm wielomianowy dla PLANARNOŚCI?

28

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

graph-algorithms co.combinatorics planar-graphs

— domotorp
źródło

1

Myślę, że wielu zgadza się, że najprostszym algorytmem wielomianowym jest algorytm Demoucron, Malgrange i Pertuiset (DMP). Są to podręczniki z algorytmem, które zwykle obejmują (patrz np. Gibbons 1985 lub Bondy & Murty 1976). Czy wystarczy podjąć decyzję o planarności, czy algorytm powinien również generować osadzanie planarne? IIRC artykuł SODA'99 Boyera i Myrvolda @joro prawdopodobnie odnosi się do pomijanych szczegółów, szczególnie dotyczących złożoności czasowej.

— Juho

2

Jeśli chcesz tylko, aby problem decyzyjny JEST PLANARNY, czyż dwóch zakazanych małoletnich, których istnienie można sprawdzić w czasie wielomianowym, nie wystarczy?

— joro

2

@joro: Tak, oczywiście byłoby to proste rozwiązanie, ale wolałbym unikać używania tak silnego twierdzenia.

— domotorp

1

Algorytm, o którym wspomniałem, był w zasadzie algorytmem Auslandera-Partera. Problemem w moim algorytmie była część 7, kiedy powiedziałem, że możemy dwuczęściowy wykres składników. Możemy w oryginalnym algorytmie, ale w algorytmie, o którym mówiłem, że potrzebujemy bardziej precyzyjnych definicji komponentów i nie byłem w stanie wyjaśnić go szczegółowo. Część rekurencyjna była wyraźnie prawdziwa (jeśli możemy zrobić krok 7, to jesteśmy skończeni), w którym wątpisz w jej poprawność. Nie zaktualizowałem mojej odpowiedzi, ponieważ widziałem, że będzie to około dwóch stron i nie mogę jej bardziej skracać i nie jest dobrze nazywać to po prostu.

— Saeed

3

Zmniejszenie do 3-połączonej skrzynki jest koncepcyjnie proste i powinno być wyjaśnione w każdym przypadku. Jeśli nie jesteśmy zbyt zainteresowani wydajnością, można łatwo zredukować obudowę do 3-połączonych. Sprawdź wszystkie cięcia 2-węzłowe.

— Chandra Chekuri

6

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.

Podziel wykres na połączone komponenty.
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 czy jest podłączony. $v$ $G_i$ $G_i-v$
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 czy 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$

Ponosi żadnej cyklu z . $C$ $G$
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 będzie rysunkiem wynikowym; może mieć skrzyżowania. $C$ $D$
Jeśli nie ma skrzyżowań, jesteśmy skończeni. $D$
Weź wierzchołki w dowolnym podłączonym składniku . Ograniczenie do indukowanego podsgrafu powinno być płaskie. W przeciwnym razie nie jest płaskie. Ponosi żadnej twarzy na rysunku ograniczony do indukowanego podgrafu i niech jest cykl określenie . 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 jest cyklem hamiltonowskim, wówczas należy skonstruować za pomocą krawędzi.) $C'$ $C$ $C'$
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 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.

— ktoś
źródło

Zredagowałem odpowiedź, aby uniknąć używania mostów i nakładającego się wykresu.

— ktoś

Załóżmy, że każdy 3-połączony komponent może być osadzony. Co zatem możemy wywnioskować na temat oryginalnego wykresu? Korzystając z tego, że 3 połączone wykresy mają (co najwyżej) jedno osadzenie, prawdopodobnie możemy stąd zakończyć, ale ten krok należy również wykonać.

— domotorp

Na końcu, w kroku 4, czym jest twarz na rysunku niepłaskim? Myślę, że można to jeszcze zdefiniować w naturalny sposób. I na samym końcu „Else G nie jest planarne” rzeczywiście wydaje się dość trywialne.

— domotorp

D

$D$

G [U \cup V (C)]

$G[U\cup V(C)]$

G

$G$

Zgadzamy się w tym, ale nie rozumiem, jak to pomaga.

— domotorp

3

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.

— Mohammad Al-Turkistany
źródło

Nie jestem zainteresowany najnowocześniejszymi algorytmami płaskości, chcę coś łatwego do wyjaśnienia. W książce nie znalazłem też nic prostszego niż algorytm Demoucron, Malgrange i Pertuiset (DMP).

— domotorp

0

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.

— Ari Trachtenberg
źródło

Jest to szybki i nie prosty algorytm.

— domotorp

0

Dwa algorytmy, oba w LogSpace

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

Drugi jest o wiele prostszy niż pierwszy.

— Anonimowy
źródło

To wcale nie jest proste.

— domotorp