Introduction: Graphs considered: planar, bounded-genus, apex-minor-free, H-minor-free. Problems considered and survey of results.This lecture is an introduction to the whole class, in particular an overview of the different types of graphs that we'll be talking about (the mysterious "Beyond" in the title). We also survey many different problems where we can do a lot better on planar graphs than we can on general graphs, to give you a flavor of what we will learn in the class. Algorithms for Planar Graphs and Beyond- MIT Video lectures.
Course
Algorithms for Planar Graphs and Beyond
Graphs in the real world tend to have a lot of special structure. In particular, graphs arising on this planet are often planar (or nearly so), meaning that they can be drawn in the plane or a sphere without any (or with few) edge crossings. This class is about efficient algorithms that exploit the structure of planar graphs and related graph classes, specifically graphs embeddable on a surface of low genus and graphs excluding a minor. We will focus on recent results in this exciting area (which all of the instructors actively do research in). We will organize an optional problem-solving session, during which we can jointly try to solve open problems. In the past, these sessions have led to important new results and published papers, as well as class projects. Class projects more generally can take the form of formulations of clean, new open problems; implementations of existing algorithms; or well-written descriptions of one or more papers in the area. Projects can be purely mathematical and/or theoretical computer science (algorithmic/complexity theoretic), or purely practical.
22 Lectures
-
-
Embedded and planar graphs: Basic definitions and concepts: combinatorial embeddings, duality, inter-digitating trees, cut-cycle duality. This lecture covers the basics of embedded graphs and in particular planar graphs. We give a definition of graphs that views edges (rather than vertices) as the primary entities, and use that view in defining combinatorial embeddings of graphs. We discuss deletions and contractions, introduce the concept of the dual of an embedded graph and formally define planar graphs. We show two important properties of planar graphs: the duality of cuts and cycles, and the complementarity of primal and dual spanning trees. All of these concepts will be widely used in the algorithms we will present throughout the semester.
-
Many efficient algorithms for planar graphs make use of «small separators»: small cuts that partition the graph into roughly balanced pieces. Such separators often allow us to apply a divide-and-conquer paradigm, recursively separating the graph to end up with small pieces with even smaller boundaries. These and related techniques are used in many algorithms we'll be presenting throughout the course.In this lecture, we discuss linear-time algorithms for planar graphs that find a small (O(√n)) subset of the nodes whose removal partitions the graph into disjoint subgraphs of size at most 3n/4.Based on interdigitating trees from Lecture 2, we first devise fundamental-cycle separators. We then show how to reduce the length of these cycles (1) by cutting the graph into pieces with smaller diameter and, if time permits, (2) by merging faces. Algorithms for Planar Graphs and Beyond- MIT Video lectures.
-
We see how to improve upon Dijkstra's algorithm for the SSSP problem in planar graphs with non-negative edge lengths. As an important technique, we revisit the concept of an r-division.In the previous lecture, we saw how to recursively separate a planar graph into small pieces with small total boundary. In this lecture, we see how to obtain a so-called r-division, where each individual piece is guaranteed to have small boundary (as opposed to small total boundary as in the previous lecture). We also discuss how to quickly compute such an r-division. Using an algorithm for fast r-division, we obtain a simple SSSP algorithm for planar graphs that's faster than Dijkstra's algorithm. We then discuss an even faster algorithm for SSSP in planar graphs. Despite the algorithm being quite simple, somewhat surprisingly, a rather involved analysis proves that its running time is linear, which is asymptotically optimal! We analyze a simplified version running in time O(n log logn). The algorithm works a little bit like Dijkstra's algorithm with "limited attention span": The simple version starts by decomposing the graph into pieces of size O(log4 n). Then, it repeatedly works on the piece with the current minimum for log n steps until the shortest-path distance to all nodes has been found. We (partially) analyze the running time of the simplified algorithm. Algorithms for Planar Graphs and Beyond- MIT Video lectures.
-
We discuss recursive divisions and how to obtain them in planar and minor-free graphs. This is one of the main tools that is used to obtain a linear-time SSSP algorithm and, in fact, once we have a suitable recursive division, the same SSSP algorithm work.
-
As we have seen and will see in other lectures, small separators have several important applications, ranging from shortest paths to approximation schemes. They are one of the core tools that allow for faster algorithms on certain graph classes.
-
In this lecture we introduce treewidth - one of the most central concepts in obtaining fast algorithms and approximation schemes for NP-hard problems. Indeed, a recurring theme in approximation schemes is to reduce the problem to an instance of small tree.
-
In this lecture we introduce two additional graph decompositions - carving decomposition and branch decomposition. We prove a theorem of Tamaki that roughly says that the branch-width of a planar graph is at most twice its radius.
-
In this lecture we look at Baker's technique from another perspective which leads to the notion of deletion decomposition: partitioning a graph into k parts such that removing any part gives a graph of low treewidth (in k).
-
Approximation schemes in minor-free graphs II: Bidimensionality: Subexponential FPT algortihms and EPTAS. In this lecture we will explore bidimensionality - a powerful theory that encompasses and unifies a very large fraction of what we know algorithmical.
-
Based on interdigitating trees from Lecture 2 (they're ubiquitous!) and dynamic trees, we discuss how to efficiently transform a shortest-path tree rooted at r into an SP tree rooted at its neighbor r', and then on to r''.
-
We discuss data structures that answer node-to-node shortest-path and distance queries in planar graphs. Such data structures are also known as distance oracles. These oracles consist of two algorithms.
-
We discuss data structures that answer approximate node-to-node shortest-path and distance queries in planar graphs. Such data structures are also known as approximate distance oracles.
-
We conclude our discussion of shortest paths by describing a near-linear time algorithm for shortest paths in directed planar graphs with negative arc lengths (but no negative-length cycles).
-
In the Traveling Salesman Problem (TSP) we need to find a shortest tour visiting all the nodes of a graph. For general graphs, there have been recent algorithmic breakthroughs: researchers have found polynomial-time algorithms.
-
PTAS for planar subset-connectivity problems I: construction of a mortar graph-brick decomposition and spanner for subset TSP and Steiner tree In this lecture we study the breakthrough result of Borradaile, Klein, and Mathieu regarding a PTAS for Steiner.
-
PTAS for planar subset-connectivity problems II: Structure theorem for Steiner tree Following up on Lecture 16, we prove the structure theorem for Steiner tree, which is the heart of the correctness of the PTAS.
-
We discuss Reif's algorithm for computing the minimum st-cut in an undirected planar graph. We then start treating flows in directed planar graphs by studying circulations and their relation to shortest paths and negative-length cycles in the dual.
-
We present an O(n logn) time algorithm for maximum st-flow in directed planar graphs. The algorithm, due to Borradaile and Klein, is simple and elegant and resembles the MSSP algorithm of lecture 11. The analysis we present is due to Erickson.
-
We present an O(n log3n) time algorithm for maximum flow with multiple sources and sinks in directed planar graphs. The reduction from multiple sources and sinks to single sources and sinks violates planarity. The algorithm is radically different from the algorithm for maximum st-flows of lecture 19, and uses almost all the technique for exact algorithms in planar graphs that we covered in class so far.
-
In this lecture we introduce the notion of a tree-cotree decomposition for bounded genus graphs (analogous to interdigitating trees in planar graphs) and use it to obtain a spanner for Steiner tree in bounded genus graphs. Together with the contraction decomposition theorem of Lecture 23 and Klein's PTAS framework, this results in an O(n log n) PTAS for Steiner tree in bounded genus graphs.Afterwards, we draw a bigger picture of all graph classes we have studied so far and take a peek at graph classes beyond H-minor-free graphs, in particular, classes of bounded expansion and nowhere dense classes of graphs. To understand these classes, we introduce the notion of shallow minors.Indeed, structural graph theory does not end at H-minor-free graphs!
-
We revisit the shortest paths problem, considering the case where the input is a directed minor-free graph with negative arc lengths (but no negative-length cycles).In Lecture 14, we saw almost-linear-time algorithms for the case of planar and bounded-genus graphs. Currently, comparable bounds for minor-free graphs are not known. We shall discuss Goldberg's algorithm, a shortest-path algorithm for general graphs with integer lengths, whose running time depends logarithmically on the magnitude of the largest negative arc length. By exploiting separators (Lecture 6), it runs faster on minor-free graphs than on general graphs, but it still requires superlinear time.