Graphen mit geometrischen Darstellungen

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

• Erstellungsjahr: 2020

Zusammenfassung der Projektergebnisse

We have obtained valuable insights in each of the three focus areas of the project. (I.) Geometric representations of planar graphs. (II.) Intersection representations and order. (III.) Sparse classes of graphs and coloring problems. For me the most haunting problem remains the behaviour of the algorithm that was developed for the construction of homothetic triangle contact representations of triangulations. We still have no proof that it stops. In this project, from the study of contact representations with pentagons and k-gons, we found a wealth of variants of the algorithm. It will be interesting to better understand applications and behaviour of this generic algorithm.

Projektbezogene Publikationen (Auswahl)

• Pentagon contact representations, Electr. J. Combin. 25 (2018), no. P3.39, 38 p.
  S. Felsner, H. Schrezenmaier, and R. Steiner
  
• 4-connected triangulations on few lines, Proc. Graph Drawing, LNCS, vol. 11904, Springer, 2019, 395–408
  S. Felsner
  
• Separating tree-chromatic number from pathchromatic number, J. Comb. Theory Ser. B 138 (2019), 206–218
  F. Barrera-Cruz, S. Felsner, T. Mészáros, P. Micek, H. Smith, L. Taylor, and W. T. Trotter
  
• Boolean dimension and tree-width, Combinatorica (2020), 18 p.
  S. Felsner, T. Mészáros, and P. Micek
  
• Improved bounds for centered colorings, Proc. ACM-SIAM Symp. Discr. Algo., SIAM, 2020, 2212–2226
  M. Dębski, S. Felsner, P. Micek, and F. Schröder
  
• On covering numbers, Young diagrams, and the local dimension of posets (2020), 18 p.
  G. Damásdi, S. Felsner, A. Girão, B. Keszegh, D. Lewis, D. T. Nagy, and T. Ueckerdt