All Simple Venn Diagrams are Hamiltonian

Gara Pruesse, Department of Computer Science, Vancouver Island University, Canada.
Frank Ruskey, Department of Computer Science, University of Victoria, Canada.

Abstract:

An n-Venn diagram is a certain collection of n simple closed curves in the plane. They can be regarded as graphs where the points of intersection are vertices and the curve segments between points of intersection are edges. Every n-Venn diagram has the property that a curve touches any given face at most once between the points of intersection incident to that face. We prove that any connected collection of n simple closed curves satisfying that property are 4-connected, if n > 3, so long as the curves intersect transversally and at most two curves intersect at any point. Hence by a theorem of Tutte, such collections, including simple Venn diagrams, are Hamiltonian.



Back to list of publications.