Скачать или смотреть Structural Graph Theory Lecture-24

In today's lecture (15/09/2021), we started Module-3: Planarity.

In particular, we discussed some key concepts related to planarity: graphs and their representations; embeddings of a graph in the plane: planar as well as not planar; planar versus nonplanar graphs.

We used our intuition to observe that the decision problem (deciding whether a graph G is planar) is in NP; however, it is not immediate (unless one uses nontrivial theorems such as Kuratowski's Theorem) why it should be in co-NP.

Finally, we discussed the Jordan Curve Theorem (JCT) from topology, and discussed the relevant topological notions: curves, closed curves, simple curves, open/closed sets, and arcwise-connected sets.

In the next lecture (16/09/2021), we will use JCT to prove that the complete graph K_5 is nonplanar.