Basic algorithms for surface-embedded graphs

Published on Nov 04, 20132762 Views

Jeff Erickson

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 th

Summer School on Computational Topology 2013 - Ljubljana

Related categories

Topology

Watch other parts

Chapter list

Basic Algorithms for Surface Graphs00:00

Surfaces01:01

Surface classification02:03

Graphs - 102:30

Graphs - 203:13

Surface embedding06:05

Surface map07:13

Navigating a surface map - 108:17

Navigating a surface map - 208:32

Navigating a surface map - 308:39

Navigating a surface map - 408:57

Navigating a surface map - 509:14

Navigating a surface map - 609:50

Navigating a surface map - 710:22

Polygonal schema - 112:12

Adjacency list12:52

Polygonal schema - 213:25

Polygonal schema - 313:31

Polygonal schema - 413:49

Rotation system15:25

Standard map data structure15:39

Duality - 117:11

Duality dictionary - 119:39

Duality dictionary - 221:05

Duality dictionary - 321:32

Duality dictionary - 421:34

Data structures again - 121:50

Data structures again - 322:55

Data structures again - 223:02

Euler’s formula23:39

Euler’s formula proof26:14

Corollaries27:57

Tree-cotree decompositions - 231:23

Tree-cotree decompositions - 131:31

Tree-cotree decompositions - 331:43

Tree-cotree decompositions - 431:50

Tree-cotree decompositions - 532:26

Tree-cotree decompositions - 632:31

Tree-cotree decompositions - 732:36

Tree-cotree decompositions - 832:37

Cut graphs35:00

Shortest nontrivial cycles35:12

Nontrivial loops and cycles37:37

Greedy tree-cotree decomposition41:43

Fundamental loops and cycles41:55

Three-path condition - 142:05

Shortest nontrivial loops43:53

Shortest non-trivial cycles46:32

Papercraft Self-Portrait49:43

Three-path condition - 250:04

Duality - 251:41