Visibility Representations with Crossings
African, American and Oceania Studies
Final Report Abstract
Graphen sind ein wichtiges Werkzeug zur Modellierung diskreter Strukturen. Man findet sie in vielen Anwendungen, wo sie auch als Netze, Schaltungen oder Diagramme bezeichnet werden. Die planaren Graphen sind die bekannteste Klasse. Ein Graph ist planar, wenn er in der Ebene kreuzungsfrei gezeichnet werden kann. Daraus lassen sich viele Eigenschaften herleiten, die zu einer breiten Theorie entwickelt worden sind. Unter anderem gibt es effiziente Algorithmen zur Erkennung und zum Zeichnen von planaren Graphen.. Dies gilt sowohl für konventionelle Methoden als auch für Sichtbarkeitsdarstellungen. Konventionell werden Graphen als Diagramme gezeichnet, bei denen die Knoten durch Punkte oder kleine Rechtecke dargestellt werden und die Kanten durch Linien zwischen den Knoten. Bei Sichtbarkeitsdarstellungen sind die Knoten horizontale Linien (bar) und die Kanten vertikale Sichtbarkeitslinien. Graphen aus Anwendungen sind in der Regel nicht planar. Kreuzungen sind unvermeidbar. Besondere Graphklassen dieses Typs sind die 1-planaren Graphen und die bar 1-visibility Graphen. Ein Graph ist 1-planar, wenn eine Kante höchstens einmal in einer konventionellen Zeichnung gekreuzt werden kann. Bei bar 1-visibility sind die Knoten halbtransparent und eine Sichtbarkeitslinie kann einen Knoten durchdringen, oder kurz eine Kante kann höchstens einen Knoten schneiden. Wir haben einen signifikanten Unterschied zum planaren Fall aufgedeckt und gezeigt, dass Kanten-Knoten Kreuzungen bei bar 1-visibility Darstellungen mächtiger sind als Knoten-Knoten Kreuzungen bei konventionellen Zeichnungen. Dies gilt auch bei der Einschränkung auf außen planare Graphen und den korrespondierenden linksbündigen Sichtbarkeitsdarstellungen. Für die entsprechenden Graphklassen o1p (outer 1-planar) und AB1V (aligned bar 1-visibility) wurden Probleme wie untere Schranken für die Dichte maximaler Graphen, die Komplexität der Erkennung und Schranken für spezielle Graphparameter gelöst. Diese Arbeiten sind insgesamt ein Beitrag zur Theorie der „beyond-planar“ Graphen, bei der es um Graphen theoretische und algorithmische Fragen zu allgemeinen Klassen von Graphen geht, die die planaren Graphen umfassen und Kreuzungen irgendwie reglementieren. „beyond-planar“ ist ein aktueller hot-spot im Graph Drawing.
Publications
- 1-Visibility Representations of 1-Planar Graphs. J. Graph Algorithms Appl. 18(3): 421-438 (2014)
F. J. Brandenburg
(See online at https://dx.doi.org/10.7155/jgaa.00330) - 1-Planarity of Graphs with a Rotation System. J. Graph Algorithms Appl. 19(1): 67-86 (2015)
Ch. Auer, F. J. Brandenburg, A. Gleißner, J. Reislhuber
(See online at https://dx.doi.org/10.7155/jgaa.00347) - Outer 1-Planar Graphs. Algorithmica 74(4): 1293-1320 (2016)
Ch. Auer, Ch. Bachmaier, F. J. Brandenburg, A. Gleißner, K. Hanauer, D. Neuwirth, J. Reislhuber
(See online at https://doi.org/10.1007/s00453-015-0002-1) - Recognizing and drawing IC-planar graphs. Theor. Comput. Sci. 636: 1-16 (2016)
F. J. Brandenburg, W. Didimo, W. S. Evans, Ph. Kindermann, G. Liotta, F. Montecchiani
(See online at https://doi.org/10.1016/j.tcs.2016.04.026) - Recognizing Optimal 1-Planar Graphs in Linear Time. Algorithmica
F. J. Brandenburg
(See online at https://doi.org/10.1007/s00453-016-0226-8) - On Aligned Bar 1-Visibility Graphs. J. Graph Algorithms Appl. 21(3): 281-312 (2017)
F. J. Brandenburg, A. Esch, D. Neuwirth
(See online at https://dx.doi.org/10.7155/jgaa.00417)
