Rozkładanie wykresów rodzaju pierwszego

Wykresy płaskie są wolne od . Wykresy te mogą być rozłożone na części składowe tri połączone, które wiadomo, że są albo płaską lub składników. $K_{3,3}$ $K_5$

Czy istnieje taki „ładny” rozkład grafów z rodzaju 1?

W swojej przełomowej pracy nad nieletnimi grafami Roberston i Seymour wykazali, że każdy wolny od drobnych wykresów można rozłożyć na „sumę klikową” wykresów „prawie płaskich”. Dotyczy to oczywiście również grafów z ograniczonym rodzajem. Szukam rozkładów specyficznych dla wykresów rodzaju 1, aby lepiej zrozumieć ich właściwości strukturalne.

— Shiva Kintali
źródło

Może to być przydatne: arxiv.org/abs/math/0411488

— Jeffε

K_{7}

$K_7$

Istnieje silniejszy wynik rozkładu dla rodzin grafów, które wykluczają wykres jednoprzecinkowy jako niewielki (tj. Wykres, który można narysować w płaszczyźnie z pojedynczym punktem, w którym krzyżują się krawędzie). Takie wykresy można rozkładać na kliki wykresów płaskich i wykresy stałej szerokości (patrz np. „Algorytmy aproksymacyjne dla klas wykresów z wyłączeniem wykresów pojedynczego przejścia jako nieletnich”). Jeśli w zestawie przeszkód torusa znajduje się wykres pojedynczego skrzyżowania, to by ci pomogło. (Nie jestem pewien, czy jest - i może istnieć prosty powód, dla którego nie ma takiej możliwości).

— Bart Jansen

Istnieje prosty powód, dla którego toroidalność nie może być przeszkodą dla przekroczenia jednego przejścia: każdy tor pojedynczego przejścia można narysować na torusie, zastępując przejście małym uchwytem.

— David Eppstein

Myślę, że Robertson i Seymour pokazali, że każdy wolny od drobnych wykresów można rozłożyć na „sumę klikową ” wykresów „ prawie związanego rodzaju ”. Podstawowymi elementami składowymi nie są wykresy płaskie, ale wykresy rodzaju związanego (rodzaj zależny od wykluczonego pomniejszego). Myślę, że wykresy toroidalne nie podlegają dalszemu rozkładowi.

— Marcin Kamiński
źródło