Klasy wykresów z nadprzyrodzoną szerokością

Istnieje kilka interesujących klas wykresów z ograniczoną szerokością. Na przykład drzewa (treewidth 1), szeregi równoległe wykresy (treewidth 2), zewnętrzne płaszczyzny (treewidth 2), routerplanar wykresy (treewidth O (k)), wykresy szerokości gałęzi (treewidth O (k)), .. . $k$ $k$

Pytanie: Czy istnieją przykłady interesujących klas wykresów, których szerokość nie jest ograniczona stałą, ale funkcją niskiego wzrostu?

Czy istnieją dobrze znane klasy wykresów z treewidth ? $O(\log\log n)$
Czy istnieją dobrze znane klasy wykresów z treewidth ? $O(\log n)$

Byłbym także zainteresowany klasami grafów o szerokości lub których logarytm jest powtarzany stałą liczbę razy. $O(\log^k n)$ $O(\log\log...n)$

Obs: Oczywiście łatwo jest gotować sztuczne rodziny grafów o danej szerokości, takie jak rodzinasiatki. Dlatego przede wszystkim szukam rodziny grafów, które były badane w innych gałęziach teorii grafów i które miałyby szerokość lub , ale nie stałą szerokość. $\;O(\log n)\times n\;$ $O(\log n)$ $O(\log\log n)$

graph-theory treewidth

— Mateus de Oliveira Oliveira
źródło

Drobne wolne wykresy (planar ++) mają szerokość

, wiele klas grafów ma szerokość logiczną

, patrz ten artykuł:

O (\sqrt{(} n))

$O(\sqrt(n))$

O (\log n)

$O(\log n)$ ii.uib.no/~martinv/Papers/Logarithmic_booleanwidth.pdf

— Daniello

@daniello Dziękuję bardzo za komentarz.

jest wciąż za duży. Naprawdę interesuje mnie szerokość co najwyżej polilogarytmiki. Artykuł o szerokości logicznej jest bardzo interesujący i daje kilka fajnych klas o szerokości logicznej

. Ale ponieważ szerokość boolowska jest co najwyżej kwadratem do kwadratu, istnieją wykresy stałej szerokości boolowskiej i

\sqrt{n}

$\sqrt{n}$

O (\log n)

$O(\log n)$

treewidth. Tak więc wyniki w artykule nie przekładają się natychmiast na szerokość.

\sqrt{n}

$\sqrt{n}$

— Mateus de Oliveira Oliveira

Uważam, że uniwersalne wykresy dla drzew zbudowanych przez Chung i Graham 1983 mają treewidth . Lub dla nieco prostszego, ale podobnego przykładu, rozważ przechodnie przechodnie zrównoważonych drzew binarnych. $\Theta(\log n)$

Jest tu jednak również wynik ujemny. Wszystkie podane przez ciebie przykłady interesujących rodzin wykresów są w niewielkim stopniu zamknięte lub bardzo blisko związane z mniejszymi rodzinami zamkniętymi. Ale rodzina niewielkich zamkniętych grafów zawiera wszystkie wykresy płaskie (a zatem ma maksymalną szerokość rozwarcia ) lub ma niedozwolony planarny moll (i dlatego ograniczył szerokość). $\Theta(\sqrt n)$

— David Eppstein
źródło