Doctoral Program in Computer Science
365 5th Avenue
New York City 10016
Room 4319
Phone: 212.817.8190
Fax: 212.817.1510
compsci@gc.cuny.edu
  Click here to go to the Graduate Center main page.

Computer Science Colloquium
 


Thursday, March 10, 4:15pm, room 9204/9205
 
János Pach  
(City College, CUNY)
 
"String graphs and the topological inference problem"
 
Given a simple graph G, is it possible to represent its vertices by simply connected regions in the plane so that two regions overlap if and only if the corresponding two vertices are adjacent? In other words, is G isomorphic to the intersection graph of a set of simply connected regions in the plane? This deceptively simple extension of propositional logic and its generalizations are often referred to in the literature as "topological inference problems." They have proved to be relevant in the area of geographic information systems, in neurology, VLSI design, and in graph drawing. We outline some recent results related to these questions.


 
The Colloquium is supported by generous contributions from the Bloomberg, Information Builders, Inc. and qbt Systems, Inc.