Wykres kwadratowy - Squaregraph

Wykres kwadratowy.

W teorii grafów , gałęzi matematyki , wykres kwadratowy jest rodzajem wykresu nieukierunkowanego, który można narysować na płaszczyźnie w taki sposób, że każda ograniczona ściana jest czworobokiem, a każdy wierzchołek z trzema lub mniej sąsiadami przypada na nieograniczoną ścianę.

Powiązane klasy grafów

W squaregraphs to jako szczególne przypadki drzew , grafów sieciowych , wykresy zębatych , a wykresy polyominos .

Oprócz tego , że są grafami planarnymi, wykresy kwadratowe są grafami medianowymi , co oznacza, że ​​dla każdych trzech wierzchołków u , v i w istnieje unikalny środkowy wierzchołek m ( u , v , w ), który leży na najkrótszych ścieżkach między każdą parą trzech wierzchołków . Podobnie jak w przypadku grafów mediany bardziej ogólnie, wykresy kwadratowe są również częściowymi sześcianami : ich wierzchołki można oznaczyć ciągami binarnymi, tak że odległość Hamminga między łańcuchami jest równa najkrótszej odległości ścieżki między wierzchołkami.

Otrzymany z squaregraph wykres poprzez wierzchołek dla każdej strefy (klasa równoważność równoległych krawędzi czworoboków) oraz krawędzi każdego dwie strefy, które spotykają się w czworoboku jest wykresem okrąg określony przez trójkąt wolne schemacie cięciwy urządzeniu dysk.

Charakteryzacja

Wykresy kwadratowe można scharakteryzować na kilka sposobów innych niż poprzez ich płaskie osadzenia:

  • Są to grafy mediany , które nie zawierają jako indukowanego podgrafu żadnego członka nieskończonej rodziny zabronionych grafów . Te zakazane wykresy kostki (The simplex wykres z K 3 ), przy czym iloczyn z krawędzią i pazur K 1,3 (simplex wykres pazur) i wykresy utworzone z wykresu przekładni dodając jeden wierzchołek połączony z piastą koła (wykres simplex rozłącznego połączenia cyklu z izolowanym wierzchołkiem).
  • Są to grafy, które są połączone i dwudzielne , takie, że (jeśli dowolny wierzchołek r jest wybrany jako pierwiastek ) każdy wierzchołek ma co najwyżej dwóch sąsiadów bliżej r , i takie, że w każdym wierzchołku v łącze v (wykres z wierzchołkiem dla każdej krawędzi padającej na v i krawędzią dla każdego 4-cyklowego cyklu zawierającego v ) jest albo cyklem o długości większej niż trzy, albo rozłącznym połączeniem ścieżek.
  • Są to graf dualny z układami linii w hiperbolicznej płaszczyzną , które nie mają trzy wzajemnie przecinające linie.

Algorytmy

Charakterystykę grafów kwadratowych pod względem odległości od pierwiastka i połączeń wierzchołków można wykorzystać wraz z wyszukiwaniem wszerz jako części algorytmu czasu liniowego w celu sprawdzenia, czy dany graf jest grafem kwadratowym, bez konieczności stosowania bardziej złożonej metody liniowej. algorytmy czasowe do testowania płaskości dowolnych grafów.

Kilka problemów algorytmicznych na wykresach kwadratowych można obliczyć wydajniej niż na bardziej ogólnych grafach planarnych lub medianach; na przykład Chepoi, Dragan i Vaxès (2002) oraz Chepoi, Fanciullini i Vaxès (2004) przedstawiają algorytmy czasu liniowego do obliczania średnicy wykresów kwadratowych i znajdowania wierzchołka minimalizującego maksymalną odległość do wszystkich innych wierzchołków.

Uwagi

Bibliografia

  • Bandelt, Hans-Jürgen; Chepoi, Victor; Eppstein, David (2010), „Combinatorics and geometry of finite and infinite squaregraphs”, SIAM Journal on Discrete Mathematics , 24 (4): 1399–1440, arXiv : 0905.4537 , doi : 10.1137 / 090760301 , S2CID   10788524 .
  • Chepoi, Victor; Dragan, Fiodor; Vaxès, Yann (2002), "Problem centrum i średnicy w planarnych czworokątach i triangulacjach", Proc. Natl. 13. rocznica. ACM–SIAM Symp. on Discrete Algorithms (SODA 2002) , s. 346–355 .
  • Chepoi, Victor; Fanciullini, Clémentine; Vaxès, Yann (2004), „Problem mediany w niektórych triangulacjach i czworokątach płaszczyzny”, Geometria obliczeniowa , 27 (3): 193-210, doi : 10.1016/j.comgeo.2003.11.002 .
  • Peterin, Iztok (2006), „A characterisation of planar median graphs” , Discussiones Mathematicae Graph Theory , 26 (1): 41–48, doi : 10,7151 / dmgt.1299
  • Soltan, P.; Zambitskii, D .; Prisǎcaru, C. (1973), Extremal Problems on Graphs and Algorithms of their Solution (po rosyjsku), Kiszyniów, Mołdawia: Ştiinţa .