Graf płaski na przecięciu grubych rzeczy?

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.)$X$$R(X)$$X$$r(X)$$S$$S$$\alpha$$R(x) /r(x) \leq \alpha$

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.

Jeśli używasz trójkątów, możesz to zrobić. Być może nie łatwiej niż Koebe ...

de Fraisseix, Ossona de Mendez i Rosenstiehl. Na trójkątnych wykresach kontaktowych. CPC 3 (2): 233–246, 1994.

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 .

$K_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.

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.