Developing and Applying Structural Tools for Combinatorial Objects
Structural techniques for labeled graphs: Labeled graphs are graphs with additional information assigned to the vertices and edges: this heading encompasses a variety of well studied classes of graphs such as directed graphs, group labeled graphs, and signed graphs. We developed new general structural tools for studying labeled graphs. As examples of problems studied under the project, we characterized when directed graphs are well-quasi-ordered under directed minors as well as a considered disjoint path and cycle problems in directed graphs.
Algorithmic applications of graph structure theory: A primary motivation for studying structural decompositions of graphs is potential algorithmic applications in theoretical computer science. Examples of applications of the techniques developed in ERC DASTCO include classification theorems characterizing which demand graphs force the disjoint paths problem to be fixed parameter tractable or polynomial time solvable.
New proofs in graph minors: Structure theorems often have long and technical proofs - for example, the proof of the structure theorem of Robertson and Seymour describing graphs excluding a fixed H as a minor occupies the first sixteen papers in the Graph Minors series and runs over 400 pages. The difficulty of the proofs has been an impediment to these powerful techniques being more widely adopted in the community. Under ERC DASTCO, we developed new and simpler proofs for many of the main results in graph minors.