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
  (Siehe online unter https://doi.org/10.37236/7216)
• 4-connected triangulations on few lines, Proc. Graph Drawing, LNCS, vol. 11904, Springer, 2019, 395–408
  S. Felsner
  (Siehe online unter https://doi.org/10.1007/978-3-030-35802-0_30)
• 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
  (Siehe online unter https://doi.org/10.1016/j.jctb.2019.02.003)
• Boolean dimension and tree-width, Combinatorica (2020), 18 p.
  S. Felsner, T. Mészáros, and P. Micek
  (Siehe online unter https://doi.org/10.1007/s00493-020-4000-9)
• 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
  (Siehe online unter https://doi.org/10.1137/1.9781611975994.136)
• 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