Some recent results in topological graph theory

Event Details
  • Date/Time:
    • Monday October 6, 2008 - Tuesday October 7, 2008
      3:00 pm - 3:59 pm
  • Location: Executive classroom 228
  • Phone:
  • URL:
  • Email:
  • Fee(s):
  • Extras:
Anita Race
H. Milton Stewart School of Industrial and Systems Engineering
Contact Anita Race

Summary Sentence: Some recent results in topological graph theory

Full Summary: Some recent results in topological graph theory

TITLE: Some recent results in topological graph theory

SPEAKER: Dr. Hein van der Holst


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.)

Additional Information

In Campus Calendar

School of Industrial and Systems Engineering (ISYE)

Invited Audience
No audiences were selected.
graph, superstructures
  • Created By: Anita Race
  • Workflow Status: Published
  • Created On: Oct 12, 2009 - 4:37pm
  • Last Updated: Oct 7, 2016 - 9:47pm