Es gibt einen schönen Satz von Koebe (siehe hier ), der besagt, dass jeder ebene Graph als Kussdiagramm von Scheiben gezeichnet werden kann (sehr romantisch ...). (Anders ausgedrückt, jeder ebene Graph kann als Schnittgraph von Scheiben gezeichnet werden.)
Der Koebe-Satz ist nicht leicht zu beweisen. Meine Frage: Gibt es eine einfachere Version dieses Theorems, bei der anstelle von Scheiben beliebige fette konvexe Formen verwendet werden dürfen (Konvexität ist möglicherweise verhandelbar, aber nicht fett). Beachten Sie, dass jeder Scheitelpunkt eine andere Form haben kann.
Vielen Dank...
Zur Verdeutlichung: Für eine Form , lassen Sie R ( X ) sein der Radius der kleinsten umschließenden Kugel von X , und lassen Sie r ( X ) lassen Sie mich den Radius der größten geschlossenen Kugel in S . Die Form S ist α- fett, wenn R ( x ) / r ( x ) ≤ α ist . (Dies ist nicht die einzige Definition für Fettleibigkeit.)
quelle
Antworten:
Du hast doch nicht gesagt, dass die fetten Objekte zweidimensional sein müssen, oder? Felsner und Francis beweisen, dass es mit achsparallelen Würfeln in 3d immer möglich ist . Der Beweis beinhaltet jedoch Schramms Verallgemeinerungen von Koebe-Thurston-Andreev, so dass es nicht gerade ein einfacheres Ergebnis ist. Sie erwähnen auch, dass es für maximal planare Graphen mit vier Verknüpfungen möglich ist, parallele gleichseitige Dreiecke zu verwenden.
quelle
Wenn Sie Dreiecke verwenden, können Sie dies tun. Vielleicht nicht einfacher als Koebe ...
de Fraisseix, Ossona de Mendez und Rosenstiehl. Auf Dreieckskontaktdiagrammen. CPC 3 (2): 233-246, 1994.
quelle
Schramm hat in seiner Doktorarbeit (Princeton, 1990) unter Verwendung von Brouwers Fixpunktsatz bewiesen, dass jeder planare Graph der Kontaktgraph einer Reihe von glatten konvexen Objekten in der Ebene ist .
Eine schöne Übersicht über dieses und andere Ergebnisse im Zusammenhang mit Koebes Theorem findet sich in einer Umfrage von Sachs .
quelle
Wir wissen, dass Sie Koebes Theorem nicht mit Rechtecken nachbilden können. Kontaktdiagramme von Rechtecken können nicht erfasst werdenK4 .
quelle
Es gibt eine neue Veröffentlichung von Duncan, Gansner, Hu, Kaufman und Kobourov über die Darstellung von Kontaktgraphen. Sie zeigen, dass 6-seitige Polygone notwendig und ausreichend sind. Die Sechsecke können konvex sein, aber bei der ersten Lesung war mir nicht klar, ob sie auch fett waren.
quelle
Gerd Wegner hat in seiner Doktorarbeit (Georg-August-Universität, Göttingen, 1967) bewiesen, dass jeder Graph der Kontaktgraph einer Reihe dreidimensionaler konvexer Polytope ist (er schreibt Grünbaum jedoch den ersten unveröffentlichten Beweis des Ergebnisses zu). Dies ist ein kurzer Beweis.
quelle