Properties of beyond-planar graphs

• Applicant: Professor Dr. Franz Josef Brandenburg
• Subject Area: Theoretical Computer Science
• Term: since 2019
• Project identifier: Deutsche Forschungsgemeinschaft (DFG) - Project number 433963685

A topological graphs is a graph drawn in the plane. Such graphs are distinguished by the types of edge crossings. The planar graphs, the best known graph class, excludes edge crossings. Classes of graphs with restrictions on crossings are called beyond-planar graphs. Examples are k-planar graphs, where each edge is crossed at most k times, fan-crossing graphs, where the crossing edges are incident to a common endpoint or fan-crossing free graphs, where such crossings are excluded. Empirical studies have shown a strong correlation between the type and the number of edge crossings and the readability of a graph drawing. We study structural properties of classes of beyond-planar graphs, and distinguish different beyond-planar graph classes by new operations on graphs.

• DFG Programme: Research Grants