Simultaneous Graph Problems
Speaker: Anna Lubiw , University of Waterloo
Date: April 13 2010
Time: 4:15PM to 5:15PM
Location: 32-155
Host: Scott Aaronson, CSAIL, MIT
Contact: Be, 3-6098, imbe@mit.edu
Relevant URL: We examine problems of representing two graphs that share some vertices and edges, with a "simultaneity" requirement that the common subgraph be represented the same way.
Such problems arise whenever it is desirable to consistently represent two related graphs, for example: graphs connected in time, where one is an updated version of the other; or two social networks that share some members; or overlap graphs of DNA fragments of two similar organisms.
Two graphs that share some vertices are *simultaneously planar* if they have planar embeddings with the common vertices and edges represented by the same points and curves. We discuss what is known about this class.
Two graphs are *simultaneous interval graphs* if they can be represented as intersection graphs of intervals with common vertices represented by the same intervals. We give a polynomial time recognition algorithm (joint work with K.R. Jampani). This problem, and others dealing with simultaneous intersection graphs, are related to graph sandwich problems and to probe graphs.
See other events that are part of Theory Colloquium 2009/2010
See other events happening in April 2010
