Venn Diagram Drawing Algorithms

Question

Someone asked about overlapping subclusters in GraphViz and got the following response:

Sorry, no. General subgraphs can share nodes without implying subset containment but not clusters. The problem is in the drawing. If clusters can overlap arbitrarily, drawing them becomes the problem of drawing Venn diagrams, for which there are no good algorithms.

What is a formal definition or example of the "problem of drawing Venn diagrams"?, and why is it (I assume NP-complete/hard) hard ? (Extra points: Sketch a reduction to a well-known NP-complete problem)

Answer 1

You have N points and a binary relation R on them, and you need to represent the relation graphically so that every node is represented by a circle on Euclidean plane so that two circles overlap if and only if for the corresponding nodes n and n' it holds that n R n'.

Answer 2

Instead of a Venn diagram as such, we can in many cases use GraphViz for the same purpose using the dual graph, which is the Boolean lattice of the intersections of the sets. Each node represents a unique choice of sets to include and sets to exclude. Nodes that differ only by the inclusion/exclusion of a single set are connected.

For increasing numbers of sets, of course there are in general many, many nodes and edges. But in many practical settings there will be many sets that do not intersect at all, so that those intersection nodes and any edges from them to other nodes may be omitted. By this method the number of nodes and edges may be reduced to a practical number.

When laying out the resulting graph it may be best to select the GraphViz algorithm "neato" and to ask to avoid overlapping the nodes. One way to make those settings is by writing, inside the opening curly brace for the graph, layout=neato,overlap=prism; .