DIMACS Discrete Math/Theory of Computing Seminar


Planar Graph Models, Hamiltonian Cycles and Jordan Curves


Peter Hamburger
Indiana-Purdue University


Seminar Room 431, CoRE Building,
Rutgers University


4:30 PM
Tuesday, October 22, 1996

Using topological graph theory, planar and spherical graph models, and Hamiltonian cycles we developed methods to investigate special families of simple closed Jordan curves on the plane as well as on the sphere. Utilizing these procedures we answered several problems and conjectures of Grunbaum on Venn diagrams and independent families of sets. One of our results corrects some erroneous statements that started with John Venn more than a century ago in 1880 and have been repeated frequently by others since then. An other one answers Grunbaum's conjecture: Every Venn diagram of n curves can be extended to a Venn diagram of n+1 curves by the addition of a suitable simple closed Jordan curve. This problem also goes back to Venn itself. We also will discuse one of Peter Winkler's related conjectures. Convex and strongly convex Venn diagrams will be studied as well. Some of the results are joint results with K. B. Chilakamarri and/or R. E. Pippert, Indiana-Purdue University Fort Wayne.

Document last modified on October 14, 1996