Planare Graph

"Triangular Graph" leitet hier weiter. Für Zeilendiagramme komplette Graphen siehe Zeilendiagramm § stark regelmäßige und perfekte Liniengrafiken. Für triangulierte Grafiken siehe Akkordgrafik. Für Datendiagramme, die über drei Variablen aufgetragen wurden, siehe Ternäre Handlung.
Beispieldiagramme
Planar Nonplanar
Butterfly graph.svg
Schmetterlingsgrafik 		Complete graph K5.svg
Komplette Graph K5
CGK4PLN.svg
Komplette Graph
K4 		Biclique K 3 3.svg
Dienstprogrammdiagramm K3,3

Im Graphentheorie, a Planare Graph ist ein Graph das kann sein eingebettet in dem Flugzeug, d.h. Mit anderen Worten, es kann so gezeichnet werden, dass sich keine Kanten gegenseitig überschreiten.[1][2] Eine solche Zeichnung heißt a Flugzeugdiagramm oder planare Einbettung der Grafik. Ein Ebenendiagramm kann als planarer Diagramm mit einer Zuordnung von jedem Knoten bis zu einem Punkt in einer Ebene und von jeder Kante zu a definiert werden Flugzeugkurve Auf dieser Ebene, so dass die extremen Punkte jeder Kurve die Punkte sind, die von ihren Endknoten abgebildet sind und alle Kurven außer ihren extremen Punkten disjunkt sind.

Jedes Diagramm, das auf einer Ebene gezeichnet werden kann Kugel auch und umgekehrt mittels Stereografische Projektion.

Ebenendiagramme können von codiert werden Kombinatorische Karten oder Rotationssysteme.

Ein Äquivalenzklasse von Topologisch äquivalent Zeichnungen auf der Kugel, normalerweise mit zusätzlichen Annahmen wie dem Fehlen von Isthmus, heißt a Planare Karte. Obwohl ein Ebenendiagramm eine hat extern oder ungebunden GesichtKeine der Gesichter einer planaren Karte hat einen bestimmten Status.

Planare Graphen verallgemeinern auf Grafiken, die auf einer Oberfläche einer gegebenen Oberfläche zeichnen werden können Gattung. In dieser Terminologie haben planare Grafiken Gattung0, da die Ebene (und die Kugel) Oberflächen der Gattung 0 sind.Grafikeinbettung"Für andere verwandte Themen.

Planaritätskriterien

Kuratowskis und Wagners Theoreme

Beweis ohne Worte das a Hypercube -Diagramm ist Nicht-Planar Verwendung Kuratowskis oder Wagners Theoreme und entweder finden K5 (oben) oder K3,3 (Unterseite) Subgraphen

Das Polieren Mathematiker Kazimierz Kuratowski lieferte eine Charakterisierung von planaren Graphen in Bezug auf Verbotene Grafiken, jetzt bekannt als als Kuratowskis Theorem:

A Finite Graph ist planar dann und nur dann, wenn es enthält kein a Untergraph das ist ein Unterteilung des Komplette Graph K5 oder der Komplette zweigliedrige Grafik K3,3 (Dienstprogrammdiagramm).

A Unterteilung eines Diagramms resultiert aus dem Einfügen von Scheitelpunkten in Kanten (z. B. eine Kantewechsel • -- • zu • - • - • ) Null oder mehrmals.

Ein Beispiel für ein Diagramm ohne Nr. K5 oder K3,3 Untergraph. Es enthält jedoch eine Unterteilung von K3,3 und ist daher nicht planar.

Anstatt Unterteilungen zu berücksichtigen, Wagners Theorem befasst sich mit Minderjährige:

Ein endliches Diagramm ist planar, wenn es nur dann ist, wenn es nicht hat K5 oder K3,3 Als ein unerheblich.

A unerheblich eines Diagramms resultiert aus der Einnahme eines Untergraphen und einem wiederholten Vertrag einer Kante in einen Scheitelpunkt, wobei jeder Nachbar der ursprünglichen Endvertempfe zum Nachbar des neuen Scheitelpunkts wird.

Eine Animation, die zeigt, dass die Petersen Graph enthält ein kleines isomorphes isomorph K3,3 Grafik und ist daher nicht planarer

Klaus Wagner Im Allgemeinen gefragt, ob eine geringfügige Klasse von Graphen durch einen endlichen Satz von "bestimmt wird"Verbotene Minderjährige". Dies ist jetzt das Robertson -Seymour -Theorem, in einer langen Reihe von Papieren bewiesen. In der Sprache dieses Satzes, K5 und K3,3 sind die verbotenen Minderjährigen für die Klasse der endlichen planaren Graphen.

Andere Kriterien

In der Praxis ist es schwierig, das Kriterium von Kuratowski zu verwenden, um schnell zu entscheiden, ob ein bestimmter Diagramm planar ist. Es gibt jedoch schnell Algorithmen für dieses Problem: für eine Grafik mit n Scheitelpunkte ist möglich, rechtzeitig zu bestimmen O(n) (lineare Zeit), ob der Diagramm planar sein kann oder nicht (siehe Planaritätstest).

Für eine einfache, verbundene, planare Graphen mit v Eckpunkte und e Kanten und f Gesichter halten die folgenden einfachen Bedingungen für v ≥ 3:

  • Satz 1. e ≤ 3v – 6;
  • Satz 2. Wenn es keine Zyklen mit Länge 3 gibt, dann e ≤ 2v – 4.
  • Satz 3. f ≤ 2v – 4.

In diesem Sinne sind planare Graphen spärliche Grafiken, in dem sie nur haben O(v) Kanten, asymptotisch kleiner als das Maximum O(v2). Der Graph K3,3Zum Beispiel hat 6 Scheitelpunkte, 9 Kanten und keine Längenzyklen 3. Daher kann es nicht planar sein. Diese Theoreme bieten die erforderlichen Bedingungen für Planarität, die nicht ausreichend Bedingungen sind und daher nur verwendet werden können, um zu beweisen, dass ein Diagramm nicht planar ist, nicht, dass es planar ist. Wenn sowohl Satz 1 als auch 2 ausfallen, können andere Methoden angewendet werden.

Eigenschaften

Eulers Formel

Hauptartikel: Euler charakteristische § Ebenendiagramme

Eulers Formel stellt fest, dass wenn eine endliche, in Verbindung gebracht, planare Graphen werden in der Ebene ohne Kantenkreuzungen gezeichnet, und v ist die Anzahl der Eckpunkte, e ist die Anzahl der Kanten und f ist die Anzahl der Gesichter (Regionen, die durch Kanten begrenzt sind, einschließlich der äußeren, unendlich großen Region), dann

Als Illustration in der Schmetterlingsgrafik oben gegeben, v = 5, e = 6 und f = 3. Im Allgemeinen gilt das Eigentum für alle planaren Graphen von f Gesicht v – e + f ein Invariante. Da die Eigenschaft für alle Grafiken mit gilt f = 2, durch mathematische Induktion Es gilt für alle Fälle. Die Formel von Euler kann auch wie folgt bewiesen werden: Wenn die Grafik nicht a ist Baumund entfernen Sie dann eine Kante, die a vervollständigt Kreislauf. Dies senkt beide e und f durch eins gehen v – e + f Konstante. Wiederholen Sie, bis das verbleibende Diagramm ein Baum ist. Bäume haben v = e + 1 und f = 1, nachgeben v – e + f = 2, ich. Die Euler charakteristisch ist 2.

In einem endlichen, in Verbindung gebracht, einfach, Planar -Diagramm, jedes Gesicht (außer möglicherweise die äußere) wird von mindestens drei Kanten begrenzt und jeder Kante berührt in den meisten zwei Gesichtern; Mit der Formel von Euler kann man dann zeigen, dass diese Grafiken sind spärlich in dem Sinne, dass wenn v ≥ 3:

A Schlegel -Diagramm eines regulären DodecaederBildung eines planaren Diagramms aus einem konvexen Polyeder.

Die Eulers Formel ist ebenfalls gültig für Konvexe Polyeder. Dies ist kein Zufall: Jedes konvexe Polyeder kann in ein verbundenes, einfaches, planares Diagramm verwandelt werden Schlegel -Diagramm des Polyeders, a Perspektivprojektion des Polyeders auf eine Ebene mit dem Mitte der Perspektive in der Nähe des Zentrums eines der Gesichter des Polyeders. Nicht jedes planare Diagramm entspricht auf diese Weise einem konvexen Polyeder: Die Bäume nicht. Steinitzs Satz sagt, dass die Polyedrische Grafiken aus konvexem Polyeder gebildet sind genau das endliche 3-verbunden Einfache planare Graphen. Allgemeiner gilt die Formel von Euler für jedes Polyeder, dessen Gesichter sind einfache Polygone das bildet eine Oberfläche Topologisch äquivalent in einer Sphäre, unabhängig von seiner Konvexität.

Durchschnittsgrad

Vernetzte planare Diagramme mit mehr als einer Kante gehorchen der Ungleichheit 2e ≥ 3f, weil jedes Gesicht mindestens drei Vorfälle mit Gesichtskanten hat und jede Kante genau zwei Fälle trägt. Es folgt durch algebraische Transformationen dieser Ungleichheit mit Eulers Formel v – e + f = 2 Das für endliche planare Graphen ist der Durchschnittsgrad streng weniger als 6. Diagramme mit höherem Durchschnittsgrad können nicht planar sein.

Münzgraphen

Hauptartikel: Circle Packing Theorem
Beispiel für den Kreisverpackungssatz auf K −5, die komplette Grafik auf fünf Eckpunkten, abzüglich einer Kante.

Wir sagen, dass zwei in einer Ebene gezogene Kreise Kuss (oder küssen) Wenn sie sich in genau einem Punkt kreuzen. Ein "Münzgraf" ist ein Diagramm, das durch einen Satz von Kreisen gebildet wird, von denen keine zwei überlappende Innenräume haben, indem für jeden Kreis ein Scheitelpunkt für jeden Kreis und eine Kante für jedes Kreispaar küssen. Das Circle Packing Theorem, zuerst nachgewiesen von Paul Koebe Im Jahr 1936 gibt an, dass ein Diagramm nur dann planar ist, wenn es sich um eine Münzgrafik handelt.

Dieses Ergebnis liefert einen einfachen Beweis von Fárys Satz, dass jedes einfache planare Diagramm in der Ebene so eingebettet werden kann, dass seine Kanten gerade sind Liniensegmente das überquert sich nicht. Wenn einer jeden Scheitelpunkt des Diagramms in der Mitte des entsprechenden Kreises in einer Münzgraphendarstellung platziert, überqueren die Liniensegmente zwischen Zentren von Küssen Kreisen keine der anderen Kanten.

Planare Graphendichte

Das Bruchkoeffizient oder Dichte D eines planaren Diagramms oder eines Netzwerks ist das Verhältnis der Zahl f – 1 von begrenzten Gesichtern (die gleiche wie die Schaltungsrang der Grafik, von Das Planaritätskriterium von Mac Lane) durch seine maximal möglichen Werte 2v – 5 für eine Grafik mit v Scheitelpunkte:

Die Dichte gehorcht 0 ≤ D ≤ 1, mit D = 0 Für ein völlig spärliches planares Diagramm (ein Baum) und D = 1 für eine völlig dichte (maximale) planare Graphe.[3]

Dual -Graph

Ein planares Diagramm und seine Dual

Bei einer Einbettung G Von einem (nicht unbedingt einfachen) angeschlossenen Graphen in der Ebene ohne Kantenkreuzungen konstruieren wir die Dual -Graph G* wie folgt: Wir wählen einen Scheitelpunkt in jedem Gesicht von G (einschließlich der Außenfläche) und für jede Kante e in G Wir stellen einen neuen Vorteil in vor G* Verbinden Sie die beiden Scheitelpunkte in G* entsprechend den beiden Gesichtern in G das trifft sich bei e. Darüber hinaus wird diese Kante so gezogen, dass sie kreuzt e genau einmal und das keine andere Kante von G oder G* ist überschnitten. Dann G* ist wieder die Einbettung eines (nicht unbedingt einfachen) planaren Diagramms; Es hat so viele Kanten wie Gso viele Eckpunkte als G hat Gesichter und so viele Gesichter wie G hat Eckpunkte. Der Begriff "Dual" ist durch die Tatsache gerechtfertigt G** = G; Hier ist die Gleichheit die Äquivalenz von Einbettungen auf der Kugel. Wenn G Ist das planare Diagramm, das einem konvexen Polyeder entspricht, dann G* ist das planare Graph, das dem Dual -Polyeder entspricht.

Duals sind nützlich, da viele Eigenschaften des Dual -Diagramms auf einfache Weise zu Eigenschaften des Originaldiagramms verwandt sind, sodass die Ergebnisse durch die Untersuchung ihrer Dual -Diagramme zu den Grafiken nachgewiesen werden können.

Während das für eine bestimmte Einbettung konstruierte Dual einzigartig ist (bis zu Isomorphismus), Diagramme können unterschiedliche (d. H. Nicht isomorphe) Duals aufweisen, die von verschiedenen (d. H. Non nichthomomorph) Einbettungen.

Familien von planaren Graphen

Maximale planare Graphen

Das Goldner -Harary -Graph ist maximaler Planar. Alle seine Gesichter sind von drei Kanten begrenzt.

Eine einfache Grafik heißt Maximaler Planar Wenn es planar ist, aber eine Kante (auf dem gegebenen Scheitelpunkt -Set) hinzufügen würde, würde diese Eigenschaft zerstören. Alle Gesichter (einschließlich der äußeren) werden dann von drei Kanten begrenzt, was den alternativen Begriff erklärt Ebene Triangulation. Die alternativen Namen "Triangular Graph"[4] oder "triangulierte Grafik"[5] wurden auch verwendet, sind aber mehrdeutig, wie sie sich häufiger auf die beziehen Liniendiagramm von a Komplette Graph und zum Akkorddiagramme beziehungsweise. Jedes maximale planare Diagramm ist mindestens 3 verbunden.

Wenn ein maximales planares Diagramm hat v Eckpunkte mit v > 2dann hat es genau 3v – 6 Kanten und 2v – 4 Gesichter.

Apollonische Netzwerke sind die maximalen planaren Graphen, die durch wiederholtes Teilen von dreieckigen Gesichtern in dreifach kleinere Dreiecke gebildet werden. Ähnlich sind sie der Planare 3 Bäume.

Strangulierte Grafiken sind die Grafiken, in denen jeder peripherer Zyklus ist ein Dreieck. In einem maximalen planaren Graphen (oder allgemeiner ein polyedrischer Diagramm) sind die peripheren Zyklen die Gesichter, sodass maximale planare Graphen erwürgt werden. Die strangulierten Grafiken umfassen auch die Akkorddiagrammeund sind genau die Grafiken, die nach gebildet werden können Clique-Sums (ohne Kanten zu löschen) von Komplette Diagramme und maximale planare Graphen.[6]

Außenplanargrafiken

Außenplanargrafiken sind Diagramme mit einer Einbettung in der Ebene, so dass alle Scheitelpunkte zum unbegrenzten Gesicht der Einbettung gehören. Jedes Außenplanargraf ist planar, aber das Gegenteil ist nicht wahr: K4 ist planar, aber nicht äußerlich. Ein Satz ähnlich wie Kuratowskis Staaten, dass ein endliches Diagramm nur dann äußerlich ist, wenn es keine Unterteilung von enthält K4 Oder von K2,3. Das obige ist eine direkte Folge der Tatsache, dass eine Grafik G ist äußere planar, wenn die Grafik gebildet wird G Durch Hinzufügen eines neuen Scheitelpunkts, wobei die Kanten ihn mit allen anderen Scheitelpunkten verbinden, ist ein planarer Diagramm.[7]

Eine 1-outerplanare Einbettung eines Diagramms entspricht einer Einbettung im Außenplanar. Zum k > 1 Eine planare Einbettung ist k-OUTERPLANAR Wenn das Entfernen der Scheitelpunkte auf der äußeren Gesicht zu a (k - 1)-OUTERPLANAR Einbettung. Ein Diagramm ist k-OUTERPLANAR, wenn es a hat k-OUTERPLANAR Einbettung.

Halin -Grafiken

A Halin Graph ist ein Diagramm, der aus einem ungerichteten Ebenebaum (ohne Grad zwei Knoten) gebildet wird, indem seine Blätter in einen Zyklus verbinden, in der Reihenfolge, die durch die Ebene des Baumes angegeben ist. Äquivalent ist es a Polyedrische Grafik In welchem ​​Gesicht befindet sich alle anderen. Jedes Halin -Diagramm ist Planar. Halin -Diagramme haben wie Außenplanargrafiken niedrig Baumbreite, machen viele algorithmische Probleme leichter zu lösen als in uneingeschränkten planaren Graphen.[8]

Aufwärts planare Grafiken

Ein Aufwärts -Planargrafik ist ein Regie acyclische Graphen Dies kann in der Ebene mit ihren Kanten als nicht kreuzende Kurven gezeichnet werden, die konsistent in eine nach oben ausgerichtete Richtung ausgerichtet sind. Nicht jeder von Planar gelenkte acyclische Diagramm ist nach oben planar, und das ist es NP-Complete Um zu testen, ob ein bestimmter Diagramm auf dem Planar ist.

Konvexe planare Graphen

Ein planares Diagramm soll sein konvex Wenn alle Gesichter (einschließlich des äußeren Gesichts) sind konvexe Polygone. Nicht alle planaren Diagramme haben eine konvexe Einbettung (z. B. die vollständige zweigliedern K2,4>). Eine ausreichende Bedingung, dass ein Diagramm konvex gezogen werden kann, ist, dass es a ist Unterteilung von a 3-Vertex-verbunden Planare Graph. Tutte's Frühlingstheorem Sogar erklärt, dass für einfache 3-Verfessel-verbundene Planare die Position der inneren Eckpunkte als Durchschnitt seiner Nachbarn ausgewählt werden kann.

Wortrepräsentierbare planare Graphen

Wortrepräsentierbar Planare Diagramme umfassen dreieckfreie planare Diagramme und allgemeiner 3-Farben-planarer Graphen.[9] sowie bestimmte Gesichtsunterteilungen von dreieckigen Gittergraphen,[10] und bestimmte Triangulationen von gitterüberzogenen Zylindergraphen.[11]

Theoreme

Aufzählung von planaren Graphen

Das asymptotisch für die Anzahl der (beschrifteten) planaren Graphen auf Scheitelpunkte ist , wo und .[12]

Fast alle planaren Grafiken haben eine exponentielle Anzahl von Automorphismen.[13]

Die Anzahl der unbezeichneten (nicht iisomorphen) planaren Diagramme auf Scheitelpunkte sind dazwischen und .[14]

Andere Ergebnisse

Das Vier Farbsatz gibt an, dass jede planare Diagramm 4-farbig (d. H. 4-teilig).

Fárys Satz gibt an, dass jede einfache Planargrafik eine Darstellung als planar geradlinige Grafik. EIN Universal Point Set ist eine Reihe von Punkten, so dass jede planare Grafik mit n Scheitelpunkte haben eine solche Einbettung in alle Scheitelpunkte in dem Punktsatz; Es gibt universelle Punkte der quadratischen Größe, die durch Einnahme einer rechteckigen Untergruppe der Ganzzahlgitter. Jedes einfache Außenplanar -Diagramm gibt eine Einbettung in die Ebene zu, sodass alle Scheitelpunkte auf einem festen Kreis liegen und alle Kanten gerade Liniensegmente sind, die in der Scheibe liegen und sich nicht überschneiden. n-Scheitel Regelmäßige Polygone sind universell für Außenplanare Graphen.

Scheinermans Vermutung (jetzt ein Satz) erklärt, dass jedes planare Diagramm als Kreuzungsdiagramm von Liniensegmente im Flugzeug.

Das Planar -Separator -Theorem stellt fest, dass jeder n-Vertex Planar -Diagramm kann in zwei aufgeteilt werden Subgraphen der Größe höchstens 2n/3 durch Entfernung von O (√n) Eckpunkte. Infolgedessen haben planare Graphen auch Baumbreite und Breitbreite Ö(√n).

Der planare Produktstruktur -Theorem stellt fest, dass jeder planare Diagramm ein Untergraphen des Starken ist Grafikprodukt von einer Grafik der Baumbreite höchstens 8 und einem Pfad.[15] Dieses Ergebnis wurde verwendet, um zu zeigen, dass planare Graphen begrenzt sind Warteschlangennummer, begrenzt Nicht repetitive chromatische Zahl, und Universelle Grafiken von nahezu linearer Größe. Es verfügt auch über Anwendungen zum Vertex -Ranking[16] und p-zentriertes Farben[17] von planaren Graphen.

Für zwei planare Grafiken mit v Scheitelpunkte ist möglich, rechtzeitig o zu bestimmen (v) auch wenn sie sind isomorph oder nicht (siehe auch Graph Isomorphismus Problem).[18]

Verallgemeinerungen

Ein Apex -Diagramm ist eine Grafik, die durch die Entfernung eines Scheitelpunkts planar gemacht werden kann, und a k-APEX -Diagramm ist ein Diagramm, das planar gemacht werden kann, durch die höchste Entfernung k Eckpunkte.

A 1-planarer Diagramm ist ein Diagramm, das in der Ebene mit höchstens einer einfachen Kreuzung pro Kante gezeichnet werden kann, und a k-Planar -Diagramm ist ein Diagramm, mit dem höchstens gezeichnet werden können k Einfache Kreuzungen pro Kante.

A MAP -Diagramm ist ein Diagramm, das aus einer Reihe von endlich vielen einfach vernetzten Innenausfällen in der Ebene gebildet wird, indem zwei Regionen angeschlossen werden, wenn sie mindestens einen Grenzpunkt teilen. Wenn sich höchstens drei Regionen an einem Punkt treffen, ist das Ergebnis ein planarer Diagramm, aber wenn sich vier oder mehr Regionen an einem Punkt treffen, kann das Ergebnis nicht planar sein.

A Toroidalgrafik ist eine Grafik, die ohne Kreuzungen auf der eingebettet werden kann Torus. Allgemeiner die Gattung einer Grafik ist die minimale Gattung einer zweidimensionalen Oberfläche, in die der Diagramm eingebettet sein kann; Planare Graphen haben Gattungen Zero und nicht planare Toroidgrafiken haben die Gattung 1.

Jeder Diagramm kann ohne Kreuzungen in dreidimensionalen Raum eingebettet werden. Ein dreidimensionales Analogon der planaren Graphen wird jedoch von der bereitgestellt Linklos einbettbare Diagramme, Diagramme, die in dreidimensionaler Raum eingebettet werden können, so dass keine zwei Zyklen sind topologisch verknüpft miteinander. In Analogie zu Kuratowskis und Wagners Charakterisierungen der planaren Graphen als die Grafiken, die nicht enthalten K5 oder K3,3 Als Minderjähriger können die verbindungslos eingebettbaren Diagramme als Diagramme charakterisiert werden, die keine der sieben Diagramme in der Petersen Familie. In Analogie zu den Charakterisierungen der Außenplanar- und planaren Diagramme als Diagramme mit Colin de Verdière Graph Invariante In den meisten zwei oder drei Jahren sind die linklos einbettbaren Diagramme die Grafiken, in denen Colin de Verdière in den vier Vierzügen invariante.

Siehe auch

Anmerkungen

  1. ^ Trudeau, Richard J. (1993). Einführung in die Graphentheorie (Korrigiert, vergrößerte Veröffentlichung. Ed.). New York: Dover Pub. p. 64. ISBN 978-0-486-67870-2. Abgerufen 8. August 2012. Ein planarer Diagramm hat also, wenn sie auf einer flachen Oberfläche gezeichnet werden, entweder keine Kantenkreuzungen oder kann ohne sie neu gezeichnet werden.
  2. ^ Barthelemy, M. (2017). Morphogenese von räumlichen Netzwerken. New York: Springer. p. 6.
  3. ^ Buhl, J.; Gautrais, J.; Sole, R.V.; Kuntz, P.; Valverde, S.; Deneubourg, J. L.; TherAlaz, G. (2004), "Effizienz und Robustheit in Ameisennetzwerken von Galerien", Europäisches physisches Journal B, Springer-Verlag, 42 (1): 123–129, Bibcode:2004EPJB ... 42..123B, doi:10.1140/EPJB/E2004-00364-9, S2CID 14975826.
  4. ^ Schnyder, W. (1989), "Planare Graphs und Poset -Dimension", Befehl, 5 (4): 323–343, doi:10.1007/bf00353652, HERR 1010382, S2CID 122785359.
  5. ^ Bhasker, Jayaram; Sahni, Sartaj (1988), "ein linearer Algorithmus, um einen rechteckigen Dual eines planar -triangulierten Diagramms zu finden", Algorithmus, 3 (1–4): 247–278, doi:10.1007/bf01762117, S2CID 2709057.
  6. ^ Seymour, P. D.; Weaver, R. W. (1984), "Eine Verallgemeinerung von Akkordgräben", Zeitschrift für Graphentheorie, 8 (2): 241–251, doi:10.1002/jgt.3190080206, HERR 0742878.
  7. ^ Felsner, Stefan (2004), "1,4 Oterplanar -Diagramme und konvexe geometrische Graphen", Geometrische Grafiken und Arrangements, Fortgeschrittene Vorträge in Mathematik, Friedr. Vieweg & Sohn, Wiesbaden, S. 6–7, doi:10.1007/978-3-322-80303-0_1, ISBN 3-528-06972-4, HERR 2061507
  8. ^ Sysło, Maciej M.; Prokurowski, Andrzej (1983), "On Halin Graphs", Graphentheorie: Verfahren einer Konferenz in Lagów, Polen, 10. bis 13. Februar 1981, Vorlesungen in Mathematics, Vol. 1018, Springer-Verlag, S. 248–256, doi:10.1007/bfb0071635.
  9. ^ "M. Halldórsson, S. Kitaev und A. Pyatkin. Semi-transitive Orientierungen und Wortrepräsentierbare Diagramme, Discr. Appl. Math. 201 (2016), 164-171".
  10. ^ T. Z. Q. Chen, S. Kitaev und B. Y. Sun. Wortrepräsentierbarkeit von Gesichtsunterteilungen von dreieckigen Gittergrafiken, Graphen und Kombination. 32 (5) (2016), 1749-1761.
  11. ^ T. Z. Q. Chen, S. Kitaev und B. Y. Sun. Wortrepräsentierbarkeit von Triangulationen von gitterbedeckten Zylindergraphen, Diskretion. Appl. Mathematik. 213 (2016), 60-70.
  12. ^ Giménez, Omer; Noy, Marc (2009). "Asymptotische Aufzählung und Begrenzung der Gesetze planarer Graphen". Zeitschrift der American Mathematical Society. 22 (2): 309–329. Arxiv:Math/0501269. Bibcode:2009jams ... 22..309g. doi:10.1090/s0894-0347-08-00624-3. S2CID 3353537.
  13. ^ McDiarmid, Colin; Steger, Angelika; Welsh, Dominic J.A. (2005). "Zufällige planare Graphen". Journal of Combinatorial Theory, Serie B. 93 (2): 187–205. Citeseerx 10.1.1.572.857. doi:10.1016/j.jctb.2004.09.007.
  14. ^ Bonichon, N.; Gavoille, C.; Hanusse, N.; Poulalhon, D.; Schaeffer, G. (2006). "Planare Diagramme, über ordnungsgemäße Karten und Bäume". Grafiken und Kombinatorik. 22 (2): 185–202. Citeseerx 10.1.1.106.7456. doi:10.1007/s00373-006-0647-2. S2CID 22639942.
  15. ^ Dujmović, Vida; Joret, Gwenäel; Micek, Piotr; Morin, Pat; Ueckerdt, Torsten; Wood, David R. (2020), "planare Graphen haben die Warteschlangennummer begrenzt", Journal of the ACM, 67 (4): 22: 1–22: 38, Arxiv:1904.04791, doi:10.1145/3385731
  16. ^ Bose, Prosenjit; Dujmović, Vida; Javarsineh, Mehrnoosh; Morin, Pat (2020), Asymptotisch optimaler Scheitelpunktranking planarer Graphen, Arxiv:2007.06455
  17. ^ Dębski, Michał; Felsner, Stefan; Micek, Piotr; Schröder, Felix (2019), Verbesserte Grenzen für zentrierte Farben, Arxiv:1907.04586
  18. ^ I. S. Filotti, Jack N. Mayer. Ein Polynom-Zeit-Algorithmus zur Bestimmung des Isomorphismus von Graphen der festen Gattung. Verfahren des 12. jährlichen ACM -Symposiums über die Theorie des Computing, S. 236–243. 1980.

Verweise

Externe Links