Wyliczanie płaskich wykresów ograniczonej szerokości poprzecznej

Szukam odniesień do następującego problemu: biorąc pod uwagę liczby całkowite i , wyliczyć wszystkie nieizomorficzne wykresy płaskie na wierzchołkach i szerokości linii . Interesują mnie zarówno wyniki teoretyczne, jak i praktyczne, ale przede wszystkim praktyczne algorytmy, które można kodować i uruchamiać dla możliwie dużych wartości i (pomyśl i ). Jeśli masz już odpowiedź, zignoruj ​​poniższe bzdury.$n$$k$$n$$\leq k$$n$$k$$k \leq 5$$n \leq 15$

Poniższe podejście działa całkiem dobrze w przypadku wyliczania wszystkich grafów nieizomorficznych na wierzchołkach i treewidth (tj. Po usunięciu ograniczenia płaskości ):$n$$\leq k$

(a) Zliczyć wszystkie wykresy nieizomorficzne na wierzchołkach i krzyżyku .$n-1$$\leq k$

(b) Dla każdego wierzchołka na wierzchołków i szerokości wierzchołka , każdej kliki na wierzchołków w i każdego podzbioru krawędzi w , utwórz z , dodając nowy wierzchołek sąsiedztwie . Dodaj do listy grahów na wierzchołkach i treewidth .$G$$n-1$$\leq k$$C$$\leq k$$G$$S$$C$$G'$$G - S$$v$$C$$G'$${\cal L}$$n$$\leq k$

(c) Przytnij , usuwając kopie tego samego wykresu.${\cal L}$

Kuszącym sposobem na rozszerzenie tego zakresu na wyliczanie płaskich wykresów treewidth jest po prostu filtrowanie wykresów niepłaskich przy każdej iteracji. Niestety nie generuje to wszystkich płaskich wykresów treewidth (na przykład, ponieważ wylicza tylko wykresy zdegenerowane).$\leq k$$\leq k$$4$

Oczywiście moglibyśmy wyliczyć wszystkie wykresy na wierzchołkach i krzywe a dopiero potem odfiltrować te niepłaskie, ale to nie wykorzystuje tego, że większość wykresów jest niepłaskich i wydaje się bardzo nieoptymalna.$n$$\leq k$

Istnieje ładne oprogramowanie, które generuje małe płaskie wykresy w odniesieniu do izomorfizmu, które mogą pomóc. Jak widzę, jednym z problemów było wygenerowanie nieizomorficznych wykresów płaskich, a większość tych płaskich wykresów (na mniej niż 15 wierzchołkach) ma małą szerokość.

Do sprawdzania, czy ich szerokość jest mniejsza niż podana wartość $k$, jednym ze sposobów jest użycie algorytmów heurystycznych w celu przyspieszenia tego obliczenia, na wypadek, gdyby dokładne algorytmy nie były praktyczne. np. na wykresie planarnym$G$ najpierw możemy znaleźć średnicę $G$ i odpowiednią ścieżkę $P$ długości $d$(która jest średnicą). Następnie znajdź wierzchołek$v\in P$ który ma najkrótszą najdłuższą odległość ($l$) do dowolnego innego wierzchołka $u\in G\setminus P$ wśród wszystkich wierzchołków $w\in P$. Szerokość$G$ jest co najwyżej $d+l$, jeśli jest mniejszy niż $k$ skończymy w przeciwnym razie albo zastosujemy inne algorytmy heurystyczne, albo uruchomimy dokładny algorytm.

W przypadku mniej niż 3 połączonych wykresów można również zastosować heurystykę, znajdując wycięte wierzchołki, a następnie naprawiając te wierzchołki i znajdując szerokość drzewa pozostałego wykresu. Ale ponieważ liczba węzłów jest niewielka ($15$), jeśli wykres to $4$- połączona wtedy średnica nie jest duża i myślę, że pierwsza heurystyka powinna tam działać. (Nie wiem, czy istnieje jakikolwiek 5 połączony wykres płaski na co najwyżej 15 wierzchołkach, ale jak wiemy, nie ma$t$połączony wykres planarny dla $t>5$)

Jako wielkość największej przeszkody dla szerokości drzewa $k$ nie jest znane, nie możemy po prostu odgadnąć górnej granicy wartości szerokości danego wykresu $G$. Wydaje się jednak, że przynajmniej dla grafów płaskich nie powinno być tak duże (należy to udowodnić).

Można wyliczyć wszystkie pary $G,B$ gdzie $G$ to wykres płaski z co najwyżej szerokością $k$, $B$ to torba wielkości $k$ tak, że istnieje rozkład drzewa $G$ z $B$ jako torba.

Teraz dla każdej pary $G,B$ gdzie $G$ ma $n-1$ wierzchołki budujemy nowy wykres $G'$ dla każdego podzbioru $S$ z $B$ przez dodanie wierzchołka $v$ z $S$ jako sąsiedzi i niech $B'$ być wielkością $k$ podzbiór $B \cup v$. Dodaj$G',B'$ gdyby $G'$ jest płaski i nie jest izomorficzny w stosunku do żadnej już znalezionej pary.

Łatwa górna granica liczby wpisów, które należy przechowywać $n \choose k$razy liczba wyliczonych wykresów, ale jest to pesymistyczne ograniczenie. W przypadku większości wykresów szerokości k większość podzbiorów rozmiaru k nie może wykonać torby, np. A$k \times n$ siatka ma tylko $n \cdot 3^{k-1}$ możliwe torby.

Wierzę, że zadziała to tak samo jak algorytm dla wykresów niepłaskich, ponieważ dla każdej pary G, B otrzymujemy wykres, czyniąc B kliką, większość tych wykresów będzie nieizomorficzna.

Jest kilka sztuczek, które można zastosować, aby to przyspieszyć, sugeruję zajrzeć do: http://www.siam.org/meetings/alenex04/abstacts/HBodlaender.pdf