Unit Disk Visibility Graphs

Das Kapitel führt Einheitendiagramme für die Sichtbarkeit von Festplatten ein, bei denen es sich um Diagrammdarstellungen geometrischer Einheiten mit Sichtbeschränkungen und einem maximalen Abstand von einer Einheit zwischen den Eckpunkten handelt. Es vertieft sich in die Rechenkomplexität des 3-Färbungsproblems auf diesen Diagrammen und beweist, dass es NP-vollständig für Einheitsdiagramme für die Sichtbarkeit von Plattensegmenten und Einheitsdiagramme für die Sichtbarkeit von Polygonen mit Löchern ist. Das Kapitel untersucht auch die Beziehung zwischen Einheits-Sichtbarkeitsgraphen und anderen Graphenklassen und zeigt, dass Einheits-Sichtbarkeitsgraphen eine ordnungsgemäße Unterklasse von Einheits-Sichtbarkeitsgraphen sind und dass Einheits-Sichtbarkeitsgraphen eine ordnungsgemäße Unterklasse von Einheits-Sichtbarkeitsgraphen sind. Darüber hinaus wirft das Kapitel zwei offene Probleme hinsichtlich der 3-Färbbarkeit der Sichtbarkeitsdiagramme von Liniensegmenten auf und unterstreicht die Notwendigkeit weiterer Forschung zum Problem der chromatischen Zahl auf Sichtbarkeitsdiagrammen einfacher Polygone.