Skip to content

Dr. Andrei Gagarin

Tuesday, 19th June 2018 1:00 pm
Where: E2-165 EITC

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


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)

Complete Seminar List
© 2011 University of Manitoba Department of Computer Science
Back to top