In der Graph-Theorie ist ein planarer Graph ein Graph, der im Flugzeug eingebettet werden kann, d. h. es kann das Flugzeug auf solche Art und Weise angezogen werden, das seine Ränder nur an ihren Endpunkten durchschneiden. Mit anderen Worten kann es auf solche Art und Weise gezogen werden, dass keine Ränder einander durchqueren.

Ein planarer Graph, der bereits im Flugzeug ohne Rand-Kreuzungen gezogen ist, wird einen Flugzeug-Graphen oder das planare Einbetten des Graphen genannt. Ein Flugzeug-Graph kann als ein planarer Graph damit definiert, von jedem Knoten bis einen Punkt im 2. Raum, und von jedem Rand bis eine Flugzeug-Kurve kartografisch darzustellen, solch werden, dass die äußersten Punkte jeder Kurve die Punkte sind, die von seinen Endknoten kartografisch dargestellt sind, und alle Kurven außer auf ihren äußersten Punkten zusammenhanglos sind. Flugzeug-Graphen können durch kombinatorische Karten verschlüsselt werden.

Es wird leicht gesehen, dass ein Graph, der das Flugzeug angezogen werden kann, der Bereich ebenso, und umgekehrt angezogen werden kann.

Die Gleichwertigkeitsklasse topologisch gleichwertiger Zeichnungen auf dem Bereich wird eine planare Karte genannt. Obwohl ein Flugzeug-Graph ein äußerliches oder unbegrenztes Gesicht hat, hat keines der Gesichter einer planaren Karte einen besonderen Status.

Eine Generalisation von planaren Graphen ist Graphen, die eine Oberfläche einer gegebenen Klasse angezogen werden können. In dieser Fachsprache haben planare Graphen Graph-Klasse 0, da das Flugzeug (und der Bereich) Oberflächen der Klasse 0 ist. Sieh "Graphen" für andere zusammenhängende Themen einbetten.

Die Lehrsätze von Kuratowski und Wagners

Der polnische Mathematiker Kazimierz Kuratowski hat eine Charakterisierung von planaren Graphen in Bezug auf verbotene Graphen zur Verfügung gestellt, die jetzt als der Lehrsatz von Kuratowski bekannt sind:

Begrenzter Graph von:A ist planar, wenn, und nur wenn er keinen Subgraphen enthält, der eine Unterteilung von K (der ganze Graph auf fünf Scheitelpunkten) oder K ist (vollenden zweiteiligen Graphen auf sechs Scheitelpunkten, von denen drei zu jedem der anderen drei in Verbindung stehen).

Eine Unterteilung eines Graphen ergibt sich aus dem Einfügen von Scheitelpunkten in Ränder (zum Beispiel, einen Rand ändernd · - · dazu · - · - ·) Null oder mehr Male. Gleichwertige Formulierungen dieses Lehrsatzes, auch bekannt als "Lehrsatzes P" schließen ein

Begrenzter Graph von:A ist planar, wenn, und nur wenn er keinen Subgraphen enthält, der homeomorphic zu K oder K ist.

In der Sowjetunion war der Lehrsatz von Kuratowski als der Lehrsatz von Pontryagin-Kuratowski bekannt, weil sein Beweis angeblich zuerst in den unveröffentlichten Zeichen von Pontryagin gegeben wurde. Durch eine langjährige akademische Tradition werden solche Verweisungen in der Bestimmung des Vorrangs nicht in Betracht gezogen, so wird der russische Name des Lehrsatzes international nicht anerkannt.

Anstatt Unterteilungen zu denken, befasst sich der Lehrsatz von Wagner mit Minderjährigen:

Begrenzter Graph von:A ist planar, wenn, und nur wenn er K oder K als ein Minderjähriger nicht hat.

Klaus Wagner hat mehr allgemein gefragt, ob eine gering geschlossene Klasse von Graphen durch einen begrenzten Satz von "verbotenen Minderjährigen" bestimmt wird. Das ist jetzt der Lehrsatz von Robertson-Seymour, der in einer langen Reihe von Papieren bewiesen ist. Auf der Sprache dieses Lehrsatzes sind K und K die verbotenen Minderjährigen für die Klasse von begrenzten planaren Graphen.

Andere planarity Kriterien

In der Praxis ist es schwierig, das Kriterium von Kuratowski zu verwenden, um schnell zu entscheiden, ob ein gegebener Graph planar ist. Jedoch dort bestehen Sie schnelle Algorithmen für dieses Problem: Für einen Graphen mit n Scheitelpunkten ist es möglich, rechtzeitig O (n) zu bestimmen (geradlinige Zeit), ob der Graph planar sein kann oder nicht (sieh planarity prüfen).

Für einen einfachen, verbundenen, planaren Graphen mit v Scheitelpunkten und e Rändern halten die folgenden einfachen planarity Kriterien:

: Lehrsatz 1. Wenn v ≥ 3 dann e ≤ 3v − 6;

: Lehrsatz 2. Wenn v ≥ 3 und gibt es keine Zyklen der Länge 3, dann e ≤ 2v − 4.

In diesem Sinn sind planare Graphen spärliche Graphen, darin haben sie nur O (v) Ränder, die asymptotisch kleiner sind als das Maximum O (v). Der Graph K hat zum Beispiel 6 Scheitelpunkte, 9 Ränder und keine Zyklen der Länge 3. Deshalb, durch den Lehrsatz 2, kann es nicht planar sein. Bemerken Sie, dass diese Lehrsätze notwendige Bedingungen für planarity zur Verfügung stellen, die nicht genügend Bedingungen sind, und nur deshalb verwendet werden können, um zu beweisen, dass ein Graph, nicht nicht planar ist, dass es planar ist. Wenn sowohl Lehrsatz 1 als auch 2 scheitert, können andere Methoden verwendet werden.

• Das planarity Kriterium von Whitney gibt eine auf der Existenz eines algebraischen Doppel-gestützte Charakterisierung;
• Das planarity Kriterium von MacLane gibt eine algebraische Charakterisierung von begrenzten planaren Graphen über ihre Zyklus-Räume;
• Das planarity Kriterium von Fraysseix-Rosenstiehl gibt eine Charakterisierung, die auf der Existenz eines bipartition der cotree Ränder eines Tiefensuche-Baums gestützt ist. Es ist zentraler nach links richtiger planarity Prüfung des Algorithmus;
• Der Lehrsatz von Schnyder gibt eine Charakterisierung von planarity in Bezug auf die teilweise Ordnungsdimension;
• Das planarity Kriterium von Colin de Verdière gibt eine Charakterisierung, die auf der maximalen Vielfältigkeit des zweiten eigenvalue von bestimmten durch den Graphen definierten Maschinenbedienern von Schrödinger gestützt ist.

Die Formel von Euler

Die Formel von Euler stellt fest, dass, wenn ein begrenzter, verbundener, planarer Graph im Flugzeug ohne irgendwelche Rand-Kreuzungen gezogen wird, und v die Zahl von Scheitelpunkten ist, ist e die Zahl von Rändern, und f ist die Zahl von Gesichtern (Gebiete, die durch Ränder einschließlich des ungeheuer großen Außengebiets begrenzt sind), dann

:.

Als eine Illustration, im Schmetterling-Graphen, der oben, v = 5, e = 6 und f = 3 gegeben ist. Wenn der zweite Graph ohne Rand-Kreuzungen neu entworfen wird, hat er v = 4, e = 6 und f = 4.

Im Allgemeinen, wenn das Eigentum für alle planaren Graphen von F-Gesichtern hält, würde jede Änderung zum Graphen, der ein zusätzliches Gesicht schafft, während er den Graphen planar hält, v &minus behalten; e + f ein invariant. Da das Eigentum für alle Graphen mit f = 2, durch die mathematische Induktion hält, die es für alle Fälle hält. Die Formel von Euler kann auch wie folgt bewiesen werden: Wenn der Graph nicht ein Baum ist, dann entfernen Sie einen Rand, der einen Zyklus vollendet. Das senkt sowohl e als auch f durch einen, v &minus abreisend; e + f unveränderlich. Wiederholen Sie sich, bis der restliche Graph ein Baum ist; Bäume haben v = e + 1 und f = 1, v &minus tragend; e + f = 2. d. h. die Eigenschaft von Euler ist 2.

In einem begrenzten, verbundenen, einfachen, planaren Graphen wird jedes Gesicht (außer vielleicht dem Außen-) durch mindestens drei Ränder begrenzt, und jeder Rand berührt höchstens zwei Gesichter; mit der Formel von Euler kann man dann zeigen, dass diese Graphen im Sinn dass e  3v &minus spärlich sind; 6 wenn v  3.

Die Formel von Euler ist auch für konvexe Polyeder gültig. Das ist kein Zufall: Jedes konvexe Polyeder kann in einen verbundenen, einfachen, planaren Graphen durch das Verwenden des Diagramms von Schlegel des Polyeders, eines Perspektivevorsprungs des Polyeders auf ein Flugzeug mit dem Zentrum der Perspektive verwandelt werden, die in der Nähe vom Zentrum von einem der Gesichter des Polyeders gewählt ist. Nicht jeder planare Graph entspricht einem konvexen Polyeder auf diese Weise: Die Bäume tun nicht zum Beispiel. Der Lehrsatz von Steinitz sagt, dass die polyedrischen von konvexen Polyedern gebildeten Graphen genau die begrenzten 3-verbundenen einfachen planaren Graphen sind. Mehr allgemein gilt die Formel von Euler für jedes Polyeder, dessen Gesichter einfache Vielecke sind, die eine Oberfläche bilden, die topologisch zu einem Bereich unabhängig von seiner Konvexität gleichwertig ist.

Durchschnittlicher Grad

Von und 3f, der ganze Graph auf fünf Scheitelpunkten, minus ein Rand.]]

Wir sagen, dass sich zwei in einem Flugzeug gezogene Kreise küssen, wann auch immer sie sich in genau einem Punkt schneiden. Ein "Münzgraph" ist ein Graph, der durch eine Reihe von Kreisen gebildet ist, von denen keine zwei überlappendes Innere, durch das Bilden eines Scheitelpunkts für jeden Kreis und eines Randes für jedes Paar von Kreisen diesen Kuss haben. Der Kreisverpackungslehrsatz, der zuerst von Paul Koebe 1936 bewiesen ist, stellt fest, dass ein Graph planar ist, wenn, und nur wenn es ein Münzgraph ist.

Dieses Ergebnis stellt einen leichten Beweis des Lehrsatzes von Fáry zur Verfügung, dass jeder planare Graph im Flugzeug auf solche Art und Weise eingebettet werden kann, dass seine Ränder Segmente der Gerade sind, die einander nicht durchqueren. Wenn man jeden Scheitelpunkt des Graphen am Zentrum des entsprechenden Kreises in einer Münzgraph-Darstellung legt, dann durchqueren die Liniensegmente zwischen Zentren des Küssens von Kreisen keinen der anderen Ränder.

Verwandte Familien von Graphen

Maximale planare Graphen

Ein einfacher Graph wird maximal planar genannt, wenn es planar, aber beitragend ist, dass jeder Rand (auf dem gegebenen Scheitelpunkt-Satz) dieses Eigentum zerstören würde. Alle Gesichter (sogar das Außen-) werden dann durch drei Ränder begrenzt, erklärend, dass die Alternative dreieckig und trianguliert für diese Graphen nennt. Wenn ein Dreiecksgraph v Scheitelpunkte mit v> 2 hat, dann hat es genau 3v − 6 Ränder und 2v − 4 Gesichter.

Die Apollonian Netze sind die maximalen planaren gebildeten Graphen durch das wiederholte Aufspalten von Dreiecksgesichtern darin verdreifacht sich von kleineren Dreiecken. Gleichwertig sind sie die planaren 3 Bäume.

Graphen von Outerplanar

Graphen von Outerplanar sind Graphen mit einem Einbetten im solchem Flugzeug, dass alle Scheitelpunkte dem unbegrenzten Gesicht des Einbettens gehören. Jeder outerplanar Graph ist planar, aber das gegenteilige ist nicht wahr: K ist planar, aber nicht outerplanar. Ein den Staaten von Kuratowski ähnlicher Lehrsatz, dass ein begrenzter Graph outerplanar ist, wenn, und nur wenn es keine Unterteilung von K oder K enthält.

Ein 1-outerplanar Einbetten eines Graphen ist dasselbe als ein Outerplanar-Einbetten. Für k> 1 ist ein planares Einbetten k-outerplanar, wenn das Entfernen der Scheitelpunkte auf dem Außengesicht hinausläuft (k − 1) das-Outerplanar-Einbetten. Ein Graph ist k-outerplanar, wenn es einen k-outerplanar hat, der einbettet

Andere verwandte Familien

Ein Spitze-Graph ist ein Graph, der planar durch die Eliminierung eines Scheitelpunkts gemacht werden kann, und ein K-Spitze-Graph ein Graph ist, der planar durch die Eliminierung an den meisten k Scheitelpunkten gemacht werden kann.

Ein toroidal Graph ist ein Graph, der ohne Überfahrten auf dem Ring eingebettet werden kann. Mehr allgemein ist die Klasse eines Graphen die minimale Klasse eines zweidimensionalen Graphen, auf den der Graph eingebettet werden kann; planare Graphen haben Klasse-Null, und nichtplanare toroidal Graphen haben Klasse ein.

Jeder Graph kann in den dreidimensionalen Raum ohne Überfahrten eingebettet werden. Jedoch wird eine dreidimensionale Entsprechung der planaren Graphen durch den linklessly embeddable Graphen, Graphen zur Verfügung gestellt, die in den dreidimensionalen Raum auf solche Art und Weise eingebettet werden können, dass keine zwei Zyklen mit einander topologisch verbunden werden. In der Analogie zu den Charakterisierungen von Kuratowski und Wagners der planaren Graphen als seiend die Graphen, die K oder K als ein Minderjähriger nicht enthalten, kann der linklessly embeddable Graphen als die Graphen charakterisiert werden, die als ein Minderjähriger keiner der sieben Graphen in der Familie von Petersen enthalten. In der Analogie zu den Charakterisierungen des outerplanar und der planaren Graphen als seiend die Graphen mit dem Graphen von Colin de Verdière invariant höchstens zwei oder drei sind die linklessly embeddable Graphen die Graphen, die Colin de Verdière invariant höchstens vier haben.

Andere Tatsachen und Definitionen

Jeder planare Graph ohne Schleifen ist 4-partite, oder 4-angeblich; das ist die mit dem Graphen theoretische Formulierung des vier Farbenlehrsatzes.

Der Lehrsatz von Fáry stellt fest, dass jeder einfache planare Graph ein Einbetten im solchem Flugzeug zulässt, dass alle Ränder Segmente der Gerade sind, die sich nicht schneiden. Ähnlich lässt jeder einfache outerplanar Graph ein Einbetten im solchem Flugzeug zu, dass alle Scheitelpunkte auf einem festen Kreis liegen und alle Ränder Segmente der Gerade sind, die innerhalb der Platte liegen und sich nicht schneiden.

In Anbetracht eines Einbettens G (nicht notwendigerweise einfach) hat Graphen im Flugzeug ohne Rand-Kreuzungen verbunden, wir bauen den Doppelgraphen G* wie folgt: Wir wählen einen Scheitelpunkt in jedem Gesicht von G (einschließlich des Außengesichtes) und für jeden Rand e in G wir führen einen neuen Rand in G* ein, der die zwei Scheitelpunkte in G* entsprechend den zwei Gesichtern in G verbindet, die sich an e treffen. Außerdem wird dieser Rand gezogen, so dass er e genau einmal durchquert, und dass kein anderer Rand von G oder G* durchgeschnitten wird. Then G* ist wieder das Einbetten (nicht notwendigerweise einfach) planarer Graph; es hat so viele Ränder wie G, so viele Scheitelpunkte wie G haben Gesichter, und so viele Gesichter wie G haben Scheitelpunkte. Der Begriff "Doppel-" wird durch die Tatsache dass G ** = G gerechtfertigt; hier ist die Gleichheit die Gleichwertigkeit von embeddings auf dem Bereich. Wenn G der planare Graph entsprechend einem konvexen Polyeder ist, dann ist G* der planare Graph entsprechend dem Doppelpolyeder.

Duals sind nützlich, weil viele Eigenschaften des Doppelgraphen auf einfache Weisen zu Eigenschaften des ursprünglichen Graphen verbunden sind, Ergebnissen ermöglichend, über Graphen durch das Überprüfen ihrer Doppelgraphen bewiesen zu werden.

Während der für ein besonderes Einbetten gebaute Doppel-einzigartig ist (bis zum Isomorphismus), können Graphen verschieden (d. h. nichtisomorph) duals, erhalten beim verschiedenen (d. h. non-homeomorphic) embeddings haben.

Ein Euklidischer Graph ist ein Graph, in dem die Scheitelpunkte Punkte im Flugzeug vertreten, und die Ränder zugeteilte Längen sind, die der Euklidischen Entfernung zwischen jenen Punkten gleich sind; sieh Geometrische Graph-Theorie.

Wie man

sagt, ist ein Flugzeug-Graph konvex, wenn alle seine Gesichter (einschließlich des Außengesichtes) konvexe Vielecke sind. Ein planarer Graph kann konvex gezogen werden, wenn, und nur wenn es eine Unterteilung eines 3 Scheitelpunkts ist, planaren Graphen verbunden hat.

Die Vermutung von Scheinerman (jetzt ein Lehrsatz) stellt fest, dass jeder planare Graph als ein Kreuzungsgraph von Liniensegmenten im Flugzeug vertreten werden kann.

Der planare Separator-Lehrsatz stellt fest, dass jeder N-Scheitelpunkt planarer Graph in zwei Subgraphen der Größe am grössten Teil von 2n/3 durch die Eliminierung von O (n) Scheitelpunkte verteilt werden kann. Demzufolge haben planare Graphen auch treewidth und Zweigbreite O (n).

Für zwei planare Graphen mit v Scheitelpunkten ist es möglich, rechtzeitig O (v) zu bestimmen, ob sie isomorph sind oder nicht (sieh auch Graph-Isomorphismus-Problem).

Referenzen

....

• . Sonderausgabe auf der Graph-Zeichnung. Doi:10.1142/S0129054106004248
• D.A. Bader und S. Sreshta, Ein Neuer Paralleler Algorithmus für die Planarity-Prüfung, UNM-ECE Technischer Bericht 03-002, am 1. Oktober 2003.

.

Links

• Planarity Rand-Hinzufügungsalgorithmus-Quellcode, Version 1.0 - Freier C Quellcode für die Bezugsdurchführung des Algorithmus von Boyer-Myrvold planarity, der sowohl einen kombinatorischen planaren embedder als auch Subgraphen von Kuratowski isolator zur Verfügung stellt. Ein offenes Quellprojekt mit dem freien Genehmigen stellt der Rand-Hinzufügung Planarity Algorithmen, jetzige Version zur Verfügung.
• Öffentliche Durchführung einer Graph-Algorithmus-Bibliothek und Redakteurs - GPL Graph-Algorithmus-Bibliothek einschließlich der Planarity-Prüfung, planarity embedder und Subgraph-Ausstellung von Kuratowski in der geradlinigen Zeit.
• Zunahme-Graph-Bibliothekswerkzeuge für planare Graphen, einschließlich der geradlinigen Zeit planarity Prüfung, das Einbetten, die Subgraph-Isolierung von Kuratowski und die lineare Zeichnung.
• 3 Dienstprogramm-Rätsel und Planare Graphen
• Planarity - Ein Rätsel-Spiel von John Tantalo geschaffen.
• NetLogo Planarity Modell - Version von NetLogo des Spiels von John Tantalo