Graphenzeichnen: Geometrische Aspekte jenseits der Planarität

In diesem Projekt wollen wir Graphen mit geringer visueller Komplexität zeichnen. Mit visueller Komplexität meinen wir die Anzahl geometrischer Primitive, die man braucht um einen gegebenen Graphen zu repräsentieren; zum Beispiel Steigungen, Strecken oder Kreisbögen, Geraden oder Kreise und – im Dreidimensionalen – Ebenen oder Kugeloberflächen. Gleichzeitig wollen wir uns auf geometrische Aspekte der aktuellen Richtung "jenseits der Planarität" im Graphenzeichnen konzentrieren, indem wir entweder Möglichkeiten finden Kreuzungen in der Ebene zu "zähmen" oder indem wir die gegenwärtige Forschung ins Dreidimensionale fortführen. Betrachten wir zum Beispiel die Streckenzahl, also die kleinstmögliche Zahl von Strecken, deren Vereinigung eine geradlinige Zeichnung eines gegebenen Graphen enthält. Dieses Maß für die visuelle Komplexität eines Graphen wurde für planare Graphen bereits recht intensiv studiert. Für 1-planaren Graphen, also Graphen, die sich mit höchstens einer Kreuzung pro Kante zeichnen lassen, ist darüber noch nichts bekannt. Wenn wir wissen, dass ein Graph eine geradlinige Zeichnung mit höchstens einer Kreuzung pro Kante hat, können wir dann eine nicht-triviale obere Schranke für die Zahl von Strecken angeben, die wir für eine solche Zeichnung benötigen? Bekommen wir im Dreidimensionalen, wo Kreuzungen weniger problematisch sind, bessere Schranken? Die Ebenenüberdeckungszahl, die wir kürzlich eingeführt haben, ist auch ein gutes Beispiel: jeder Graph hat eine kreuzungsfreie geradlinige Zeichnung in der Ebene. Wenn wir jedoch die Klasse der planaren Graphen verlassen, wie viele Ebenen brauchen wir dann, um eine kreuzungsfreie geradlinige Zeichnung eines gegebenen Graphen "unterzubekommen"? Betrachten wir fast-planare Graphen, also Graphen, die planar werden, wenn man nur eine einzige Kante entfernt. Während Kreuzungsminimierung selbst für fast-planare Graphen NP-schwer ist, wissen wir, dass wir einen solchen Graphen immer so zeichnen können, dass die Zeichnung in die Vereinigung von vier Ebenen (oder trivialerweise zwei Kugeloberflächen) "passt". In diesem Gebiet gibt es viele offene Fragen. Zum Beispiel: Genügt eine sublineare Zahl von Ebenen für kubische Graphen?