Kreisbogengraph
-
Links ein Kreisbogengraph und rechts ein Modell dafür -
Die dargestellte Biklaue ist ein Beispiel für einen einfachen Graphen, der kein Kreisbogenmodell besitzt.
Ein Kreisbogengraph ist in der Diskreten Mathematik eine Struktur der Graphentheorie.
Sei ein Graph. Ist eine Familie von Kreisbögen zu einem festen Radius dergestalt, dass gilt
so heißt Kreisbogenmodell für . Ein Graph ist genau dann ein Kreisbogengraph, wenn er ein Kreisbogenmodell besitzt. Kreisbogengraphen wurden ab den 1970er Jahren zuerst von Alan Tucker und dann bald von vielen Weiteren untersucht.
Einige Teilklassen
Gibt es ein Modell mit der Eigenschaft, dass alle Kreisbögen Einheitslänge haben, spricht man von einem Unit-Kreisbogengraph. Lässt sich eine Familie angeben, in der alle Inklusionen von Kreisbögen echte Inklusionen sind, spricht man von Proper-Kreisbogengraphen. Existiert ein Modell so, dass die Kreisbögen als Mengen die Helly-Eigenschaft besitzen, heißt der Graph auch Helly-Kreisbogengraph.
Die Intervallgraphen sind ein wichtiger Spezialfall. Im Gegensatz zu diesen sind Kreisbogengraphen im Allgemeinen jedoch nicht mehr perfekt oder chordal, denn für ungerade Kreisgraphen existiert stets ein Kreisbogenmodell. Auch die lineare Beschränkung an die Anzahl maximaler Cliquen, die man bei Intervallgraphen hat, geht in eine exponentielle Schranke über.
Algorithmische Komplexität klassischer Probleme
| Kreisbogengraph | |
|---|---|
| Erkennung | Linear (McConnel 2003) |
| 3-Färbung | Polynomiell (Garey et al. 1980) |
| Cliquenüberdeckung | Linear (Hsu und Tsai 1991) |
| Unabhängige Menge | Linear (Hsu und Tsai 1991) |
| Dominierende Menge | Linear (Hsu und Tsai 1991) |
| Hamiltonpfad | Polynomiell (Mertizios und Bezák 2014) |
| Hamiltonkreis | Polynomiell (Shih et al. 1992) |
| Färbungszahl | NP-vollständig (Garey et al. 1980) |