Schedule:The monumental Graph Minor Theory, developed by Robertson and Seymour since the 1980s, is one of the most fundamental achievements in combinatorics, and offers the potential for broad algorithmic frameworks. It took some time to realize that the techniques developed in Graph Minors can be used in the design of efficient and generic algorithms. One of the main techniques extracted from Graph Minors is based on structural results explaining the existence (or the absence) of certain grid-like or bidimensional structures in graphs.
Bidimensionality theory uses these structures to develop efficient frameworks for both approximation algorithms and fixed-parameter algorithms for a broad range of NP-hard optimization problems in a broad range of graphs, namely, planar graphs and graphs excluding a fixed minor. The theory is based on algorithmic and combinatorial extensions to parts of Graph Minor Theory, in particular initiating a parallel graph contraction theory (where edge deletion is forbidden).
This exciting area of efficient graph algorithms via bidimensionality is still under active development. The goal of this workshop is twofold: (1) a tutorial of the basic techniques and results, which may be useful for solving subproblems arising in other settings; and (2) documenting the frontiers of our knowledge and remaining open problems, to encourage more people to extend the field. Specific directions for further study include extending beyond minor-closed graph families, further connections between approximation and fixed-parameter algorithms, the challenge of directed graphs, frameworks for solving even more general graph problems, tight grid–treewidth bounds for general graphs, and making graph-minor bounds (including grid bounds) more practical in terms of constants.
Time Speaker Title 9:50-10:50 Erik Demaine History of Bidimensionality and Basic Bidimensionality 11:00-12:00 Daniel Marx The Square Root Phenomenon in Planar Graphs 12:00-2:00 Lunch break (on your own) 2:00-3:00 Fedor Fomin Advanced Bidimensionality and Its Applications 3:00-3:20 Break 3:20-4:00 MohammadTaghi Hajiaghayi Bidimensionality and Graph Decomposition 4:05-4:45 Marek Cygan Pursuing the Dependence on Treewidth in Parameterized Algorithms 4:50-5:30 Julia Chuzhoy Polynomial Bounds for the Grid Minor Theorem