Georgia Institute of Technology College of Sciences

Structural graph theory has traditionally focused on classes of graphs that are 'sparse' rather than 'dense' (that is, have few edges rather than many edges). We will study this paradigm, focusing on modern developments for dense graphs. Along the way we will see connections to algorithms and complexity, discrete geometry, and logic. In each unit, we first introduce standard techniques for sparse graphs, and then we study their 'dense analogs'. Specific topics include connectivity, tree width and related width parameters, graphs on surfaces, graph minors, bounded expansion, and nowhere denseness, in that order. Their 'dense analogs' include, respectively: rank-connectivity, clique width, geometric intersection graphs, vertex-minors, bounded flip-width, and monadic dependence.