SPEAKER: Dr. Hein van der Holst

ABSTRACT:

Each graph can be embedded in 3-space. The problem becomes more interesting if we put restrictions on the type of embedding. For example, a linkless embedding of a graph is one where each pair of vertex-disjoint circuits has linking number equal to zero. The class of all graphs that have a linkless embedding is closed under taking minors. Robertson, Seymour, and Thomas gave the forbidden minors for this class of graphs. Open remained how to find a linkless embedding in polynomial time. In the talk we start with discussing an algorithm to find a linkless embedding.

Instead of embedding the graph in 3-space, we could also consider mapping properties of certain superstructures of the graph in 3-space, and, indeed, if this superstructure has not the right mapping properties in 3-space, see whether it has the right one in 4-space, etc. We introduced for a graph G a new graph parameter (G), which is defined as the smallest d such that superstructures of G have a zero intersection mapping in d-space. The nicest property of this graph parameter is its independence of the superstructure and thus depends on the graph only. For d = 2 and d = 3, (G) d if and only if G is outerplanar and planar, respectively. The graphs G with (G) 4 are exactly those that have a linkless embedding. In the second part of the talk we will discuss this new graph parameter. (This part is joint work with R. Pendavingh.)