Czy wykresy „rodzaju zewnętrznego” mają stałą szerokość grzbietu?

Niech i przez zestaw wszystkich wykresów, które mogą być osadzone na powierzchni rodzaju tak, aby wszystkie wierzchołki znajdowały się na zewnętrznej powierzchni . Na przykład jest zbiorem zewnętrznych wykresów płaskich. Czy szerokość wykresów w być ograniczona przez jakąś funkcję ?G k k G 0 G k$k\in\mathbb{N}$$G_k$$k$$G_0$$G_k$$k$

Drugi kierunek oczywiście nie ma takiego znaczenia, ponieważ stała szerokość nie oznacza nawet stałego rodzaju: Niech będzie połączeniem rozłącznych kopii . Szerokość jest stała, jednak jej rodzaj to . n K 3 , 3 H n$H_n$$n$$K_{3,3}$$H_n$$n$

Tak.

Dodaj wierzchołek na środku zewnętrznej powierzchni, połączony ze wszystkimi wierzchołkami na zewnętrznej powierzchni; to nie zmienia rodzaju i nie zmniejsza szerokości grzbietu. Teraz wykres ma bardzo płytkie drzewo wyszukiwania o pierwszej szerokości, zakorzenione w nowym wierzchołku (wszystko przylega do niego).

Utwórz drzewo rozpinające podwójnego wykresu, którego podwójne krawędzie są rozłączne od krawędzi drzewa pierwszego wyszukiwania szerokości. Następnie jest zestaw krawędzi O (rodzaju), które nie należą do żadnego z drzew. Każda z tych krawędzi indukuje krótki cykl (trójkąt) wraz ze ścieżką w drzewie pierwszego wyszukiwania szerokości, a przecięcie powierzchni wzdłuż tych cykli tworzy płaską powierzchnię (patrz mój artykuł „Dynamiczne generatory wykresów osadzonych topologicznie”). Oznacza to, że jeśli G 'jest podpisem wykresu wejściowego wywołanego przez wierzchołki, które nie są punktami końcowymi krawędzi cięcia O (rodzaju), to G' jest płaski, a jego wierzchołki mogą być pokryte powierzchniami O (rodzaju) jego osadzanie planarne (ściany, na które cykle cięcia przecinają oryginalną powierzchnię zewnętrzną).

Ale na wykresie planarnym, na którym wszystkie wierzchołki należą do k ścian, można usunąć kolejne krawędzie O (k) (drzewo rozpinające ścian), aby uzyskać wykres płaszczyzny zewnętrznej. Tak więc szerokość G 'to O (rodzaj). Jeśli tworzy się rozkład drzewa G 'o tej szerokości, a następnie dodaje do każdej torby wierzchołki, które są punktami końcowymi krawędzi cyklu cięcia, wynikiem jest rozkład drzewa oryginalnego wykresu wejściowego z rzędem O (rodzaj).

Wydaje się prawdopodobne, że musi to już gdzieś być w literaturze, ale nie wiem, gdzie i niektórym szybkim wyszukiwaniom nie udało się znaleźć wyraźnego stwierdzenia tego dokładnego wyniku. Jednak bardziej ogólne stwierdzenie znajduje się w innym moim artykule: w „Średnicy i szerokości w mniejszych rodzinach grafów zamkniętych” Udowadniam między innymi, że ograniczone wykresy rodzajów o ograniczonej średnicy ograniczyły szerokość. W tym przypadku (dodając ten dodatkowy wierzchołek w zewnętrznej powierzchni) można przyjąć, że średnica wynosi maksymalnie dwa.