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