Dreiecksgraph

Ein Dreiecksgraph ist in der Graphentheorie ein planarer Graph, bei dem jedes seiner Gebiete durch einen Kreis der Länge ${\displaystyle 3}$ umrandet ist. Ein Dreiecksgraph hat daher mindestens drei Knoten.

Ein maximal planarer Graph (oder maximal ebener Graph) ist ein planarer Graph, dem keine 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 ${\displaystyle n}$ Knoten hat genau ${\displaystyle 3n-6}$ Kanten und ${\displaystyle 2n-4}$ Gebiete. Der kleinste Dreiecksgraph ist der Kreisgraph ${\displaystyle C_{3}}$ bestehend aus genau drei Knoten.

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

• Reinhard Diestel: Graphentheorie. Springer, 2006, ISBN 3-540-21391-0 (eingeschränkte Vorschau in der Google-Buchsuche).