Embedded and Planar Graphs: Basic Definitions and Concepts
By Shay Mozes - MIT
-
575
- Report An Inaccuracy In Lecture Information:
Lecture Description
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.
Course Description
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.
