Rozkład drzewa dla grafów płaskich

Najpierw zapytany na stronie math.SE bez odpowiedzi

1. Załóżmy, że mam wykres płaski z osadzeniem planarnym, jak znaleźć rozkład drzewa?
2. Jaki jest optymalny rozkład drzewa siatki kwadratowej -by- ? Nie do końca pewny, jak zdefiniować „optymalny”, ale powinien odróżniać rozkład z jedną dużą torbą od rozkładu z wieloma dużymi torbami.$d$$d$

Jeśli to, czego naprawdę chcesz, to dobry porządek eliminacji, być może szukasz uogólnionego podziału na sekcje . Jest to strategia wykorzystująca dobre separatory wykresu płaskiego w celu uzyskania algorytmów dla eliminacji Gaussa, wyznacznika itp. Dla macierzy pochodzących z wykresów płaskich.$O(n^{\omega/2})$

W przypadku pierwszego pytania jest otwarte, czy znalezienie rozkładu drzewa dla grafów płaskich można przeprowadzić w czasie wielomianowym. Najlepszym algorytmem aproksymacyjnym może być algorytm RatCatcher firmy Seymour i Thomas, który oblicza szerokość gałęzi płaskiego wykresu, więc ma współczynnik aproksymacji 1,5 na podstawie relacji między szerokością gałęzi a szerokością.

Po drugie, mamy następujące twierdzenie o szerokości linii siatek:$k \times k$

Twierdzenie. siatka ma treewidth .$k \times k$$k$

I torby można zabrać z rozmiarem , z całkowitą liczbą torebek . Nie jestem pewien, czy tego właśnie chcesz, więc możesz to zrobić, jeśli zmienisz definicję „optymalnego”.$k+1$$k(k-1)$

Jeśli nie chcesz optymalnego rozkładu drzewa, możesz zbudować rozkład drzewa, obliczając rekurencyjnie separatory.