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.
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.
The Massachusetts Institute of Technology (MIT), founded in 1861, is located in Cambridge, Massachusetts, and is one of the foremost U.S. institutions in science and technology. It is comprised of five schools and one college, including the renowned School of Engineering and Sloan School of Management, offering Bachelor's, Master's, and Doctorate degrees. Notable alumni include Ben Bernanke, Chairman of the Federal Reserve, Benjamin Netanyahu, prime minister of Israel, and American astronaut "Buzz" Aldrin.