String Graphs and their complexity (Part 2 of 2)

A string graph is the intersection graph of a set of Jordan curves in the plane. Each curve is represented by a vertex, and an edge between two vertices means that the corresponding curves intersect. The complexity of recognizing string graphs was open until recently, when the problem was shown to be decidable (Pach, Toth; Schaefer, Stefankovic 2001). Shortly afterwards the problem was shown to be in NP (Schaefer, Sedgwick, Stefankovic 2003), making it NP-complete (Kratochvil, 1991). We will cover the complexity results on string graphs and their combinatorial and topological underpinnings.

Event Topic

Discrete Applied Math Seminar