DMS Combinatorics Seminar

Speaker: Alec Helm (University of South Carolina)

Title: Optimal Drawings of Infinite Graphs

Abstract: A drawing of a graph is an association of vertices to distinct points and edges to Jordan curves which run between the points associated to the edge’s endvertices.  If these edge curves pairwise intersect only at mutually incident endpoints, we call the drawing an embedding. Famous 1930’s theorems of Wagner and Kuratowski give necessary and sufficient conditions for a finite graph to admit an embedding in the plane, but less known is Wagner’s 1960’s theorem giving necessary conditions for a (possibly infinite) graph to admit a plane embedding. In this talk, we will briefly discuss Wagner’s Theorem and use it as a springboard to investigate the crossing number of infinite graphs. The crossing number of a graph is the minimum number of edge intersections needed to draw the graph in the plane, and thus a graph admits a plane embedding if and only if its crossing number is zero. We show the conditions under which a graph's crossing number is well-defined, and give a characterization of the crossing number of most graphs. Along the way, we extend many classical concepts from the study of finite graph crossing number to the infinite case, such as topological minor monotonicity, the notion of augmented drawings and graphs, and niceness in graph drawing