Ordered Graph Decompositions and their Applications

• Applicant: Dr. Lena Marie Schlipf
• Subject Area: Theoretical Computer Science
• Term: since 2023
• Project identifier: Deutsche Forschungsgemeinschaft (DFG) - Project number 512370152

Algorithmic graph theory is an important and rich research area. Many real world problems can be modeled as graph theoretical problems, such as route planning, communication network design, and VLSI-design. For the last decades, ordered graph decompositions have been used as a key tool in algorithmic graph theory. These orders decompose the graph into subgraphs that fulfill certain criteria such as (edge-)connectivity. Examples are st-numberings and canonical orders. Closely related to ordered graph decompositions are inductively defined constructions of graph classes as many algorithms that compute ordered graph decompositions are based on inductively defined constructions. A good knowledge on these concepts helps a lot on attacking problems in the field of algorithmic graph theory and graph drawing; new understanding of such concepts might even help in solving some long standing open questions (e.g., the Edge-Independent Spanning Tree Conjecture). The main goal of this project is to study ordered graph decompositions and inductively defined constructions of graphs, develop new ones and illustrate their impact on applications. (1.) We study different concepts of graph decompositions and inductively defined constructions. For example, we are interested in (edge-)orders for k-(edge-)connected graphs with k larger than four. Furthermore, we plan to investigate restricted graph classes, like 1-planar graphs and subclasses thereof, as use-cases. We expect to find new orders that are not only interesting on their own behalf but can be used as a tool in order to solve a variety of problems (see (2.)). (2.) We want to illustrate the impact of (our newly invented) ordered graph decompositions and inductively defined constructions by presenting exciting applications such as recognizing Laman graphs and by investigating some long standing open problems in graph theory. Additionally, we will apply the newly invented decompositions on appealing graph drawing problems, e.g., visibility representations.

• DFG Programme: Research Grants