Satz von Steinitz

Satz von Steinitz (Umgeleitet vom Satz von Steinitz) Zur Navigation springen Zur Suche springen Dieser Artikel handelt vom Satz über Graphen von Polyedern. Für andere Verwendungen, siehe Satz von Steinitz (Begriffsklärung).

In der polyedrischen Kombinatorik, ein Zweig der Mathematik, Der Satz von Steinitz ist eine Charakterisierung der ungerichteten Graphen, die durch die Kanten und Scheitelpunkte dreidimensionaler konvexer Polyeder gebildet werden: sie sind genau die 3-eckenverbundenen planaren Graphen. Das ist, Jedes konvexe Polyeder bildet einen dreifach zusammenhängenden planaren Graphen, und jeder 3-fach zusammenhängende planare Graph kann als Graph eines konvexen Polyeders dargestellt werden. Deshalb, Die 3-verbundenen planaren Graphen werden auch als polyedrische Graphen bezeichnet.[1] Dieses Ergebnis liefert einen Klassifikationssatz für die dreidimensionalen konvexen Polyeder, etwas, das in höheren Dimensionen nicht bekannt ist.[2] Es liefert eine vollständige und rein kombinatorische Beschreibung der Graphen dieser Polyeder, andere Ergebnisse darauf zulassen, wie Eberhards Satz über die Realisierung von Polyedern mit gegebenen Flächentypen, leichter nachzuweisen, ohne Bezug auf die Geometrie dieser Formen.[3] Zusätzlich, Es wurde beim Zeichnen von Diagrammen angewendet, als Möglichkeit, dreidimensionale Visualisierungen abstrakter Graphen zu erstellen.[4] Branko Grünbaum hat diesen Satz genannt "das wichtigste und tiefste bekannte Ergebnis zu 3-Polytopen."[5] Der Satz erscheint in a 1922 Veröffentlichung von Ernst Steinitz,[6] nach wem es benannt ist. Sie kann durch mathematische Induktion bewiesen werden (wie Steinitz es getan hat), indem der minimale Energiezustand eines zweidimensionalen Federsystems gefunden und das Ergebnis in drei Dimensionen angehoben wird, oder mit dem Kreispackungssatz. Es sind mehrere Erweiterungen des Theorems bekannt, in dem das Polyeder, das einen gegebenen Graphen realisiert, zusätzliche Einschränkungen hat; zum Beispiel, Jeder polyedrische Graph ist der Graph eines konvexen Polyeders mit ganzzahligen Koordinaten, oder der Graph eines konvexen Polyeders, dessen Kanten alle eine gemeinsame Mittelkugel berühren.

Inhalt 1 Definitionen und Aussage des Theorems 2 Beweise 2.1 Induktion 2.2 Heben 2.3 Kreisverpackung 3 Realisierungen mit zusätzlichen Eigenschaften 3.1 Ganzzahlige Koordinaten 3.2 Gleiche Steigungen 3.3 Festlegen der Form eines Gesichts 3.4 Tangentiale Kugeln 4 Verwandte Ergebnisse 5 Geschichte 6 Referenzen Definitionen und Aussage des Theorems Das Beleuchten des Skeletts eines konvexen Polyeders von einer Lichtquelle in der Nähe einer seiner Flächen bewirkt, dass seine Schatten ein planares Schlegel-Diagramm bilden.

Ein ungerichteter Graph ist ein System aus Ecken und Kanten, jede Kante verbindet zwei der Eckpunkte. Aus jedem Polyeder kann man einen Graphen bilden, indem man die Scheitel des Graphen den Scheiteln des Polyeders entsprechen lässt und indem man zwei beliebige Scheitel des Graphen durch eine Kante verbindet, wann immer die entsprechenden zwei Polyeder-Eckpunkte die Endpunkte einer Kante des Polyeders sind. Dieser Graph ist als Skelett des Polyeders bekannt.[7] Ein Graph ist planar, wenn er mit seinen Ecken als Punkte in der euklidischen Ebene gezeichnet werden kann, und seine Kanten als Kurven, die diese Punkte verbinden, so dass keine zwei Kantenkurven einander schneiden und dass der Punkt, der einen Scheitel darstellt, nur dann auf der Kurve liegt, die eine Kante darstellt, wenn der Scheitel ein Endpunkt der Kante ist. Nach dem Satz von Fáry, Jede ebene Zeichnung kann so begradigt werden, dass die Kurven, die die Kanten darstellen, Liniensegmente sind. Ein Graph ist 3-fach zusammenhängend, wenn er mehr als drei Ecken und hat, nach dem Entfernen von zwei beliebigen seiner Eckpunkte, jedes andere Knotenpaar bleibt durch einen Pfad verbunden. Der Satz von Steinitz besagt, dass diese beiden Bedingungen sowohl notwendig als auch ausreichend sind, um die Skelette dreidimensionaler konvexer Polyeder zu charakterisieren: ein gegebener Graph {Anzeigestil G} ist der Graph eines konvexen dreidimensionalen Polyeders, dann und nur dann, wenn {Anzeigestil G} ist planar und 3-ecken-zusammenhängend.[5][8] Beweise Illustration des Beweises des Satzes von Balinski, zeigt die Nullmenge einer linearen Funktion (blau) durch zwei gegebene Ecken gehen (gelb) und die Pfade des Simplex-Verfahrens, die den verbleibenden Graphen verbinden (grün) Eine Richtung des Satzes von Steinitz (die leichter zu beweisende Richtung) besagt, dass der Graph jedes konvexen Polyeders eben und 3-fach zusammenhängend ist. Wie in der Abbildung gezeigt, Planarität kann mit einem Schlegel-Diagramm gezeigt werden: wenn man eine Lichtquelle in der Nähe einer Fläche des Polyeders platziert, und ein Flugzeug auf der anderen Seite, Die Schatten der Polyederkanten bilden einen planaren Graphen, so eingebettet, dass die Kanten gerade Liniensegmente sind. Die 3-Konnektivität eines polyedrischen Graphen ist ein Spezialfall von Balinskis Theorem, dass der Graph beliebig ist {Anzeigestil k} -dimensionales konvexes Polytop ist {Anzeigestil k} -in Verbindung gebracht. Die Konnektivität des Graphen eines Polytops, nach dem Entfernen von irgendwelchen {Anzeigestil k-1} seiner Eckpunkte, kann bewiesen werden, indem man einen weiteren Knoten wählt {Anzeigestil v} , Finden einer linearen Funktion, die auf der resultierenden Menge von Null ist {Anzeigestil k} Eckpunkte, und Folgen der durch das Simplex-Verfahren erzeugten Pfade, um jeden Scheitelpunkt mit einem von zwei äußersten Scheitelpunkten der linearen Funktion zu verbinden, mit dem gewählten Eckpunkt {Anzeigestil v} mit beiden verbunden.[9] Das andere, schwieriger, Die Richtung des Satzes von Steinitz besagt, dass jeder planare 3-fach zusammenhängende Graph der Graph eines konvexen Polyeders ist. Für diesen Teil gibt es drei Standardansätze: Beweise durch Induktion, Anheben zweidimensionaler Tutte-Einbettungen in drei Dimensionen unter Verwendung der Maxwell-Cremona-Korrespondenz, und Verfahren, die das Kreispackungstheorem verwenden, um ein kanonisches Polyeder zu erzeugen.

Induction Δ-Y and Y-Δ transforms of a polyhedron Although Steinitz's original proof was not expressed in terms of graph theory, es kann in diesen Begriffen umgeschrieben werden, und beinhaltet das Auffinden einer Folge von Δ-Y- und Y-Δ-Transformationen, die jeden 3-verbundenen planaren Graphen auf reduzieren {Anzeigestil K_{4}} , der Graph des Tetraeders. Eine Y-Δ-Transformation entfernt einen Scheitelpunkt dritten Grades aus einem Graphen, Hinzufügen von Kanten zwischen all seinen früheren Nachbarn, wenn diese Kanten nicht bereits existierten; die Rückwandlung, eine Δ-Y-Transformation, entfernt die Kanten eines Dreiecks aus einem Graphen und ersetzt sie durch einen neuen Scheitelpunkt dritten Grades neben denselben drei Scheitelpunkten. Sobald eine solche Sequenz gefunden wird, sie lässt sich umkehren und in geometrische Operationen umwandeln, die ausgehend von einem Tetraeder Schritt für Schritt das gewünschte Polyeder aufbauen. Jede Y-Δ-Transformation in der umgekehrten Sequenz kann geometrisch durchgeführt werden, indem ein Scheitelpunkt dritten Grades von einem Polyeder abgeschnitten wird. Eine Δ-Y-Transformation in umgekehrter Reihenfolge kann geometrisch durchgeführt werden, indem eine Dreiecksfläche von einem Polyeder entfernt und seine benachbarten Flächen bis zu dem Punkt verlängert werden, an dem sie sich treffen, aber nur, wenn dieser dreifache Schnittpunkt der drei benachbarten Flächen auf der anderen Seite der vom Polyeder entfernten Fläche liegt. Wenn der dreifache Schnittpunkt nicht auf der anderen Seite dieser Fläche liegt, eine projektive Transformation des Polyeders genügt, um es auf die richtige Seite zu verschieben. Deswegen, durch Induktion über die Anzahl der Δ-Y- und Y-Δ-Transformationen, die benötigt werden, um einen gegebenen Graphen auf zu reduzieren {Anzeigestil K_{4}} , Jeder polyedrische Graph kann als Polyeder realisiert werden.[5] Eine spätere Arbeit von Epifanov verstärkte Steinitz 'Beweis, dass jeder polyedrische Graph reduziert werden kann {Anzeigestil K_{4}} durch Δ-Y- und Y-Δ-Transformationen. Epifanov bewies dies, wenn zwei Scheitelpunkte in einem planaren Graphen angegeben sind, dann kann der Graph auf eine einzelne Kante zwischen diesen Terminals reduziert werden, indem Δ-Y- und Y-Δ-Transformationen mit seriell-parallelen Reduktionen kombiniert werden.[10] Epifanovs Beweis war kompliziert und nicht konstruktiv, aber es wurde von Truemper vereinfacht, indem Methoden verwendet wurden, die auf Graphminoren basieren. Truemper beobachtete, dass jeder Gittergraph auf diese Weise um Δ-Y reduzierbar ist und Y-Δ-Transformationen durchführt, dass diese Reduzierbarkeit durch Graphminoren erhalten bleibt, und dass jeder planare Graph ein Minor eines Gittergraphen ist.[11] Diese Idee kann verwendet werden, um das Lemma von Steinitz zu ersetzen, dass eine Reduktionsfolge existiert. Nach diesem Austausch, der Rest des Beweises kann wie der Originalbeweis von Steinitz mittels Induktion geführt werden.[8] Für diese Beweise, durchgeführt unter Verwendung einer der Möglichkeiten zum Auffinden von Sequenzen von Δ-Y- und Y-Δ-Transformationen, Es gibt polyedrische Graphen, die eine nichtlineare Anzahl von Schritten erfordern. Etwas präziser, unendlich viele Graphen erfordern eine mindestens proportionale Anzahl von Schritten {Anzeigestil n^{3/2}} , wo {Anzeigestil n} ist die Anzahl der Scheitelpunkte im Graphen, und die bekannteste Obergrenze für die Anzahl der ausreichenden Schritte ist größer, proportional zu {Anzeigestil n^{2}} .[12] Eine alternative Form des Induktionsbeweises basiert auf dem Entfernen von Kanten (und Komprimieren der Vertices zweiten Grades, die nach dieser Entfernung verbleiben könnten) oder kontrahierende Kanten und Bilden eines Spiegels des gegebenen planaren Graphen. Jeder polyedrische Graph kann auf reduziert werden {Anzeigestil K_{4}} durch eine lineare Anzahl dieser Operationen, und wiederum können die Operationen umgekehrt und die umgekehrten Operationen geometrisch ausgeführt werden, gibt eine polyedrische Realisierung des Graphen. Jedoch, während es einfacher ist zu beweisen, dass eine Reduktionsfolge für diese Art von Argument existiert, und die Reduktionssequenzen sind kürzer, Die geometrischen Schritte, die zur Umkehrung der Sequenz erforderlich sind, sind komplizierter.[13] Anhebende Gleichgewichtsspannung auf dem Diagramm eines Würfels Ein Kegelstumpf, der die gestresste Zeichnung anhebt (mit den gleichen 2d-Positionen) into 3d If a graph is drawn in the plane with straight line edges, dann ist eine Gleichgewichtsspannung als eine Zuordnung von reellen Zahlen ungleich Null definiert (Gewichte) zu den Rändern, mit der Eigenschaft, dass sich jeder Knoten an der Position befindet, die durch den gewichteten Durchschnitt seiner Nachbarn gegeben ist. Laut der Maxwell-Cremona-Korrespondenz, eine Gleichgewichtsspannung kann auf eine stückweise lineare kontinuierliche dreidimensionale Oberfläche angehoben werden, so dass die Kanten, die die Grenzen zwischen den flachen Teilen der Oberfläche bilden, auf die gegebene Zeichnung projizieren. Das Gewicht und die Länge jeder Kante bestimmen den Unterschied in den Neigungen der Oberfläche auf beiden Seiten der Kante, und die Bedingung, dass jeder Scheitelpunkt im Gleichgewicht mit seinen Nachbarn ist, ist äquivalent zu der Bedingung, dass diese Neigungsunterschiede bewirken, dass die Oberfläche in der Nähe des Scheitelpunkts korrekt auf sich selbst trifft. Positive Gewichte werden in konvexe Flächenwinkel zwischen zwei Flächen der stückweise linearen Oberfläche übersetzt, und negative Gewichte führen zu konkaven Diederwinkeln. Umgekehrt, jede kontinuierliche stückweise lineare Fläche entsteht auf diese Weise aus einer Gleichgewichtsspannung. Wenn ein endlicher planarer Graph gezeichnet und so mit einer Gleichgewichtsspannung versehen wird, dass alle inneren Kanten der Zeichnung positive Gewichte haben, und alle Außenkanten haben negative Gewichte, dann durch Übersetzen dieser Spannung in eine dreidimensionale Oberfläche auf diese Weise, und dann Ersetzen der flachen Oberfläche, die das Äußere des Graphen darstellt, durch ihr Komplement in derselben Ebene, man erhält ein konvexes Polyeder, mit der zusätzlichen Eigenschaft, dass seine senkrechte Projektion auf die Ebene kreuzungsfrei ist.[14][15] Die Maxwell-Cremona-Korrespondenz wurde verwendet, um polyedrische Realisierungen polyedrischer Graphen zu erhalten, indem sie mit einer Methode zum Zeichnen planarer Graphen von W kombiniert wurde. T. Alle, die Tutte-Einbettung. Die Methode von Tutte beginnt damit, dass eine Fläche eines polyedrischen Graphen in einer konvexen Position in der Ebene fixiert wird. Diese Fläche wird die äußere Fläche einer Zeichnung eines Graphen. Das Verfahren fährt fort, indem es ein System von linearen Gleichungen in den Scheitelpunktkoordinaten aufstellt, wonach jeder verbleibende Knoten im Durchschnitt seiner Nachbarn platziert werden sollte. Dann, wie Tutte gezeigt hat, Dieses Gleichungssystem hat eine eindeutige Lösung, bei der jede Fläche des Graphen als konvexes Polygon gezeichnet wird.[16] Intuitiv, Diese Lösung beschreibt das Muster, das man erhalten würde, wenn man die Innenkanten des Graphen durch ideale Federn ersetzt und sie in ihren Zustand minimaler Energie einschwingen lässt.[17] Das Ergebnis ist nahezu eine Gleichgewichtsspannung: wenn man jeder inneren Kante das Gewicht eins zuweist, dann ist jeder innere Scheitelpunkt der Zeichnung im Gleichgewicht. Jedoch, es ist nicht immer möglich, den Außenkanten negative Zahlen zuzuweisen, damit sie, zu, im Gleichgewicht sind. Eine solche Zuordnung ist immer dann möglich, wenn die Außenfläche ein Dreieck ist, und so kann diese Methode verwendet werden, um jeden polyedrischen Graphen zu realisieren, der eine dreieckige Fläche hat. Wenn ein polyedrischer Graph keine Dreiecksfläche enthält, sein dualer Graph enthält ein Dreieck und ist ebenfalls polyedrisch, man kann also das Duale auf diese Weise realisieren und dann den ursprünglichen Graphen als das polare Polyeder der dualen Realisierung realisieren.[4][18] Ein alternatives Verfahren zum Realisieren von Polyedern unter Verwendung von Liftings vermeidet Dualität, indem eine beliebige Fläche mit höchstens fünf Scheitelpunkten als äußere Fläche gewählt wird. Jeder polyedrische Graph hat ein solches Gesicht, und durch sorgfältigere Wahl der festen Form dieses Gesichts, die Tutte-Einbettung des restlichen Graphen kann aufgehoben werden.[19] Kreispackung Ein aus einer Kreispackung auf der blauen Mittelkugel realisiertes Polyeder. Jeder Polyederscheitel wird in der Packung durch seinen Horizontkreis dargestellt (rot). Jedes Gesicht wird durch den Kreis dargestellt, der durch seinen Schnittpunkt mit der Kugel gebildet wird.

Nach einer Variante des Kreispackungssatzes, für jeden polyedrischen Graphen, Es gibt ein System von Kreisen in der Ebene oder auf jeder Kugel, die die Scheitelpunkte und Flächen des Graphen darstellen, so dass: jeweils zwei benachbarte Eckpunkte des Graphen werden durch Tangentenkreise dargestellt, jeweils zwei benachbarte Flächen des Graphen werden durch einen Tangentenkreis dargestellt, Jedes Paar aus einem Scheitelpunkt und einer Fläche, die er berührt, wird durch Kreise dargestellt, die sich im rechten Winkel kreuzen, und alle anderen Kreispaare sind voneinander getrennt.[20] Dasselbe System von Kreisen bildet eine Darstellung des dualen Graphen, indem es die Rollen von Kreisen vertauscht, die Scheitelpunkte darstellen, und Kreise, die Gesichter darstellen. Von einer solchen Darstellung auf einer Kugel, eingebettet in den dreidimensionalen euklidischen Raum, man kann ein konvexes Polyeder bilden, das kombinatorisch äquivalent zu dem gegebenen Graphen ist, als Schnittpunkt von Halbräumen, deren Grenzen durch die Gesichtskreise gehen. Von jedem Scheitelpunkt dieses Polyeders, der Horizont auf der Kugel, von diesem Scheitelpunkt aus gesehen, ist der Kreis, der es darstellt. Diese Horizonteigenschaft bestimmt die dreidimensionale Position jedes Scheitelpunkts, und das Polyeder kann äquivalent als die konvexe Hülle der Eckpunkte definiert werden, so positioniert. Die Sphäre wird zur Mittelsphäre der Verwirklichung: Jede Kante des Polyeders ist tangential zur Kugel, an einem Punkt, an dem zwei tangentiale Scheitelkreise zwei tangentiale Flächenkreise kreuzen.[21] Realizations with additional properties Integer coordinates It is possible to prove a stronger form of Steinitz's theorem, dass jeder polyedrische Graph durch ein konvexes Polyeder realisiert werden kann, dessen Koordinaten ganze Zahlen sind.[22] Zum Beispiel, Steinitz' ursprünglicher induktionsbasierter Beweis kann auf diese Weise gestärkt werden. Jedoch, Die ganzen Zahlen, die sich aus Steinitz 'Konstruktion ergeben würden, sind doppelt exponentiell in der Anzahl der Scheitelpunkte des gegebenen polyedrischen Graphen. Das Aufschreiben von Zahlen dieser Größenordnung in Binärschreibweise würde eine exponentielle Anzahl von Bits erfordern.[18] Geometrisch, Dies bedeutet, dass einige Merkmale des Polyeders eine Größe haben können, die doppelt exponentiell größer ist als andere, was die aus diesem Verfahren abgeleiteten Erkenntnisse für Anwendungen beim Zeichnen von Graphen problematisch macht.[4] Nachfolgende Forscher haben Lifting-basierte Realisierungsalgorithmen gefunden, die nur eine lineare Anzahl von Bits pro Scheitelpunkt verwenden.[19][23] Es ist auch möglich, die Anforderung zu lockern, dass die Koordinaten ganze Zahlen sind, und Koordinaten so zuordnen, dass die {Anzeigestil x} -Koordinaten der Eckpunkte sind verschiedene ganze Zahlen im Bereich von 0 zu {Anzeigestil 2n-4} und die anderen beiden Koordinaten sind reelle Zahlen im Einheitsintervall, so dass jede Kante mindestens eine Länge hat, während das gesamte Polyeder ein lineares Volumen hat.[24][25] Es ist bekannt, dass einige polyedrische Graphen auf Gittern mit nur polynomischer Größe realisierbar sind; insbesondere gilt dies für die Pyramiden (Realisierungen von Radgraphen), Prismen (Realisierungen von Prismengraphen), und gestapelte Polyeder (Realisierungen apollinischer Netzwerke).[26] Eine andere Möglichkeit, die Existenz ganzzahliger Realisierungen zu erklären, besteht darin, dass jedes dreidimensionale konvexe Polyeder ein kombinatorisch äquivalentes ganzzahliges Polyeder hat.[22] Zum Beispiel, das reguläre Dodekaeder ist selbst kein ganzzahliges Polyeder, wegen seiner regelmäßigen fünfeckigen Flächen, aber es kann als äquivalentes ganzzahliges Pyritoeder realisiert werden.[19] Dies ist in höheren Dimensionen nicht immer möglich, wo es Polytope gibt (wie diejenigen, die aus der Perles-Konfiguration erstellt wurden) die kein ganzzahliges Äquivalent haben.[27] Equal slopes A Halin graph is a special case of a polyhedral graph, gebildet aus einem planar eingebetteten Baum (ohne Ecken vom Grad zwei) indem die Blätter des Baumes zu einem Kreislauf verbunden werden. Für Halin-Graphen, man kann polyedrische Realisierungen besonderer Art wählen: der äußere Kreis bildet eine horizontale konvexe Grundfläche, und jede andere Fläche liegt direkt über der Basisfläche (wie in den durch Heben realisierten Polyedern), wobei alle diese oberen Flächen die gleiche Neigung haben. Polyederflächen mit Flächen gleicher Neigung über einem beliebigen Basispolygon (nicht unbedingt konvex) kann aus dem geraden Skelett des Polygons konstruiert werden, und eine äquivalente Art, diese Erkenntnis zu beschreiben, ist, dass die zweidimensionale Projektion des Baums auf die Grundfläche sein gerades Skelett bildet. Der Beweis dieses Ergebnisses erfolgt mit Induktion: Jeder verwurzelte Baum kann zu einem kleineren Baum reduziert werden, indem die Blätter von einem internen Knoten entfernt werden, dessen Kinder alle Blätter sind, Der aus dem kleineren Baum gebildete Halin-Graph hat eine Realisierung durch die Induktionshypothese, und es ist möglich, diese Realisierung zu modifizieren, um dem Baumknoten, dessen Kinder entfernt wurden, eine beliebige Anzahl von Blattkindern hinzuzufügen.[28] Specifying the shape of a face In any polyhedron that represents a given polyhedral graph {Anzeigestil G} , die Gesichter von {Anzeigestil G} sind genau die Zyklen in {Anzeigestil G} die sich nicht trennen {Anzeigestil G} in zwei Komponenten: das ist, Entfernen eines Gesichtszyklus aus {Anzeigestil G} lässt den Rest {Anzeigestil G} als zusammenhängender Teilgraph. Solche Zyklen werden periphere Zyklen genannt. Daher, die kombinatorische Struktur der Gesichter (aber nicht ihre geometrischen Formen) wird eindeutig aus der Graphenstruktur bestimmt. Eine weitere Stärkung des Satzes von Steinitz, von Barnette und Grünbaum, besagt, dass für jeden polyedrischen Graphen, jede Seite des Diagramms, und jedes konvexe Polygon, das diese Fläche darstellt, Es ist möglich, eine polyedrische Realisierung des gesamten Graphen zu finden, der die angegebene Form für die bezeichnete Fläche hat. Dies hängt mit einem Satz von Tutte zusammen, dass jeder polyedrische Graph in der Ebene gezeichnet werden kann, wobei alle Flächen konvex sind und jede festgelegte Form für seine Außenfläche vorhanden ist. Jedoch, Die nach Tuttes Methode erzeugten planaren Graphzeichnungen heben sich nicht unbedingt zu konvexen Polyedern auf. Stattdessen, Barnette und Grünbaum beweisen dieses Ergebnis mit einem induktiven Verfahren.[29] Es ist auch immer möglich, einen polyedrischen Graphen gegeben {Anzeigestil G} und einem beliebigen Zyklus {Anzeigestil C} in {Anzeigestil G} , eine Realisierung zu finden, wofür {Anzeigestil C} bildet unter Parallelprojektion die Silhouette der Realisierung.[30] Tangent spheres The realization of polyhedra using the circle packing theorem provides another strengthening of Steinitz's theorem: Jeder 3-verbundene planare Graph kann als konvexes Polyeder so dargestellt werden, dass alle seine Kanten dieselbe Einheitskugel berühren, die Mittelkugel des Polyeders.[21] Indem eine sorgfältig ausgewählte Möbius-Transformation einer Kreispackung durchgeführt wird, bevor sie in ein Polyeder umgewandelt wird, Es ist möglich, eine polyedrische Realisierung zu finden, die alle Symmetrien des zugrunde liegenden Graphen realisiert, in dem Sinne, dass jeder Graphautomorphismus eine Symmetrie der polyedrischen Realisierung ist.[31][32] Allgemeiner, wenn {Anzeigestil G} ist ein polyedrischer Graph und {Anzeigestil K} ist ein beliebiger glatter dreidimensionaler konvexer Körper, Es ist möglich, eine polyedrische Darstellung von zu finden {Anzeigestil G} bei dem alle Kanten tangential sind {Anzeigestil K} .[33] Kreispackungsmethoden können auch verwendet werden, um die Graphen von Polyedern zu charakterisieren, die eine Umkreisung durch alle ihre Ecken haben, oder eine Insphere, die alle ihre Gesichter berührt. (Die Polyeder mit Umkreis sind auch in der hyperbolischen Geometrie als ideale Polyeder von Bedeutung.) In beiden Fällen, Die Existenz einer Kugel entspricht der Lösbarkeit eines Systems linearer Ungleichungen auf positiven reellen Variablen, die jeder Kante des Diagramms zugeordnet sind. Im Fall der Insphäre, diese Variablen müssen in jedem Flächenzyklus des Diagramms genau eins ergeben, und zu mehr als einem in jedem Nicht-Gesichts-Zyklus. Duell, für die Umrundung, die Variablen müssen sich an jedem Scheitelpunkt zu eins summieren, und mehr als einer über jeden Schnitt mit zwei oder mehr Eckpunkten auf jeder Seite des Schnitts. Obwohl es exponentiell viele lineare Ungleichungen geben kann, die erfüllt werden müssen, eine Lösung (wenn einer existiert) kann in polynomieller Zeit unter Verwendung der Ellipsoidmethode gefunden werden. Die Werte der Variablen aus einer Lösung bestimmen die Winkel zwischen Kreispaaren in einer Kreispackung, deren zugehöriger Polyeder die gewünschte Beziehung zu seiner Kugel hat.[34][35] Zugehörige Ergebnisse Die Graphen dreidimensionaler nichtkonvexer Polyeder sind möglicherweise nicht verbunden (links), und selbst für topologisch sphärische Polyeder, deren Flächen einfache Polygone sind, sind diese Graphen möglicherweise nicht 3-verbunden (Rechts).[36] In jeder Dimension höher als drei, Das algorithmische Steinitz-Problem besteht darin, zu bestimmen, ob ein gegebenes Gitter das Seitengitter eines konvexen Polytops ist. Es ist unwahrscheinlich, dass es eine polynomiale Zeitkomplexität hat, da es NP-hart und stärker vollständig für die Existenztheorie der Realen ist, sogar für vierdimensionale Polytope, by Richter-Gebert's universality theorem.[37] Hier, Die Existenztheorie der Realzahlen ist eine Klasse von Rechenproblemen, die formuliert werden können, um reelle Variablen zu finden, die ein gegebenes System polynomialer Gleichungen und Ungleichungen erfüllen. Für das algorithmische Steinitz-Problem, Die Variablen eines solchen Problems können die Scheitelpunktkoordinaten eines Polytops sein, und die Gleichungen und Ungleichungen können verwendet werden, um die Ebenheit jeder Fläche in dem gegebenen Flächengitter und die Konvexität jedes Winkels zwischen Flächen zu spezifizieren. Vollständigkeit bedeutet, dass jedes andere Problem dieser Klasse in eine äquivalente Instanz des algorithmischen Steinitz-Problems transformiert werden kann, in polynomieller Zeit. Die Existenz einer solchen Transformation impliziert dies, wenn das algorithmische Steinitz-Problem eine Lösung in Polynomialzeit hat, dann gilt dies für jedes Problem in der Existenztheorie der Realen, und jedes Problem in NP.[38] Jedoch, weil ein gegebener Graph mehr als einem Flächengitter entsprechen kann, Es ist schwierig, dieses Vollständigkeitsergebnis auf das Problem der Erkennung der Graphen von 4-Polytopen zu erweitern. Die Bestimmung der Rechenkomplexität dieses Graphenerkennungsproblems bleibt offen.[39] Forscher haben auch graphentheoretische Charakterisierungen der Graphen bestimmter spezieller Klassen dreidimensionaler nichtkonvexer Polyeder gefunden[36][40] und vierdimensionale konvexe Polytope.[39][41][42] Jedoch, in beiden Fällen, Das allgemeine Problem bleibt ungelöst. In der Tat, sogar das Problem zu bestimmen, welche vollständigen Graphen die Graphen nichtkonvexer Polyeder sind (außer {Anzeigestil K_{4}} für den Tetraeder und {Anzeigestil K_{7}} für das Kaiserpolyeder) bleibt ungelöst.[43] Der Satz von Eberhard charakterisiert teilweise die Multisets von Polygonen, die kombiniert werden können, um die Flächen eines konvexen Polyeders zu bilden. Es kann bewiesen werden, indem man einen 3-verbundenen planaren Graphen mit dem gegebenen Satz von Polygonflächen bildet, und dann das Theorem von Steinitz anwenden, um eine polyedrische Realisierung dieses Graphen zu finden.[3] László Lovász hat eine Übereinstimmung zwischen polyedrischen Darstellungen von Graphen und Matrizen gezeigt, die die Invarianten des Colin de Verdière-Graphen derselben Graphen realisieren. Die Colin-de-Verdière-Invariante ist der maximale Corank einer gewichteten Adjazenzmatrix des Graphen, unter einigen zusätzlichen Bedingungen, die für polyedrische Graphen irrelevant sind. Dies sind quadratische symmetrische Matrizen, die durch die Eckpunkte indiziert sind, mit dem Scheitelgewicht {Anzeigestil i} im Diagonalkoeffizienten {Anzeigestil M_{ich,ich}} und mit dem Gewicht der Kante {Anzeigestil i,j} in den Nebendiagonalkoeffizienten {Anzeigestil M_{ich,j}} und {Anzeigestil M_{j,ich}} . Wenn Eckpunkte {Anzeigestil i} und {Anzeigestil j} sind nicht benachbart, der Koeffizient {Anzeigestil M_{ich,j}} muss Null sein. Diese Invariante ist genau dann höchstens drei, wenn der Graph ein planarer Graph ist. Wie Lovász zeigt, wenn der Graph polyedrisch ist, Eine Darstellung davon als Polyeder kann erhalten werden, indem eine gewichtete Adjazenzmatrix mit Korank drei gefunden wird, Finden von drei Vektoren, die eine Basis für seinen Nullraum bilden, Verwenden der Koeffizienten dieser Vektoren als Koordinaten für die Eckpunkte eines Polyeders, und geeignetes Skalieren dieser Scheitelpunkte.[44] History The history of Steinitz's theorem is described by Grünbaum (2007),[45] der sein erstes Erscheinen in kryptischer Form in einer Publikation von Ernst Steinitz notiert, ursprünglich eingeschrieben 1916.[6] Weitere Einzelheiten lieferte Steinitz in späteren Vorlesungsnotizen, veröffentlicht nach seinem 1928 Tod. Obwohl moderne Behandlungen des Satzes von Steinitz ihn als graphentheoretische Charakterisierung von Polyedern angeben, Steinitz verwendete nicht die Sprache der Graphen.[45] Die graphentheoretische Formulierung des Theorems wurde Anfang der 1960er Jahre von Branko Grünbaum und Theodore Motzkin eingeführt, mit seinem Beweis auch in Grünbaums Graphentheorie umgewandelt 1967 text Konvexe Polytope.[45] Die Arbeit von Epifanov über Δ-Y- und Y-Δ-Transformationen, Stärkung des Beweises von Steinitz, war durch andere Probleme motiviert als die Charakterisierung von Polyedern. Truemper (1989) schreibt Grünbaum die Beobachtung der Relevanz dieser Arbeit für das Theorem von Steinitz zu.[11] Die Maxwell-Cremona-Korrespondenz zwischen Spannungsdiagrammen und polyedrischen Anhebungen wurde in einer Reihe von Artikeln von James Clerk Maxwell aus entwickelt 1864 zu 1870, basierend auf früheren Arbeiten von Pierre Varignon, Wilhelm Rankine, und andere, und wurde im späten 19. Jahrhundert von Luigi Cremona populär gemacht.[46] The observation that this correspondence can be used with the Tutte embedding to prove Steinitz's theorem comes from Eades & Garvan (1995).[4] Der Kreispackungssatz wurde von Paul Koebe in bewiesen 1936[47][48] und (unabhängig) Wiedersehen. M. Andreev rein 1970;[48][49] Es wurde Mitte der 1980er Jahre von William Thurston populär gemacht, wer (trotz der Berufung auf Koebe und Andreev) wird oft als einer seiner Entdecker anerkannt.[48] Andreevs Version des Theorems wurde bereits als Steinitz-ähnliche Charakterisierung für bestimmte Polyeder im hyperbolischen Raum formuliert,[49] und die Verwendung von Kreispackungen zur Realisierung von Polyedern mit Mittelkugeln stammt aus der Arbeit von Thurston.[50] Das Problem der Charakterisierung von Polyedern mit eingeschriebenen oder umschriebenen Kugeln, schließlich mit einer Methode gelöst, die auf Kreispackungsrealisierungen basiert, geht zurück auf unveröffentlichte Arbeiten von René Descartes circa 1630[51] und an Jakob Steiner in 1832;[34][52] Die ersten Beispiele für Polyeder, die keine Realisierung mit einer Umkreis- oder Innensphäre haben, wurden von Steinitz in gegeben 1928.[34][53] References ^ Weisstein, Erich W., "Polyederdiagramm", MathWorld ^ Sturmfels, Bernd (1987), "Grenzkomplexe konvexer Polytope können nicht lokal charakterisiert werden", Zeitschrift der London Mathematical Society, Zweite Serie, 35 (2): 314–326, CiteSeerX 10.1.1.106.3222, doi:10.1112/jlms/s2-35.2.314, HERR 0881520 ^ Nach oben springen: a b Malkewitsch, Joseph, "Techniken zum Beweis kombinatorischer Theoreme über 3-Polytope", Geometrische Strukturen (Kursnotizen), City University of New York ^ Hochspringen zu: a b c d Eades, Peter; Garwan, Patrick (1995), "Zeichnen von gestressten planaren Graphen in drei Dimensionen", in Brandenburg, Franz Josef (ed.), Diagramm zeichnen, Symposium zum Zeichnen von Graphen, GD '95, Passau, Deutschland, September 20-22, 1995, Verfahren, Vorlesungsunterlagen in Informatik, vol. 1027, Springer, pp. 212–223, doi:10.1007/BFb0021805, HERR 1400675 ^ Nach oben springen: a b c Grünbaum, Branko (2003), "13.1 Satz von Steinitz", Konvexe Polytope, Abschlusstexte in Mathematik, vol. 221 (2und Aufl.), Springer-Verlag, pp. 235–244, ISBN 0-387-40409-0 ^ Nach oben springen: a b Steinitz, Ernst (1922), "IIIAB12: Polyeder und Raumeinteilungen", Encyclopädie der mathematischen Wissenschaften (auf Deutsch), vol. Band 3 (Geometrien), pp. 1–139, Abgeschlossen am 31. August 1916 ^ Technisch gesehen, dieser Graph ist das 1-Skelett; Siehe Grünbaum (2003), p. 138, und Ziegler (1995), p. 64. ^ Nach oben springen: a b Ziegler, Günter M. (1995), "Kapitel 4: Satz von Steinitz für 3-Polytope", Vorlesungen über Polytope, Abschlusstexte in Mathematik, vol. 152, Springer-Verlag, pp. 103–126, ISBN 0-387-94365-X ^ Balinski, M. L. (1961), "Über die Graphenstruktur konvexer Polyeder im n-Raum", Pacific Journal of Mathematics, 11 (2): 431–434, doi:10.2140/pjm.1961.11.431, HERR 0126765 ^ Epifanov, G. v. (1966), "Reduktion eines ebenen Graphen auf eine Kante durch Stern-Dreieck-Transformationen", Doklady Akademii Nauk SSSR (auf Russisch), 166: 19–22, HERR 0201337, Zbl 0149.21301 ^ Nach oben springen: a b Truemper, K. (1989), "Über die Delta-Wye-Reduktion für planare Graphen", Zeitschrift für Graphentheorie, 13 (2): 141–148, doi:10.1002/jgt.3190130202, HERR 0994737 ^ Chang, Hsien Chih; Kossarini, Markus; Erickson, Jeff (2019), "Untere Schranken für die elektrische Reduktion auf Oberflächen", im Barett, Kieme; Wang, Jesus (Hrsg.), 35th International Symposium on Computational Geometry (SoCG 2019), Leibniz International Proceedings in Informatics (LIPs), vol. 129, Tagesstuhl, Deutschland: Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, pp. 25:1–25:16, arXiv:1707.04683, doi:10.4230/LIPIcs.SoCG.2019.25, ISBN 978-3-95977-104-7, HERR 3968611 ^ Barnett, David W.; Grünbaum, Branko (1969), "Zum Satz von Steinitz über konvexe 3-Polytope und zu einigen Eigenschaften planarer Graphen", in Chartrand, G.; Kapoor, S. F. (Hrsg.), Die vielen Facetten der Graphentheorie: Proceedings of the Conference an der Western Michigan University, Kalamazoo, MI., Oktober 31 - November 2, 1968, Vorlesungsunterlagen in Mathematik, vol. 110, Springer, pp. 27–40, doi:10.1007/BFb0060102, HERR 0250916 ^ Maxwell, J. Sachbearbeiter (1864), "Über reziproke Figuren und Kräftediagramme", Philosophisches Magazin, 4Serie, 27 (182): 250–261, doi:10.1080/14786446408643663 ^ Weißley, Walter (1982), "Bewegungen und Spannungen projizierter Polyeder", Strukturelle Topologie, 7: 13–38, hdl:2099/989, HERR 0721947 ^ Tutte, W. T. (1963), "Wie man ein Diagramm zeichnet", Verfahren der London Mathematical Society, 13: 743–767, doi:10.1112/plms/s3-13.1.743, HERR 0158387 ^ Brandes, Ulrich (2001), "Rückgriff auf physikalische Analogien", in Kaufmann, Michael; Wagner, Dorothee (Hrsg.), Diagramme zeichnen: Methoden und Modelle, Vorlesungsunterlagen in Informatik, vol. 2025, Berlin: Springer, pp. 71–86, CiteSeerX 10.1.1.9.5023, doi:10.1007/3-540-44969-8_4, HERR 1880146 ^ Nach oben springen: a b Onn, Schmuel; Sturmfels, Bernd (1994), "Ein quantitativer Satz von Steinitz", Beiträge zur Algebra und Geometrie, 35 (1): 125–129, HERR 1287206 ^ Nach oben springen: a b c Gefärbtes Band, Ares; Rote, Günter; Schulz, André (2011), "Kleine Gittereinbettungen von 3-Polytopen", Discrete & Computational Geometry, 45 (1): 65–87, arXiv:0908.0488, doi:10.1007/s00454-010-9301-0, HERR 2765520, S2CID 10141034 ^ Brightwell, Graham R.; Scheinermann, Eduard R. (1993), "Darstellungen planarer Graphen", SIAM-Journal für diskrete Mathematik, 6 (2): 214–229, doi:10.1137/0406017, HERR 1215229 ^ Nach oben springen: a b Ziegler, Günter M. (2007), "Konvexe Polytope: Extremalkonstruktionen und f-Vektorformen. Abschnitt 1.3: Satz von Steinitz über Kreispackungen", bei Müller, Esra; Reiner, Sieger; Sturmfels, Bernd (Hrsg.), Geometrische Kombinatorik, IAS/Park City Mathematics Series, vol. 13, Amerikanische Mathematische Gesellschaft, pp. 628–642, ISBN 978-0-8218-3736-8 ^ Nach oben springen: a b Grünbaum (2003), Satz 13.2.3, p. 244, gibt dies in äquivalenter Form an, wobei die Koordinaten rationale Zahlen sind. ^ Buchin, Kevin; Schulz, André (2010), "Über die Anzahl der Spannbäume, die ein planarer Graph haben kann", im Berg, Markieren; Meier, Ulrich (Hrsg.), Algorithmen - ESA 2010, 18th Annual European Symposium, Liverpool, Vereinigtes Königreich, September 6-8, 2010, Verfahren, Teil I, Vorlesungsunterlagen in Informatik, vol. 6346, Springer, pp. 110–121, CiteSeerX 10.1.1.746.942, doi:10.1007/978-3-642-15775-2_10, ISBN 978-3-642-15774-5, HERR 2762847, S2CID 42211547 ^ Chrobak, Marek; Goodrich, Michael T.; Tamassia, Roberto (1996), "Konvexe Zeichnungen von Graphen in zwei und drei Dimensionen", Proceedings des 12. ACM-Symposiums zur Computergeometrie (SoCG '96), ACM, pp. 319–328, doi:10.1145/237218.237401, S2CID 1015103 ^ Schulz, André (2011), "Zeichnen von 3-Polytopen mit guter Scheitelpunktauflösung", Zeitschrift für Graphenalgorithmen und -anwendungen, 15 (1): 33–52, doi:10.7155/Ja wirklich.00216, HERR 2776000 ^ Demaine, Erich D.; Schulz, André (2017), "Einbetten gestapelter Polytope in ein Gitter mit Polynomgröße", Discrete & Computational Geometry, 57 (4): 782–809, arXiv:1403.7980, doi:10.1007/s00454-017-9887-6, HERR 3639604, S2CID 104867 ^ Grünbaum (2003), p. 96a. ^ Aichholzer, Oswin; Cheng, Howard; Devadoss, Satjan L.; Hackl, Thomas; Huber, Stefan; Li, Brian; Risteski, Andrej (2012), "Was macht einen Baum zu einem geraden Skelett??" (Pdf), Proceedings of the 24th Canadian Conference on Computational Geometry (CCCG'12) ^ Barnett, David W.; Grünbaum, Branko (1970), "Vorbelegung der Gesichtsform", Pacific Journal of Mathematics, 32 (2): 299–306, doi:10.2140/pjm.1970.32.299, HERR 0259744 ^ Barnett, David W. (1970), "Projektionen von 3-Polytopen", Israelisches Journal für Mathematik, 8 (3): 304–308, doi:10.1007/BF02771563, HERR 0262923, S2CID 120791830 ^ Hart, Georg W. (1997), "Berechnung kanonischer Polyeder", Mathematica in Bildung und Forschung, 6 (3): 5–10 ^ Bern, Marschall W.; Eppstein, David (2001), "Optimale Möbius-Transformationen für Informationsvisualisierung und Vernetzung", in Dehne, Frank K. H. A.; Sack, Jörg Rüdiger; Tamassia, Roberto (Hrsg.), Algorithmen und Datenstrukturen, 7th Internationaler Workshop, WADS 2001, Vorsehung, RI, Vereinigte Staaten von Amerika, August 8-10, 2001, Verfahren, Vorlesungsunterlagen in Informatik, vol. 2125, Springer, pp. 14–25, arXiv:cs/0101006, doi:10.1007/3-540-44634-6_3, S2CID 3266233 ^ Schramm, Oded (1992), "Wie man ein Ei einsperrt", Mathematische Entdeckungen, 107 (3): 543–560, Bibcode:1992InMat.107..543S, doi:10.1007/BF01231901, HERR 1150601, S2CID 189830473 ^ Nach oben springen: a b c Rivin, Igor (1996), "Eine Charakterisierung idealer Polyeder im hyperbolischen 3-Raum", Annalen der Mathematik, Zweite Serie, 143 (1): 51–70, doi:10.2307/2118652, JSTOR 2118652, HERR 1370757 ^ Dillencourt, Michael B.; Schmied, Warren D. (1996), "Graphentheoretische Bedingungen für Beschreibbarkeit und Delaunay-Realisierbarkeit", Diskrete Mathematik, 161 (1-3): 63–77, doi:10.1016/0012-365X(95)00276-3, HERR 1420521 ^ Nach oben springen: a b Eppstein, David; Mumford, Elena (2014), "Steinitz-Theoreme für einfache orthogonale Polyeder", Zeitschrift für Computergeometrie, 5 (1): 179–244, doi:10.20382/jocg.v5i1a10, HERR 3259910, S2CID 8531578 ^ Richter-Gebert, Jürgen (1996), Realisierungsräume von Polytopen, Vorlesungsunterlagen in Mathematik, vol. 1643, Springer-Verlag, CiteSeerX 10.1.1.2.3495, doi:10.1007/BFb0093761, ISBN 978-3-540-62084-6, HERR 1482230 ^ Schäfer, Markus (2013), "Realisierbarkeit von Graphen und Verknüpfungen", in Pac, John (ed.), Dreißig Essays zur Theorie geometrischer Graphen, New York: Springer, pp. 461–482, CiteSeerX 10.1.1.220.9651, doi:10.1007/978-1-4614-0110-0_24, HERR 3205168 ^ Nach oben springen: a b Eppstein, David (2020), "Baumkronen und ihre Graphen", Discrete & Computational Geometry, 64 (2): 259–289, arXiv:1510.03152, doi:10.1007/s00454-020-00177-0, HERR 4131546, S2CID 213885326 ^ Hong, Seok-Hee; Nagamochi, Hiroshi (2011), "Erweiterung des Satzes von Steinitz auf nach oben gerichtete sternförmige Polyeder und sphärische Polyeder", Algorithmen, 61 (4): 1022–1076, doi:10.1007/s00453-011-9570-x, HERR 2852056, S2CID 12622357 ^ Blind, Roswitha; Mani-Levitska, Peter (1987), "Rätsel und Polytop-Isomorphismen", Mathematische Gleichungen, 34 (2-3): 287–297, doi:10.1007/BF01830678, HERR 0921106, S2CID 120222616 ^ Kalai, Gil (1988), "Eine einfache Möglichkeit, ein einfaches Polytop von seinem Graphen zu unterscheiden", Zeitschrift für kombinatorische Theorie, Serie A, 49 (2): 381–383, doi:10.1016/0097-3165(88)90064-7, HERR 0964396 ^ Ziegler, Günter M. (2008), "Polyederflächen hoher Gattung", Diskrete Differentialgeometrie, Oberwolfacher Seminare, vol. 38, Springer, pp. 191–213, arXiv:math/0412093, doi:10.1007/978-3-7643-8621-4_10, ISBN 978-3-7643-8620-7, HERR 2405667, S2CID 15911143 ^ Lovász, Lászlo (2001), "Steinitz-Darstellungen von Polyedern und der Colin-de-Verdière-Zahl", Zeitschrift für kombinatorische Theorie, Serie B, 82 (2): 223–236, doi:10.1006/jctb.2000.2027, HERR 1842113 ^ Nach oben springen: a b c Grünbaum, Branko (2007), "Graphen von Polyedern; Polyeder als Graphen", Diskrete Mathematik, 307 (3–5): 445–463, doi:10.1016/j.disc.2005.09.037, hdl:1773/2276, HERR 2287486 ^ Erickson, Jeff; Lin, Patrick (2020), "Eine toroidale Maxwell-Cremona-Delaunay-Korrespondenz", in Cabella, Sergio; Chen, Danny Z. (Hrsg.), 36th International Symposium on Computational Geometry (SoCG 2020), Leibniz International Proceedings in Informatics (LIPs), vol. 164, Tagesstuhl, Deutschland: Schloss Dagstuhl–Leibniz-Zentrum für Informatik, pp. 40:1–40:17, arXiv:2003.10057, doi:10.4230/LIPics.SoCG.2020.40, ISBN 978-3-95977-143-6, S2CID 209514295 ^ Koebe, Paul (1936), "Kontaktprobleme der Konformen Abbildung", Berichte über die Verhandlungen der Sächsischen Akademie der Wissenschaften zu Leipzig: Mathematisch-Physische Klasse (auf Deutsch), 88: 141–164 ^ Nach oben springen: a b c Stephenson, Kenneth (2003), "Kreisverpackung: eine mathematische Geschichte" (Pdf), Bekanntmachungen der American Mathematical Society, 50 (11): 1376–1388, CiteSeerX 10.1.1.101.5592, HERR 2011604 ^ Nach oben springen: a b Andrejew, E. M. (1970), "Konvexe Polyeder in Lobačevskiĭ-Räumen", Mathematicheskii Sbornik, 81 (123): 445–478, HERR 0259734 ^ Schramm, Oded (1991), "Existenz und Eindeutigkeit von Packungen mit spezifizierter Kombinatorik", Israelisches Journal für Mathematik, 73 (3): 321–341, doi:10.1007/BF02773845, HERR 1135221, S2CID 121855202; siehe Diskussion nach Korollar 3.8, p. 329 ^ Federico, Pasqual Josef (1982), Descartes über Polyeder: Eine Studie der "Von den festen Elementen", Quellen in der Geschichte der Mathematik und Physik, vol. 4, Springer, p. 52 ^ Steiner, Jakob (1832), "Frage 77", Systematische Entwicklung der Abhängigkeit geometrischer Gestalten von einander (auf Deutsch), Berlin: G. Finke, p. 316 ^ Steinitz, Ernst (1928), "Über isoperimetrische Probleme bei konvexen Polyedern", Journal für die Reine und Angewandte Mathematik (auf Deutsch), 1928 (159): 133–143, doi:10.1515/crll.1928.159.133, HERR 1581158, S2CID 199546274 Kategorien: Planare GraphenGeometrische GraphentheoriePolyedrische KombinatorikTheoreme der GraphentheorieTheoreme der diskreten Geometrie