Graphs with Geometric Representations

• Applicant: Professor Dr. Stefan Felsner
• Subject Area: Mathematics
• Term: from 2016 to 2019
• Project identifier: Deutsche Forschungsgemeinschaft (DFG) - Project number 299431151

• Final Report Year: 2020

Final Report Abstract

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.

Publications

• 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