Topological Graph Theory, Applications and Abstraction

Topological graph theory, applications and abstraction.

Joan P. Hutchinson

Professor of Mathematics and Computer Science

Macalester College

Graph theory is the study of discrete, finite, 2-dimensional structures. Topological graph theory is the study of their embeddings, suitably faithful representations, in various geometric spaces. Here we compare and contrast embeddings on surfaces, locally 2-dimensional spaces, and on multiple planar layers. There is elegant mathematical theory for the former case; there are devilishly hard problems with the latter, encompassing many applications. Approximations and partial results are thus often used, but perhaps surprisingly some applications lend themselves to the abstract theory of surface embeddings. In this talk I will concentrate on graph-coloring problems on surfaces and on planar layers. The most widely-know problem is that of the Four-Color Theorem: how many colors are needed to color the countries of a map when countries with a border in common must receive different colors? We now know that four colors suffice for planar maps, but that four are not enough when maps are drawn on nonplanar surfaces or on multiple planar layers. We'll look at theory and its application to the testing of printed circuit boards that arise in these contexts.