Testy płaskości — Planarity testing
W teorii wykres The płaskość testowania problemem jest algorytmiczne problem testowania, czy dana wykres jest wykresem płaska (to znaczy czy może być sporządzony w płaszczyźnie bez przecięcia krawędzi). Jest to dobrze zbadany problem w informatyce, dla którego powstało wiele praktycznych algorytmów , wiele wykorzystujących nowatorskie struktury danych . Większość z tych metod działa w czasie O ( n ) (czasie liniowym), gdzie n to liczba krawędzi (lub wierzchołków) grafu, która jest asymptotycznie optymalna. Zamiast być pojedynczą wartością logiczną, wynikiem algorytmu testowania planarności może być osadzanie grafu planarnego , jeśli graf jest planarny, lub przeszkoda dla planarności, taka jak podwykres Kuratowskiego, jeśli tak nie jest.
Kryteria płaskości
Algorytmy testowania planarności zazwyczaj wykorzystują twierdzenia z teorii grafów, które charakteryzują zbiór grafów planarnych w kategoriach niezależnych od rysunków grafów. Obejmują one
- Twierdzenie Kuratowskiego że wykres jest płaski tylko wtedy, gdy nie zawierają podgrafu który jest podpodział na K 5 (The zakończeniu wykres pięć wierzchołków ) lub K 3,3 (z wykresu użytkowego , A zakończeniu dwustronnego wykres na sześciu wierzchołkach, z których trzy łączą się z każdym z pozostałych trzech).
- Twierdzenie Wagnera, że graf jest planarny wtedy i tylko wtedy, gdy nie zawiera drobnego (podgrafu skrócenia), który jest izomorficzny z K 5 lub K 3,3 .
- Fraysseix-Rosenstiehl kryterium płaskość , charakteryzując grafach planarnych w kategoriach kolejności od lewej do prawej krawędzi w przeszukiwanie w głąb drzewa.
Kryterium płaskości Fraysseixa-Rosenstiehla może być stosowane bezpośrednio jako część algorytmów do testowania płaskości, natomiast twierdzenia Kuratowskiego i Wagnera mają zastosowanie pośrednie: jeśli algorytm może znaleźć kopię K 5 lub K 3,3 na danym grafie, może być upewnij się, że wykres wejściowy nie jest płaski i zwraca się bez dodatkowych obliczeń.
Inne kryteria planarności, które matematycznie charakteryzują grafy planarne, ale są mniej istotne dla algorytmów testowania planarności, obejmują:
- kryterium planarności Whitneya, że graf jest planarny wtedy i tylko wtedy, gdy jego matroid graficzny jest również kograficzny,
- kryterium planarności MacLane'a charakteryzujące grafy planarne przez podstawy ich przestrzeni cykli ,
- Twierdzenie Schnydera charakteryzujące grafy planarne przez wymiar porządkowy skojarzonego porządku częściowego , a
- Kryterium płaskości Colina de Verdière'a z wykorzystaniem spektralnej teorii grafów .
Algorytmy
Metoda dodawania ścieżki
Klasyczny dodatek droga metoda Hopcroft i Tarjan był pierwszym opublikowane liniowy czas algorytm badania płaskość 1974. implementacji Hopcroft i Tarjan algorytm jest zabezpieczone w bibliotece efektywnego rodzaju dane oraz algorytmy poprzez Mehlhorn , Mutzel i näher . W 2012 roku Taylor rozszerzył ten algorytm, aby wygenerować wszystkie permutacje cyklicznego porządku krawędzi dla płaskich osadzeń dwupołączonych komponentów.
Metoda dodawania wierzchołków
Metody dodawania wierzchołków działają poprzez utrzymywanie struktury danych reprezentującej możliwe osadzenia indukowanego podgrafu danego wykresu i dodawanie wierzchołków pojedynczo do tej struktury danych. Metody te rozpoczęły się nieefektywną metodą O( n 2 ) opracowaną przez Lempela , Evena i Cederbauma w 1967 roku. Została ona ulepszona przez Evena i Tarjana, którzy znaleźli rozwiązanie w czasie liniowym dla kroku numeracji s , t oraz przez Bootha i Lueker , który opracował strukturę danych drzewa PQ . Dzięki tym ulepszeniom działa w czasie liniowym i przewyższa w praktyce metodę dodawania ścieżek. Ta metoda została również rozszerzona, aby umożliwić efektywne obliczanie płaskiego osadzenia (rysowania) dla grafu płaskiego. W 1999 roku Shih i Hsu uprościli te metody przy użyciu drzewa PC (niezakorzenionego wariantu drzewa PQ) i przechodzenia postorder w drzewie przeszukiwania w głąb wierzchołków.
Metoda dodawania krawędzi
W 2004 r. John Boyer i Wendy Myrvold opracowali uproszczony algorytm O( n ), pierwotnie zainspirowany metodą drzewa PQ, która usuwa drzewo PQ i używa dodawania krawędzi do obliczenia osadzania płaskiego, jeśli to możliwe. W przeciwnym razie obliczany jest podpodział Kuratowskiego ( K 5 lub K 3,3 ). Jest to jeden z dwóch obecnie najnowocześniejszych algorytmów (drugi to algorytm testowania planarności de Fraysseix, de Mendez i Rosenstiehl). Zobacz eksperymentalne porównanie ze wstępną wersją testu planarności Boyera i Myrvolda. Co więcej, test Boyera-Myrvolda został rozszerzony, aby wyodrębnić wiele podpodziałów Kuratowskiego z niepłaskiego wykresu wejściowego w czasie działania liniowo zależnym od rozmiaru wyjściowego. Kod źródłowy dla testu płaskości i ekstrakcji wielu podpodziałów Kuratowskiego jest publicznie dostępny. Algorytmy lokalizujące podwykres Kuratowskiego w czasie liniowym w wierzchołkach zostały opracowane przez Williamsona w latach 80. XX wieku.
Metoda sekwencji konstrukcyjnej
Inna metoda wykorzystuje indukcyjną konstrukcję 3-spójnych grafów do przyrostowego budowania osadzeń płaskich każdego 3-spójnego składnika G (a więc i osadzenia płaskiego samego G ). Konstrukcja zaczyna się od K 4 i jest zdefiniowana w taki sposób, że każdy graf pośredni na drodze do pełnej składowej jest ponownie połączony z trzema. Ponieważ takie wykresy mają unikalne osadzenie (aż do odwrócenia i wyboru powierzchni zewnętrznej), następny większy wykres, jeśli nadal jest planarny, musi być udoskonaleniem poprzedniego wykresu. Pozwala to zredukować test płaskości do testowania dla każdego kroku, czy następna dodana krawędź ma oba końce na zewnętrznej powierzchni bieżącego osadzania. Chociaż jest to koncepcyjnie bardzo proste (i daje liniowy czas działania), sama metoda cierpi ze względu na złożoność znajdowania sekwencji konstrukcyjnej.