Graphenorientierungen in Ebene und Raum

• Antragsteller: Professor Dr. Stefan Felsner
• Fachliche Zuordnung: Mathematik
• Förderung: Förderung von 2007 bis 2016
• Projektkennung: Deutsche Forschungsgemeinschaft (DFG) - Projektnummer 55908010

• Erstellungsjahr: 2015

Zusammenfassung der Projektergebnisse

Im Zentrum der Untersuchungen in der ersten Förderperiode standen α-Orientierungen planarer Graphen. Das sind Orientierungen, bei denen jeder Knoten eine durch α vorgegebene Anzahl von ausgehenden Kanten hat. Wichtige Beispiele sind Schnyder Woods von Triangulierungen und 2-Orientierungen von Quadrangulierungen. Mit K. Knauer entwickelten wir Verallgemeinerungen der Flip-Verbände von α-Orientierungen, der allgemeinste Fall ist hier durch distributive Polyeder gegeben. Die Struktur der Flipa Verbände spielt eine wichtige Rolle für die Mischzeit der Flip-Markovketten von α-Orientierungen. Entgegen unseren Erwartungen stellte sich heraus, dass es selbst in den Flip-Verbänden von Schnyder Woods “Flaschenhälse” geben kann, diese Flaschenhälse sind Obstruktionen gegen eine polynomielle Mischzeit. In der zweiten Förderperiode verschob sich der Fokus auf Anwendungen von Schnyder Woods und anderen α-Orientierungen. Mein persönlicher Favorit unter den Anwendungen ist die Konstruktion von Kartogrammen für Triangulierungen im rektilinearen Modell. Dabei kombinieren wir Zeichnungen, die auf Schnyder Woods basieren, mit Resultaten zu flächenuniversellen Rechteckszerlegungen. Rektilineare Modelle für die Darstellung von Graphen entwickelten sich zu einem im Antrag noch nicht vorgesehenen Schwerpunkt. In diesem Bereich konnten wir zahlreiche Beiträge leisten, die auf vielfältigen Techniken aufbauen, z.B. auf diskreten harmonischen Funktionen und Flüssen. Mit N. Aerts studierten wir, welche planaren Graphen eine Zeichnung bea sitzen, in der jede Fläche ein Dreieck ist. Auch in diesem Kontext spielten diskrete harmonische Funktionen, Mehrgüterflüsse und Schnyder Woods eine Rolle. Aus dem Studium der Schnittgraphen von horizontalen und vertikalen Segmenten entstand ein unerwartet kurzer und eleganter Beweis für die auf Brightwell und Trotter zurückgehende obere Schranke von 4 für die Dimension der Inzidenzordnung allgemeiner planarer Karten. Im Themenschwerpunkt “Ordnungen und Dimension” konnten noch zwei weitere bemerkenswerte Ergebnisse erzielt werden. Yannakakis zeigte 1982, dass die Berechnung der Dimension von Ordnungen im Allgemeinen NP-schwer ist. Offen blieb die Komplexität des Entscheidungsproblems für Dimension 3 bei Eingaben der Höhe 2. Gemeinsam mit I. Mustata und M. Pergel konnten wir zeigen, dass auch dieser Spezialfall NP-vollständig ist. Das Ergebnis wäre ohne die Vorarbeiten zu Schnittgraphen von Segmenten nicht zustandegekommen. P. Micek und V. Wiechert führten die von Trotter und mir angestoßenen Untersuchungen zur Dimension von Ordnungen mit planaren Covergraphen weiter. Mit G. Joret erzielten die beiden das bisher stärkste Ergebnis in dieser Richtung: Die Dimension von Ordnungen der Höhe ≤ h ist auch dann schon beschränkt, wenn der Covergraph zu einer Klasse mit bounded expansion gehört.

Projektbezogene Publikationen (Auswahl)

• Bijections for Baxter families and related objects. J. Comb. Theory Ser. A 18, (2011) 993–1020
  S. Felsner, E. Fusy, M. Noy und D. Orden
  
• Contact representations of planar graphs with cubes. In Proc. Symp. Comput. Geom. (2011), 315–320
  S. Felsner und M. C. Francis
  
• Distributive lattices, polyhedra and generalized flow. Europ. J. Combin. 32, (2011) 45–59
  S. Felsner und K. Knauer
  
• Computing cartograms with optimal complexity. Discr. and Comput. Geom. 50, (2013) 784–810
  M. J. Alam, T. Biedl, S. Felsner, M. Kaufmann, S. G. Kobourov und T. Ueckerdt
  
• Rectangle and square representations of planar graphs. In J. Pach, Hg., Thirty Essays in Geometric Graph Theory. Springer (2013), 213–248
  S. Felsner
  
• Straight line triangle representations. In Proc. Graph Drawing, Bd. 8242 von Lect. Notes Comp. Sci. Springer (2013), 119–130
  N. Aerts und S. Felsner
  
• Bend-optimal orthogonal graph drawing in the general position model. Comp. Geom.: Theory and Appl. , (2014) 460–468
  S. Felsner, M. Kaufmann und P. Valtr
  
• Edge-intersection graphs of grid paths: The bend-number. Discr. Appl. Math. 167, (2014) 144–162
  D. Heldt, K. B. Knauer und T. Ueckerdt
  
• Exploiting air-pressure to map floorplans on point sets. J. Graph Alg. and Appl., (2014) 233–252
  S. Felsner
  
• The order dimension of planar maps revisited. SIAM J. Discr. Math. 28, (2014) 1093–1101
  S. Felsner