Ebener Graph

Ebener Graph
Planare Zeichnung des K4

Ein planarer Graph (auch plättbarer Graph) ist in der Graphentheorie ein Graph, der auf einer Ebene mit Punkten für die Knoten und Linien für die Kanten dargestellt werden kann, so dass sich die Kanten nicht schneiden.

Der Satz von Kuratowski gibt eine weitere Charakterisierung von planaren Graphen und erlaubt die Beantwortung der Frage nach der Plättbarkeit von Graphen.

Eine konkrete Darstellung eines Graphen in der Ebene wird auch Einbettung genannt. Ein ebener Graph ist ein in die Ebene eingebetteter Graph. Durch die Einbettung wird die Ebene in zusammenhängende Gebiete geteilt, die von den Kanten des Graphen begrenzt werden. Die begrenzenden Kanten eines Gebietes bilden seinen Rand. Das Gebiet um den Graphen herum wird auch äußeres Gebiet genannt. Die Einbettung kann auch auf einer Kugeloberfläche stattfinden. Umgekehrt ist auch jeder auf einer Kugel kreuzungsfrei darstellbare Graph planar.

Zwei Einbettungen sind äquivalent, wenn es eine isomorphe Abbildung zwischen den Rändern ihrer Gebiete gibt. Es lässt sich zeigen, dass für jeden planaren Graphen auch eine Einbettung existiert, bei der die Kanten geradlinig sind.

Ein Graph heißt maximal planar oder Dreiecksgraph, wenn er planar ist und ihm keine Kante hinzugefügt werden kann, ohne dass dadurch seine Planarität verloren geht.

Ein Graph heißt fast planar oder kritisch planar, wenn der Graph durch Entfernen eines beliebigen Knotens planar wird. Bsp.: K5 ist fast planar.

Beispiel eines kreisartig plättbaren Graphen, rechts ein ebener Graph

Ein Graph heißt kreisartig planar (oft auch außenplanar oder außerplanar), wenn er sich so in die Ebene einbetten lässt, dass alle seine Ecken auf dem Rand ein und desselben Gebiets liegen.

Die Planarität eines Graphen lässt sich mit verschiedenen Algorithmen in linearer Zeit testen. Allerdings sind diese Algorithmen nicht einfach zu implementieren.

Verbindung zu anderen Graph-Eigenschaften

In einem zusammenhängenden planaren Graphen gilt nach dem eulerschen Polyedersatz stets:

Knotenzahl + Gebietszahl - Kantenzahl = 2.

Aus dieser Eigenschaft folgt, dass planare Graphen in Bezug auf die Knotenanzahl nur linear viele Kanten haben können.

Ist ein planarer Graph 3-fach zusammenhängend, so sind alle seine Einbettungen äquivalent.

Der Vier-Farben-Satz besagt, dass sich planare Graphen mit 4 Farben färben lassen. Dreiecksfreie planare Graphen sind 3-färbbar.

Ein planarer Graph kann höchstens 5-fach zusammenhängend sein und es gibt immer einen Knoten mit Knotengrad höchstens 5

Weblinks

  • Planarity - Ein Spiel, das auf planaren Graphen basiert.

Wikimedia Foundation.

Игры ⚽ Поможем решить контрольную работу

Schlagen Sie auch in anderen Wörterbüchern nach:

  • Plättbarer Graph — Planare Zeichnung des K4 Ein planarer Graph (auch plättbarer Graph) ist in der Graphentheorie ein Graph, der auf einer Ebene mit Punkten für die Knoten und Linien für die Kanten dargestellt werden kann, so dass sich die Kanten nicht schneiden.… …   Deutsch Wikipedia

  • Einheitsdistanz-Graph — Der Petersen Graph ist ein Einheitsdistanz Graph: er kann so gezeichnet werden, dass jede Kante gleich lang ist. Ein Einheitsdistanz Graph ist ein geometrischer Graph, bei dem jede Kante gleich lang ist. Kanten eines Einheitsdistanz Graphen… …   Deutsch Wikipedia

  • Planarer Graph — Planare Zeichnung des K4 Ein planarer oder plättbarer Graph ist in der Graphentheorie ein Graph, der auf einer Ebene mit Punkten für die Knoten und Linien für die Kanten dargestellt werden kann, sodass sich keine Kanten schneiden. Der Satz von… …   Deutsch Wikipedia

  • Plättbar — Planare Zeichnung des K4 Ein planarer Graph (auch plättbarer Graph) ist in der Graphentheorie ein Graph, der auf einer Ebene mit Punkten für die Knoten und Linien für die Kanten dargestellt werden kann, so dass sich die Kanten nicht schneiden.… …   Deutsch Wikipedia

  • Dreiecksgraph — Der Goldner–Harary Graph ist maximal planar. Jedes Gebiet wird von drei Kanten umrandet. Ein Dreiecksgraph ist in der Graphentheorie ein planarer Graph, bei dem jedes seiner Gebiete durch einen Kreis der Länge 3 umrandet ist. Ein Dreiecksgraph… …   Deutsch Wikipedia

  • Kreiskritische Knotenmenge — Der Begriff Feedback Vertex Set bzw. kreiskritische Knotenmenge bezeichnet in der Komplexitätstheorie ein graphentheoretisches Entscheidungsproblem, das NP vollständig ist. Definition Es fragt, ob es zu einem ungerichteten Multigraphen G = (V,E) …   Deutsch Wikipedia

  • Geometrische Graphentheorie — Die geometrische Graphentheorie ist ein spezieller Zweig der Graphentheorie, der sich mit der Untersuchung geometrischer Graphen beschäftigt. Ein geometrischer Graph ist ein Graph, bei dem Knoten oder Kanten mit geometrischen Objekten oder… …   Deutsch Wikipedia

  • Dreiecksnetz — Ein Dreiecksnetz ist ein ebener oder räumlicher Graph, der nur aus Dreiecken besteht. Das Dreieck wie auch dessen Ermittlung werden Triangulierung genannt. Dreiecksnetze werden in der Technik zur Vermessung und zur Modellierung verwendet.… …   Deutsch Wikipedia

  • Auflagendruck — Unter dem Begriff Druck werden alle Reproduktionsverfahren zur Vervielfältigung von Druckvorlagen zusammengefasst. Inhaltsverzeichnis 1 Grundlagen 2 Druckprinzipien 2.1 Fläche gegen Fläche 2.2 Zylinder gegen Fläche …   Deutsch Wikipedia

  • Druck (Reproduktionstechnik) — Unter dem Begriff Druck werden alle Reproduktionsverfahren zur Vervielfältigung von Druckvorlagen zusammengefasst. Inhaltsverzeichnis 1 Grundlagen 2 Druckprinzipien 2.1 Fläche gegen Fläche 2.2 Zylinder gegen Fläche …   Deutsch Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”