Material Detail

Basic algorithms for surface-embedded graphs

Basic algorithms for surface-embedded graphs

This video was recorded at Summer School on Computational Topology and Topological Data Analysis, Ljubljana 2013. 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


  • User Rating
  • Comments
  • Learning Exercises
  • Bookmark Collections
  • Course ePortfolios
  • Accessibility Info

More about this material


Log in to participate in the discussions or sign up if you are not already a MERLOT member.