clarke@csri.toronto.edu (Jim Clarke) (03/29/88)
(SF = Sandford Fleming Building, 10 King's College Road)
(GB = Galbraith Building, 35 St. George Street)
SUMMARY:
COLLOQUIUM, Tuesday, April 5, 11 am, SF1105 -- Irith Ben-Arroyo Hartman:
"Grid Intersection Graphs"
THEORY SEMINAR, Thursday, April 7, 3 pm, GB244 -- Rajeev Motwani:
"On Embedding Graphs In 3-Space With No Linked Cycles"
---------------
COLLOQUIUM, Tuesday, April 5, 11 am, SF1105
Dr. Irith Ben-Arroyo Hartman
University of Toronto
"Grid Intersection Graphs"
An intersection graph of a family V of sets, is a graph G=(V,E) whose ver-
tices are the sets, with (vi, vj) in E if and only if sets vi and vj intersect.
A grid intersection graph (GIG) is a bipartite graph G=(X,Y;E), which is an
intersection graph of sets of horizontal and vertical segments in the plane.
We discuss intersection graphs and grid intersection graphs and prove that all
bipartite planar graphs are GIG's. These graphs have related applications to
VLSI circuit layout.
THEORY SEMINAR, Thursday, April 7, 3 pm, GB244
Rajeev Motwani
University of California
"On Embedding Graphs In 3-Space With No Linked Cycles"
We consider the problem of deciding whether a graph can be embedded in 3-
space such that no two vertex-disjoint cycles are topologically linked. The
Robertson-Seymour Theory of Graph Minors is applicable to this problem and
guarantees the existence of an O(n^3) algorithm for the decision problem.
However, not even a finite time decision procedure had been devised for
this problem. We exibhit a small set of forbidden minors and show that any
graph with these minors cannot be embedded without linked cycles. We
further establish that any graph which does not contain these minors is
embeddable without linked cycles. Thus, we have an O(n^3) algorithm for the
decision problem. We believe that the proof technique will lead to an algo-
rithm for actually embedding a graph provided it does not contain the for-
bidden minors. To the best of our knowledge, this is the first problem for
which a polynomial time algorithm has been constructed after it was shown
that such an algorithm must exist.
(Joint work with A. Raghunathan and H. Saran)
--
Jim Clarke -- Dept. of Computer Science, Univ. of Toronto, Canada M5S 1A4
(416) 978-4058
BITNET,CSNET: clarke@csri.toronto.edu CDNNET: clarke@csri.toronto.cdn
UUCP: {allegra,cornell,decvax,linus,utzoo}!utcsri!clarke