event
Some recent results in topological graph theory
Primary tabs
TITLE: Some recent results in topological graph theory
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.)
Status
- Workflow Status: Published
- Created By: Anita Race
- Created: 10/12/2009
- Modified By: Fletcher Moore
- Modified: 10/07/2016
Categories
Keywords
Target Audience