THE ELECTRONIC JOURNAL OF COMBINATORICS (ed. June 2005), DS #5.

Venn Diagram Survey
An Example of Separating Vertices

To make a Venn diagram more simple, we wish to add vertices, which corresponds to adding faces (by adding edges) in the dual graph. Since any face in the Venn dual whose boundary contains more than four edges corresponds to a vertex of degree greater than four in the Venn diagram, adding a chord across that face corresponds to splitting the relevant vertex into two adjacent vertices in the Venn diagram - thus adding one extra vertex into the diagram and making it "more" (i.e. closer to) simple.
Consider the symmetric 5-venn diagram shown to the left. This diagram can be constructed using the necklace construction ideas on the page Symmetric Diagrams, Necklaces, and Chains; it is very non-simple, but it is also not rigid. On this page we show how to transform it into the unique simple diagram on 5 vertices, shown at the beginning of the page on symmetric diagrams.

Below we show the corresponding unlabelled Venn dual (the red edges) overlaying a monochromatic version of the diagram to the left, and then the dual graph alone on the right. In both graphs the external vertices, corresponding to the external empty region in the Venn diagram, are identified; we separate them to emphasize the symmetry of the diagram.



To the right we show how one of the separable vertices can be separated to create a new vertex - the green and black curves have now formed a new vertex where they intersect. This corresponds exactly to adding the thin green edge in the Venn dual.

The fact that this can be done without creating any new regions corresponds to the fact that the vertices in the Venn dual corresponding to the newly neighbouring faces can have an edge added between them (i.e. their labels differ by a single bit).

Below we show how this edge can be added symmetrically to create five new vertices in the diagram (on the left) and adding five new edges to the dual (on the right).

Continuing in this fashion, we add edges to the dual graph until no more can be added; at this point the Venn dual is composed entirely of 4-faces (faces with exactly 4 edges bordering them), implying that the corresponding Venn diagram is simple. Following [KRSW], we can call this operation quadrangulation since each resulting face is a quadrangle. The final diagram is shown below; it is isomorphic to the unique simple symmetric 5-Venn diagram.

AltStyle によって変換されたページ (->オリジナル) /