Basic algorithms for surface-embedded graphs

author: Jeff Erickson, Department of Computer Science, University of Illinois at Urbana-Champaign
published: Nov. 4, 2013,   recorded: July 2013,   views: 2736


Related Open Educational Resources

Related content

Report a problem or upload files

If you have found a problem with this lecture or would like to send us extra material, articles, exercises, etc., please use our ticket system to describe your request and upload the data.
Enter your e-mail into the 'Cc' field, and we will keep you updated with your request's status.
Lecture popularity: You need to login to cast your vote.

 Watch videos:   (click on thumbnail to launch)

Watch Part 1
Part 1 53:02
Watch Part 2
Part 2 37:13
Watch Part 3
Part 3 48:42
Watch Part 4
Part 4 22:45


For many classical algorithmic graph problems, faster algorithms are known for graphs that have additional structure. This short course will survey some important algorithmic techniques for graphs that can be drawn in the plane or other surfaces without crossing edges. The course will introduce several fundamental mathematical tools, including Euler's formula, rotation systems, duality, tree-cotree decompositions, the combinatorial Gauss-Bonnet theorem, homotopy, homology, covering spaces, balanced separators, and treewidth, as well as applications of these tools for computing minimum spanning trees, shortest paths, minimum cuts, and approximation solutions for several NP-hard prob

Link this page

Would you like to put a link to this lecture on your homepage?
Go ahead! Copy the HTML snippet !

Write your own review or comment:

make sure you have javascript enabled or clear this field: