Overview
This course teaches about adjacency labelling for planar graphs and beyond. The learning outcomes include understanding universal graphs, the strong graph product, binary search trees, row code trees, bulk insertion, deletion, rebalancing, and the product structure theorem. The course covers the skills of labelling schemes, graph products, and tree structures. The teaching method involves theoretical explanations and examples. The intended audience for this course is individuals interested in graph theory, data structures, and algorithms.
Syllabus
Intro
Adjacency Labelling
Universal Graphs Labeling schemes and universal graphs
Planar Graphs
The Strong Graph Product
The Product Structure Theorem
Binary Search Trees Any binary search tree can label a path
The Row Code Tree Biased binary search res
Bulk Insertion
Bulk Deletion
Rebalancing
Missing Pieces
Summary and Conclusions Summary
Taught by
IEEE FOCS: Foundations of Computer Science