Rozkładanie wykresów rodzaju pierwszego

15

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 K 5 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.

graph-theory co.combinatorics planar-graphs graph-minor Shiva Kintali
źródło
Może to być przydatne: arxiv.org/abs/math/0411488
Jeffε
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

Odpowiedzi:

1

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