6.889: Algorithms for Planar Graphs and Beyond (Fall 2011)

Erik Demaine, Shay Mozes, Christian Sommer, Siamak Tazari


[Home] [Problem Sets] [Project] [Lectures] [Problem Session Notes] [Klein's Book]

Lectures (including video)

L01 Sept. 7 Erik

[+] Introduction: Graphs considered: planar, bounded-genus, apex-minor-free, H-minor-free. Problems considered and survey of results.

[Notes] [Video]
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.
L02 Sept. 12 Shay

[+] Embedded and planar graphs: Basic definitions and concepts: combinatorial embeddings, duality, inter-digitating trees, cut-cycle duality.

[Notes] [Video]
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.
L03 Sept. 14 Christian

[+] Planar separators: Lipton-Tarjan and Miller's separators, r-divisions.

[Notes] [Video]
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.

L04 Sept. 19
Sept. 26
Christian

[+] Single-source shortest paths: Nonnegative lengths in planar graphs.

[Notes] [Video]
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.

L05 Sept. 26 Siamak

[+] Shortest paths and recursive divisions in minor-free graphs.

[Notes] [Video]
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 works for both planar and minor-closed classes. However, both the recursive division algorithm and the SSSP analysis require the graph to be of bounded degree and it turns out that, in general H-minor-free graphs, a reduction to the bounded-degree case as in the planar case is not possible. We will see how to use knitted H-partitions to overcome this issue and obtain a generalized recursive division algorithm for all H-minor-free classes.

[HKRS97] M. R. Henzinger, P. N. Klein, S. Rao, S. Subramanian: Faster shortest path algorithms for planar graphs. In: Journal of Computer and System Sciences, vol. 55(1):pp. 3-23, 1997.
[RW09] B. Reed, D. R. Wood: A linear-time algorithm to find a separator in a graph excluding a minor. In: ACM Transactions on Algorithms, vol. 5(4):pp. 1-16, 2009.
[TM09] S. Tazari, M. Müller-Hannemann: Shortest paths in linear time on minor-closed graph classes, with an application to Steiner tree approximation. In: Discrete Applied Mathematics, vol. 157:pp. 673-684, 2009.
[Taz10, Chapter 5] S. Tazari: Algorithmic Graph Minor Theory: Approximation, Parameterized Complexity, and Practical Aspects. Doctoral Dissertation, Humboldt-Universität zu Berlin, 2010.

L06 Sept. 28 Siamak

[+] Separators in H-minor-free graphs.

[Notes] [Video]
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 focus on studying a result of Alon, Seymour, and Thomas, stating that every H-minor-free graph admits a small separator and such a separator can be found in polynomial (in fact, subquadratic) time. To this end, we introduce the notion of a haven and show that every graph with a haven of large order must contain a large clique as a minor. We will also briefly discuss how the concept of a knitted H-Partition introduced in the last lecture can be used to find a slightly larger separator in linear time.

L07 Oct. 3 Siamak

[+] Treewidth and parameterized complexity.

[Notes] [Video]
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 treewidth, while not losing too much, and then solve the problem exactly on that instance. We study treewidth, pathwidth, and some of their most fundamental properties.

Treewidth is a natural parameter of a graph and as we will see, if a graph has small treewidth, then we can solve a large number of NP-hard problems efficiently - regardless of the size of the graph. This takes us to the realm of parameterized complexity theory where we study problems not just with regard to the input size but together with a parameter. The goal is to find algorithms where we confine the exponential behavior to the parameter and remain efficient in the input size; hence, when the parameter is small, we still obtain very good algorithms. Another goal is to develop a robust negative theory that allows us to show that, in all likelihood, certain parameterized problems do not admit efficient algorithms in this sense.

L08 Oct. 5 Shay

[+] Approximation schemes in planar graphs: Branchwidth and Baker's technique.

[Notes] [Video]
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. We use the radius bound on the width of a decomposition of planar graphs to devise a PTAS for minimum vertex cover. This PTAS is an example of a general technique due to Baker, which can be applied to many other problems.
L09 Oct. 12 Siamak

[+] Approximation schemes in minor-free graphs I: local treewidth and apex-minor-free graphs, extension to H-minor-free graphs, deletion decomposition

[Notes] [Video]
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). This idea of a simplifying decomposition is one of the main themes of this course.

We will then see how to generalize this idea from planar graphs to apex-minor-free graphs. To this end, we introduce the notion of local treewidth, one of the major concepts in algorithmic graph structure theory. For the generalization to H-minor-free graphs we will have to look at the Robertson-Seymour decomposition of H-minor-free graphs into clique-sums of almost embeddable graphs.

All in all, we obtain a clean and simple deletion decomposition theorem for all H-minor-free graphs that can be used to obtain many approximation algorithms, PTASes, and parameterized algorithms.

L10 Oct. 17 Siamak

[+] Approximation schemes in minor-free graphs II: Bidimensionality: Subexponential FPT algorithms and EPTAS

[Notes] [Video]
In this lecture we will explore bidimensionality - a powerful theory that encompasses and unifies a very large fraction of what we know algorithmically about planar and H-minor-free graphs as far as PTASes and parameterized algorithms go. The main idea of how to establish parameter-treewidth bounds using grids is very simple and easy to grasp and immediately leads to subexponential parameterized algorithms for a large number of problems. After that, we study an abstract framework of how to derive EPTASes for many of our favorite problems using bidimensionality as the backbone.
L11 Oct. 19 Christian

[+] Multiple-source shortest paths.

[Notes] [Video]
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'', for all the nodes on any face of a planar graph. We shall see that, by doing so, we can compute the shortest-path distance from all the nodes on a single face in time O(n log n) (plus roughly the number of distances output).
L12 Oct. 24
Oct. 26
Christian

[+] Exact distance oracles for planar graphs.

[Notes] [Video]

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: (1) given a graph G, a preprocessing algorithm constructs a data structure and (2) given the data structure and a pair of nodes (v,w), a query algorithm computes and outputs the distance d(v,w) with respect to G. Three quantities and their tradeoffs are of particular interest: the running times of the preprocessing and query algorithms, and the space requirement of the data structure. We shall see that, for any planar graph and for any integer 1<r<n, there is a distance oracle with preprocessing time and space O(n2/r) and query time O(√r) (up to logarithmic factors).

To obtain these data structures, we shall use r-divisions, MSSP, and an efficient implementation of Dijkstra's algorithm, which we refer to as FR-Dijkstra (due to Fakcharoenphol and Rao). FR-Dijkstra is executed on a rather dense graph with the nodes being the boundary nodes of some pieces of an r-division and the edges representing the shortest paths within these pieces (so-called dense distance graphs). This particular implementation requires time (almost) proportional to the number of nodes only (as opposed to the number of edges, which is much bigger). The edges not considered are redundant and they can be safely ignored due to the Monge property, which essentially says that some shortest paths in planar graphs do not cross.

The efficient implementation of Dijkstra's algorithm and variants thereof also play a crucial role in subsequent lectures on shortest paths with negative lengths and maximum flow.

L13 Oct. 26 Christian

[+]Approximate distance oracles for planar graphs.

[Notes] [Video]

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. Analogously to exact distance oracles, approximate distance oracles consist of two algorithms: (1) given a graph G and an approximation parameter ε, a preprocessing algorithm constructs a data structure and (2) given the data structure and a pair of nodes (v,w), a query algorithm computes and outputs an estimate for the distance d(v,w) with respect to G. The estimate is supposed to be at most (1+ε) times larger than the actual shortest-path distance (and no smaller).

We shall see that, for any planar graph and for any ε>0, there is a (1+ε)-approximate distance oracle with preprocessing time O((n/ε) log2 n) and space O((n/ε) log n) and query time O((1/ε) log n).

To obtain these data structures, we recursively separate the graph by shortest paths. On these path separators, we carefully select a set of portals, through which we approximate shortest paths that intersect with the separator path.

L14 Oct. 31 Shay

[+] Shortest paths with negative lengths in planar graphs.

[Notes] [Video]
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). We define the Monge property for matrices and introduce an algorithm nicknamed SMAWK (due to Aggarwal, Klawe, Moran, Shor and Wilber) for efficient search in Monge matrices. The notes also sketch a generalization of the shortest paths algorithm to graphs with bounded genus.
L15 Nov. 2 Christian

[+] PTAS for planar TSP: Klein's framework for approximation schemes in planar graphs

[Notes] [Video]

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 with approximation ratio strictly below 3/2.

TSP is NP-hard even for planar graphs. In this lecture, we discuss a linear-time approximation scheme for planar graphs. For any constant ε>0, there is an algorithm that finds a tour of length at most (1+ε) times the optimal length of a tour. (Unless P=NP, such an approximation scheme cannot exist for general graphs.)

The TSP algorithm also serves as a beautiful example of a more general framework for efficient approximation schemes in planar graphs.

It may be helpful to review (/ first watch) some of the materials of Lecture 8 on approximation schemes in planar graphs.

L16 Nov. 7 Siamak

[+] PTAS for planar subset-connectivity problems I: construction of a mortar graph-brick decomposition and spanner for subset TSP and Steiner tree

[Notes] [Video]
In this lecture we study the breakthrough result of Borradaile, Klein, and Mathieu regarding a PTAS for Steiner tree in planar graphs. Steiner tree is a subset-type problem, where we mainly care about a given subset of terminals in the graph. In particular, the weight of a Steiner tree can be arbitrarily smaller than the minimum spanning tree of the graph. This makes it very different from all problems we have studied so far.

In the previous lecture we got acquainted with Klein's framework for designing PTASes in planar graphs and applied it to the TSP problem. In this lecture, we review this framework and see how to apply it to the Steiner tree problem. We will see that the most difficult step is to obtain a spanner. We study the so called mortar graph-brick decomposition and how it gives rise to a spanner. This decomposition has been applied to further problems as well and has been generalized to bounded-genus graphs.

In Lecture 16 we will describe the algorithm and its correctness based on a structure theorem. The structure theorem itself is presented in Lecture 17.

L17 Nov. 9 Siamak

[+] PTAS for planar subset-connectivity problems II: Structure theorem for Steiner tree

[Notes] [Video]
Following up on Lecture 16, we prove the structure theorem for Steiner tree, which is the heart of the correctness of the PTAS.
L18 Nov. 14 Shay

[+] Flow in planar graphs I: undirected min cut, circulations and max-flow in st-planar graphs.

[Notes] [Video]
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 use these concepts in a linear-time algorithm for maximum flow in the special case where the source and sink lie on the same face (st-planar graphs).
L19 Nov. 16 Shay

[+] Flow in planar graphs II: maximum st-flow in directed planar graphs.

[Notes] [Video]
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.
L20 Nov. 21 Shay

[+] Flow in planar graphs III: maximum flow with multiple sources and sinks in directed planar graphs.

[Notes] [Video]
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.
L21 Nov. 28 Shay

[+] Flow in planar graphs IV: maximum flow with multiple sources and sinks in directed planar graphs.

[Notes] [Video]
We continue the presentation of the O(n log3n) time algorithm for maximum flow with multiple sources and sinks in directed planar graphs. After a short recap of where we left off at the end of lecture 20, we finish the description of the procedure to eliminate residual paths between nodes with positive and negative excess on a cycle. Then we discuss some additional complication that arise in the recursive approach.
L22 Nov. 30 Siamak

[+] Introduction to Graphs on Surfaces: 2-cell embeddings, classification of surfaces, combinatorial embedding schemes, genus, cycles

[Notes]
We discuss some basics on graphs on surfaces as given in the book "Graphs on Surfaces" by Bojan Mohar and Carsten Thomassen. Specifically, we discuss 2-cell embeddings, classification of surfaces, combinatorial embedding schemes, genus, and cycles of embedded graphs.
L23 Dec. 5 Erik

[+] Contraction decomposition of bounded-genus and H-minor-free graphs: PTASs, FPT algortihms, k-cut, radial coloring, tight roots, radially shortest paths, te structures

[Notes] [Video]
This lecture is about contraction decomposition: partitioning the edges of the graph into k pieces (for a specified integer k ≥ 2) such that contracting any piece reduces the graph down to bounded treewidth. We've already seen in Lecture 15 how to do this for planar graphs. In this lecture, we see how to do it in bounded-genus graphs in detail, and H-minor-free graphs at a high level. We also briefly discuss applications of contraction decomposition to PTASs and FPT algorithms. The H-minor-free contraction decomposition is a new result from STOC 2011 by Demaine, Hajiaghayi, and Kawarabayashi.
L24 Dec. 7 Siamak

[+] Steiner tree in bounded genus graphs / Beyond H-minor-free: Overview of (sparse) graph classes.

[Notes] [Video]

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!

L25 Dec. 12 Christian

[+] Shortest paths with negative lengths in minor-free graphs.

[Notes] [Video]

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.

Dec. 14 Project Presentations no notes or video

Credits

Videography: Shay Mozes
Christian Sommer
Siamak Tazari
Equipment: Video shot with a Canon VIXIA HG21 camera using Manfrotto 701HDV Pro Fluid Video Mini Head on Manfrotto 055XPROB Aluminum Tripod Legs. Audio recorded using Countryman IsoMax E6 EarSet Microphone on camera using Sennheiser EW 112-p G3 wireless microphone system. See our guide to recording video lectures.
Editor: Erik Demaine