[3-circle Venn diagram -- click me for main page]

THE ELECTRONIC JOURNAL OF COMBINATORICS (ed. March 2001), DS #5.

Venn Diagram Survey
Variations and Extensions

Beyond what we've discussed in the preceding pages, there are many other aspects of Venn diagrams that have been considered in the literature. We mention some of these below.

Geometrical Variations

Convexity

A Venn diagram is convex if the interiors of all its curves are convex. Note that the regions of a Venn diagram can alway be made convex, for example, by taking the Tutte embedding of the diagram. Grünbaum defines a stronger notion of convexity by insisting that not only are the curves convex, but also regions and the complement of the external region; we call this condition strong convexity.

Every monotone Venn diagram is isomorphic to a convex diagram via the following result of Bultena, Grünbaum, and Ruskey [BGR]. A FISC is a family of finitely intersecting simple closed curves in the plane, with the property that the intersection of the interiors of all the curves is not empty. Clearly, every Venn diagram is a FISC. A FISC is monotone if its directed dual graph has a unique source and a unique sink; this corresponds with our definition of a monotone Venn diagram.

Theorem BGR A FISC has a convex drawing in the plane if and only if it is monotone. The survey article of Hamburger [Ha98] contains a wealth of material on geometric aspects of Venn diagrams, particularly convexity issues.

Diagrams made from convex k-gons

Let k-gon designate any convex polygon with at most k sides. Define N(k) to be the maximum number of curves in a Venn diagram whose curves are k-gons. Grünbaum [Gr75] proves that N(k) is asympotically lg(n) via a sqeezing argument, where lg denotes the base 2 logarithm. The upper bound uses a construction very much like Edwards' general construction, except that the circle is replaced by a square and the nth curve is a 2ⁿ-gon. Also, Grünbaum [Gr75, pg. 17] states that "the construction we used ... is a modification to convex polygons of the method described in Moor [Mo]."

Define K(n) to be the smallest k for which there exists a Venn diagram of K(n) curves, all of which are k-gons. Grünbaum [Gr75] contains a proof of the following theorem.

Theorem G. K(3) = K(4) = K(5) = 3, and K(6) < 5.

The value of K(7) is unknown, but Grünbaum has constructed and independent family of 7 hexagons.

Recently, Jeremy Carroll of HP labs (Bristol, England) [Ca99] has solved the problem of finding a collection of six triangles that form a Venn diagram, thereby proving that K(6) = 3. This was listed as an open problem in the first version of this survey.

Six amazing triangles

Exposure

A Venn diagram is exposed if each of its curves touches the outer face at some point of non-intersection. Note, for example, that the 3-Venn diagram #3.2 is not exposed, even though all curves have a point of intersection on the outer face. Stated in terms of n-Venn graphs, being exposed is the same as the condition that the vertex corresponding to the outer face has degree n. Every symmetric Venn diagram must be exposed (obvious) and every convex Venn diagram must be exposed ([Gr92a]). A Venn diagram has a hidden curve if it has a curve that does not touch the outer region. For example, in Venn's general construction, curves 4,5,...,n-1 are all hidden. Chilakamarri, Hamburger, and Pippert [CHP96b] gave an example, shown below, of a simple 6-Venn diagram which is not in the same class as any exposed diagram. The hidden curve is the dotted green one.

All simple Venn diagrams with five or less curves are exposed, but with five curves there are 8 (5 reducible, 3 irreducible) that do not have a convex drawing in the plane [CHP97a].

More Ellipses

Hamburger and Pippert [HP96a] proved that there are simple reducible Venn diagrams with 5 congruent ellipses, in spite of the fact that Venn had stated that there are no such diagrams. In fact, there are two of them, but they are in the same class.

Generalizing Venn Diagrams

We began the "What is a Venn diagram page" with a generalization, namely, the independent family, and there are several other generalizations that have appeared in the literature.

k-fold Venn diagrams

In an ordinary Venn diagram each intersection consists of one connected region. Fisher, Koh, and Grünbaum [FKG] define a k-fold Venn diagram to be one in which each intersection consists of exactly k connected regions. They show how to construct such diagrams for any n,k > 1.

d-dimensional Venn diagrams

Independent sets and Venn diagrams can be generalized to more than two dimensions. In the definition of independent set and Venn diagram, "curve" gets replaced with "boundary of an open d-cell" (that is, homeomorphic to a d-sphere) and "region" is replace with "open d-cell". Rényi, Rényi, and Surányi [RRS] proved that an independent family of d-spheres has at most d+1 members, thereby generalizing the result that a Venn diagram whose curves are circles contains at most three curves.

Grünbaum [Gr75] mentions several general geometric problems regarding d-dimensional diagrams where the sets are required to be boundaries of d-polytopes or convex regions.

Infinitely intersecting Venn diagrams

If we relax the restriction that Venn diagrams meet in only finitely many points, then we lose some of the nice graph theoretic considerations (e.g., the dual graph is no longer a subgraph of the hypercube), but do gain some flexibility. Below we show a diagram made from three congruent curves, red, blue, and green. Each curve is congruent and they are successively rotated by pi/4 radians about the central point.

Such a construction is possible for any n, and is attributed to Peter Shor in Knuth, Graham, and Patashnik [GKP]. The idea of the construction is to take a De Bruijn cycle⁹, C, of length 2ⁿ, together with a regular 2ⁿ-gon inscribed in a circle. Make a curve by successively choosing a circular arc for each 1 in C and a polygonal edge segment for each 0. To obtain the other curves rotate this one about the central point by 2 k pi / 2ⁿ radians for k = 1,2,...,n-1. The example shown above is created by starting with the De Bruijn cycle C = 00011101.