[Colloquium] Stefankovic/Dissertation Defense/5-10-05

[Margaret Jaffey]

	Department of Computer Science/The University of Chicago

			*** Dissertation Defense ***


Candidate:  Daniel Stefankovic

Date:  Tuesday, May 10, 2005

Time and Location:  3:00 p.m. in Ryerson 251

Title:  Curves on Surfaces, String Graphs, and Crossing Numbers

Abstract:
Computational topology is a classical algorithmic theory going back
at least to Dehn (1912).  While many of its central questions have been
shown to be undecidable, we have found efficient algorithms for a number
of classical questions involving curves on surfaces. These algorithms
lead to the resolution of the complexity status of the "string graph
problem," stated by Sinden in 1966.

Classical algorithms for curves on surfaces work on explicit
representations of curves. However applications often require that the
curves be given by a compressed representation, such as, normal
coordinates, or Dehn-Thurston parameterization. The compressed
representation has size logarithmically smaller than the explicit
representation. Which problems on simple curves can be solved in time
polynomial in the size of the compressed representation?

We will show that many problems, such as, computing the number of
connected components, computing Dehn twists, and computing the geometric
intersection number have polynomial-time algorithms. Our main tool are
equations over monoids.

A string graph is the intersection graph of a set of curves in the
plane. Each curve is represented by a vertex, and an edge between two
vertices means that the corresponding curves intersect. The string graph
problem asks for an algorithm to recognize string graphs. The string
graph problem was shown to be decidable by Pach and Toth and 
independently
by Schaefer and the speaker in 2002; both papers put the problem in 
NEXP.
Finally the problem was shown to be NP-complete by Schaefer, Sedgewick,
and the speaker in 2003. Algorithms for simple curves on surfaces were 
an
essential ingredient in the solution.

The crossing number cr(G) of a graph G  is the minimum number
of crossings  needed to draw the graph G in the plane. For the odd 
crossing
number ocr(G) we minimize the number of pairs of edges that cross odd 
number
of times. A Theorem of Hanani (1934) and Tutte (1970)  states that 
ocr(G)=0 if
and only if cr(G)=0. Is ocr(G)=cr(G) for every graph G? We will show how
understanding of arcs on annulus leads to a simple counterexample.

Candidate's Advisor:  Prof. Laszlo Babai


A draft copy of Mr. Stefankovic's dissertation will be available soon 
in Ry 161A.

-- 
=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-
Margaret P. Jaffey				margaret at cs.uchicago.edu
Department of Computer Science
Student Support Rep (Ry 161A)		(773) 702-6011
The University of Chicago		http://www.cs.uchicago.edu
=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-