## Dr. Andrei Gagarin

When:Title: Embedding graphs containing K5-subdivisions on the torus and proving non-toroidality

Abstract:

Given a graph G, a classic problem is how to determine whether it is possible to draw G in the plane (on the sphere) with no edge crossings. Such drawing of G in the plane would be a planar embedding. The torus is the sphere with a handle, i.e. an orientable topological surface of genus 1, which is closest to the sphere. A similar problem is how to determine whether it is possible to draw G on the torus with no edge crossings, i.e. to obtain a toroidal embedding of G.

A toroidality testing algorithm usually starts with a (non-planar) subgraph of G isomorphic to a subdivision of K5 or K3,3 and tries to extend one of its embeddings on the torus to an embedding of the whole graph G in all possible ways. We have shown a modification of this approach – non-planar graphs which don’t contain certain types of K3,3-subdivisions are much easier to decide on their toroidality by decomposing them in accordance with the “edges” of K5 in the K5-subdivision, testing planarity of resulting components, and eventually considering rearrangements of planar embeddings. This provides an efficient method to handle the case of an initial K5-subdivision subgraph in the graph. For general non-planar graphs containing K3,3-subdivisions, we show some particular examples to decide on their toroidality in an ad hoc way.

(Joint work with William Kocay, University of Manitoba, Canada)