Sichtbarkeitsdarstellungen von Graphen mit Kreuzungen

• Antragsteller: Professor Dr. Franz Josef Brandenburg
• Fachliche Zuordnung: Theoretische Informatik ; Afrika-, Amerika- und Ozeanienbezogene Wissenschaften
• Förderung: Förderung von 2013 bis 2016
• Projektkennung: Deutsche Forschungsgemeinschaft (DFG) - Projektnummer 239775286

Graphen sind ein wichtiges Werkzeug zur Modellierung diskreter Strukturen. In Anwendungen werden sie auch als Netzwerke, Pläne, Diagramme oder Schemata bezeichnet. Die weite Verbreitung von Graphen ist auch durch die in natürlicher Weise gegebene Visualisierung begründet. Die planaren Graphen sind die bekannteste und am meisten untersuchte Graphklasse. Die aus Anwendungen stammenden Graphen sind jedoch meist nicht planar. Es kommt zu Kreuzungen in einem überschaubaren Umfang. In jüngster Zeit sind daher Konzepte für beyond-planar Graphen vorgeschlagen worden. Derartige Graphen erlauben Kreuzungen in einer kontrollierten Weise, so dass wichtige Merkmale planarer Graphen, wie eine lineare Anzahl an Kanten oder Zeichenverfahren erhalten bleiben. Die planaren Graphen werden konventionell geradlinig oder orthogonal gezeichnet. Daneben gibt es Sichtbarkeitsdarstellungen, bei denen die Knoten als horizontale Linien dargestellt werden und die Kanten durch eine vertikale Sichtbarkeit zwischen den Knoten. Diese Art der Darstellung ist weniger populär, aber sie ist algorithmisch einfacher und konzeptionell flexibler. Sichtbarkeitsdarstellungen haben ein bislang nicht erforschtes Potential, wenn man in kontrollierter Weise Kreuzungen zulässt. Dann dominieren sie den geradlinigen Zeichenstil. Sie bieten viele Möglichkeiten, beyond-planar Graphen zu definieren. Dieses Potential wollen wir erforschen. Dazu werden neue Graphklassen definiert und diese bezüglich typischer graphentheoretischer Eigenschaften und der Komplexität der Erkennung untersucht und optimierte Zeichenverfahren entwickelt. Diese grundlegenden Forschungen dienen der Entwicklung von beyond-planar Graphen.

• DFG-Verfahren: Sachbeihilfen