Graf płaski na przecięciu grubych rzeczy?

14

Istnieje piękne twierdzenie Koebe'a (patrz tutaj ), które stwierdza, że ​​każdy płaski wykres można narysować jako wykres całowania dysków (bardzo romantyczny ...). (Mówiąc nieco inaczej, każdy wykres płaski można narysować jako wykres przecięcia dysków.)

Twierdzenie Koebe'a nie jest łatwe do udowodnienia. Moje pytanie: czy istnieje łatwiejsza wersja tego twierdzenia, w której zamiast dysków można stosować dowolne tłuste kształty wypukłe (wypukłość może być otwarta na negocjacje, ale nie tłustość). Pamiętaj, że każdy wierzchołek może mieć inny kształt.

Dzięki...

Wyjaśnienie: Dla kształt , niech R ( X ) jest promień najmniejszej otaczającej kulę X i pozwolić R ( X ) pozwolić mi promienia największego zamkniętych kulką w S . Kształt S jest α- tłuszczem, jeżeli R ( x ) / r ( x ) α . (To nie jest jedyna definicja tłuszczu, BTW.)XR(X)Xr(X)SSαR(x)/r(x)α

Sariel Har-Peled
źródło
lekko pedantyczny: twierdzenie Koebe'a dotyczy grafów kontaktowych, które nieco różnią się od grafów przecięcia. Którą wersję wolisz?
Suresh Venkat,
Zakładam więc, że wymagana jest grubość, ponieważ każdy wykres płaski jest wykresem przecięcia segmentów w płaszczyźnie (Chalopin i Gonçalves, STOC 09). Jeśli nie są grubi, całowanie jest tym samym, co skrzyżowanie. (Hm, ostatnie zdanie jest dziwne wyrwane z kontekstu!)
RJK
Tłuszcz tylko ułatwia życie, jeśli chodzi o robienie innych rzeczy na wykresie (na przykład znalezienie separatora).
Sariel Har-Peled,
3
Zastanawiam się, czy prawdziwe pytanie brzmi: „daj prosty dowód twierdzenia Koebe'a” zamiast „znajdź rodziny tłuszczów o niskiej złożoności, które symulują twierdzenie Koebe'a”
Suresh Venkat
2
Pewnie. To ważna interpretacja. Myślę jednak, że aby uzyskać prosty dowód Koebe twierdzenia, trzeba odpocząć go jakoś ...
Sariel Har-Peled

Odpowiedzi:

10

Nie mówiłeś, że grube przedmioty muszą być dwuwymiarowe, prawda? Felsner i Francis udowadniają, że zawsze jest to możliwe z sześcianami równoległymi do osi w 3d . Ale dowód obejmuje uogólnienia Schramm'a dotyczące Koebe-Thurston-Andreev, więc nie jest to wcale prostszy wynik. Po drodze wspominają również, że w przypadku czterech połączonych maksymalnych wykresów płaskich możliwe jest użycie równoległych trójkątów równobocznych.

David Eppstein
źródło
To chyba też miłe pytanie. Czy istnieje szybki dowód na to, że każdy wykres płaski jest reprezentatywny jako wykres kontaktowy sfer?
RJK
7

Schramm udowodnił, że każdy wykres płaski jest wykresem kontaktowym pewnego zestawu gładkich wypukłych obiektów w płaszczyźnie w swojej rozprawie doktorskiej (Princeton, 1990) za pomocą twierdzenia Brouwera o stałym punkcie.

Ładna ankieta na temat tego i innych wyników związanych z twierdzeniem Koebe znajduje się w ankiecie Sachsa .

RJK
źródło
6

K.4

Suresh Venkat
źródło
Prostokąty równoległe osi? A może jakieś prostokąty?
Sariel Har-Peled,
równoległe prostokąty osi.
Suresh Venkat,
4

Jest nowy artykuł na temat arxiv autorstwa Duncana, Gansnera, Hu, Kaufmana i Kobourova na temat reprezentacji grafów kontaktowych. Pokazują, że sześciokątne wielokąty są konieczne i wystarczające. Sześciokąty mogą być wypukłe, ale przy pierwszym czytaniu nie było dla mnie jasne, czy są również tłuste.

Suresh Venkat
źródło
Jo-jo Właśnie odkryłem ten artykuł ... Używają wspomnianego wyżej wyniku de Fraisseix i wyniku Kanta ...
Sariel Har-Peled
Tutaj „kontakt” definiuje się inaczej. Z mojego czytania kontakt punktowy jest niedozwolony.
RJK
Wyobrażam sobie, że jest to uzasadnione w przypadku reprezentacji wielokątnych (skoro jakikolwiek kontakt niebędący wierzchołkiem będzie koniecznie niepunktowy)?
Suresh Venkat
Ponieważ tutaj są tylko trzy dopuszczalne nachylenia, dotyk musi odbywać się za pomocą równoległych krawędzi stykających się ze sobą ... Nie?
Sariel Har-Peled,
0

Gerd Wegner w swojej rozprawie doktorskiej (Georg-August-Universität, Göttingen, 1967) udowodnił, że każdy wykres jest wykresem kontaktowym zestawu trójwymiarowych wypukłych polytopów (ale przypisuje pierwszy niepublikowany dowód wyniku Grünbaumowi). To krótki dowód.

RJK
źródło
Istnieją proste bezpośrednie dowody na to, na przykład poprzez umieszczenie punktów na krzywej momentu i obliczenie ich wykresu Voronoi. Tutaj jednak warunek otłuszczenia zawodzi żałośnie ...
Sariel Har-Peled,
Ach, zupełnie źle zrozumiałem „gruby”. Wstydzę się przyznać (ale chyba musi być teraz jasne), że nie znałem definicji, dopóki nie przejrzałem „grubego trójkąta”. Czy możesz podać odniesienie / definicję tej koncepcji?
RJK
Przedstawionej przeze mnie reprezentacji można także użyć do przedstawienia dowolnego wykresu w ten sposób - nie tylko wykresów płaskich.
Sariel Har-Peled,
Dzięki za wyjaśnienie „tłuszczu” w pytaniu. Warto zauważyć, że w tym poście nie wspomniałem również o planarach. Dla danej wartości otyłości każdy wykres jest reprezentowany przez wypukłe polytopy tłuszczu w pewnym (wystarczająco wysokim) wymiarze. Oczywistym pytaniem jest, czy ograniczenie wymiaru może być jednolite na wszystkich wykresach. Czy zostało to zbadane?
RJK
O ile mi wiadomo, ale nie znam się na takich sprawach ...
Sariel Har-Peled,