Quelltext der Seite Dreiecksgraph

[[Datei:Goldner-Harary graph.svg|mini|240px|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 (Graphentheorie)|Kreis]] der Länge <math>3</math> umrandet ist. Ein Dreiecksgraph hat daher mindestens drei [[Knoten (Graphentheorie)|Knoten]].

Ein '''maximal planarer Graph''' (oder ''maximal ebener Graph'') ist ein planarer Graph, dem keine [[Kante (Graphentheorie)|Kante]] hinzugefügt werden kann, ohne dass dadurch seine Planarität verloren geht. Jeder Graph mit mindestens drei Knoten ist genau dann maximal planar, wenn er ein Dreiecksgraph ist.

Ein Dreiecksgraph mit <math>n</math> [[Knoten (Graphentheorie)|Knoten]] hat genau <math>3n-6</math> Kanten und <math>2n-4</math> Gebiete. Der kleinste Dreiecksgraph ist der [[Kreisgraph]] <math>C_3</math> bestehend aus genau drei Knoten.

Die [[chordaler Graph|chordalen Graphen]] werden gelegentlich auch als Dreiecksgraphen bezeichnet; sie bilden aber weder eine Obermenge noch eine Teilmenge der maximal planaren Graphen.

== Literatur ==
* {{Literatur
   |Autor=Reinhard Diestel
   |Titel=Graphentheorie
   |Verlag=Springer
   |Datum=2006
   |ISBN=3-540-21391-0
   |Online={{Google Buch |BuchID=imMyNFYQussC}}}}

[[Kategorie:Planarer Graph]]