Planarer Graph über den Schnittpunkt fetter Dinger?

14

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.)XR(X)Xr(X)SSαR(x)/r(x)α

Sariel Har-Peled
quelle
um etwas pedantisch zu sein: Koebes Theorem handelt von Kontaktgraphen, die sich geringfügig von Schnittgraphen unterscheiden. Welche Version würdest du bevorzugen?
Suresh Venkat
Daher gehe ich davon aus, dass Fettigkeit erforderlich ist, da jedes ebene Diagramm das Schnittdiagramm der Segmente in der Ebene ist (Chalopin & Gonçalves, STOC 09). Wenn sie nicht fett sind, ist Küssen dasselbe wie eine Kreuzung. (Hm, der letzte Satz ist seltsam aus dem Zusammenhang
gerissen
Fett macht das Leben einfacher, wenn man andere Dinge mit dem Graphen macht (zum Beispiel das Finden eines Trennzeichens).
Sariel Har-Peled
3
Ich frage mich, ob die eigentliche Frage hier lautet: "Geben Sie einen einfachen Beweis für Koebes Theorem" statt "Finden Sie Fettformfamilien mit geringer Komplexität, die Koebes Theorem simulieren"
Suresh Venkat
2
Sicher. Das ist eine gültige Interpretation. Um jedoch einen einfachen Beweis für das Koebe-Theorem zu erhalten, muss man sich irgendwie entspannen ...
Sariel Har-Peled

Antworten:

10

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.

David Eppstein
quelle
Nun, das ist auch eine schöne Frage, denke ich. Gibt es einen schnellen Beweis, dass jeder ebene Graph als Kontaktgraph von Kugeln darstellbar ist?
RJK
6

Wir wissen, dass Sie Koebes Theorem nicht mit Rechtecken nachbilden können. Kontaktdiagramme von Rechtecken können nicht erfasst werdenK4.

Suresh Venkat
quelle
Achsparallele Rechtecke? Oder irgendwelche Rechtecke?
Sariel Har-Peled
achsparallele Rechtecke.
Suresh Venkat
4

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.

Suresh Venkat
quelle
Yo yo. Ich habe dieses Papier gerade selbst entdeckt ... Sie verwenden das oben erwähnte Ergebnis von de Fraisseix et al und ein Ergebnis von Kant ...
Sariel Har-Peled
Hier wird "Kontakt" anders definiert. Punktkontakt ist nach meiner Lektüre nicht zulässig.
RJK
Ich kann mir vorstellen, dass dies für polygonale Darstellungen sinnvoll ist (da jeder Nicht-Vertex-Kontakt notwendigerweise ein Nicht-Punkt-Kontakt ist).
Suresh Venkat
Da hier nur drei Slops zulässig sind, muss die Berührung über parallele Kanten erfolgen, die sich gegenseitig berühren ... Nein?
Sariel Har-Peled
0

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.

RJK
quelle
Es gibt einfache direkte Beweise dafür, zum Beispiel indem man Punkte auf die Momentenkurve legt und ihr Voronoi-Diagramm berechnet. Hier scheitert der
Fettleibigkeitszustand
Ah, ich habe "Fett" völlig falsch verstanden. Es ist mir peinlich zuzugeben (aber ich denke, es muss jetzt klar sein), dass ich die Definition nicht kannte, bis ich "fettes Dreieck" gegoogelt habe. Könnten Sie bitte eine Referenz / Definition für dieses Konzept angeben?
RJK
Die erwähnte Darstellung kann auch verwendet werden, um alle Graphen auf diese Weise darzustellen - nicht nur ebene Graphen.
Sariel Har-Peled
Danke für die Klarstellung von "Fett" in der Frage. Es ist erwähnenswert, dass ich in diesem Beitrag auch Planar nicht erwähnt habe. Für einen gegebenen Wert der Fettheit kann jedes Diagramm durch fettkonvexe Polytope in einer (ausreichend hohen) Dimension dargestellt werden. Die naheliegende Frage ist, ob die Bemaßungsgrenze über alle Diagramme hinweg einheitlich sein kann. Wurde das untersucht?
RJK
Nicht so weit ich weiß, aber ich bin nicht sehr gut
informiert