imported>Dexxor: https://www.or.uni-bonn.de/~hougardy/paper/ga.pdf Seite 227

2025-09-14T16:26:48Z

https://www.or.uni-bonn.de/~hougardy/paper/ga.pdf Seite 227

Neue Seite

[[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]]

Dreiecksgraph - Versionsgeschichte

imported>Dexxor: https://www.or.uni-bonn.de/~hougardy/paper/ga.pdf Seite 227