11

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)

Andrew Tomazos
  • 66,139
  • 40
  • 186
  • 319
  • 1
    This seems like it would do better on [Mathematics](http://math.stackexchange.com/). – Kevin Reid Apr 28 '12 at 23:48
  • 3
    The quote can be found here: [Gansner, Emden R.](http://www.research.att.com/people/Gansner_Emden_R/) (2006-03-30). "[overlapping subgraphs](http://marc.info/?l=graphviz-interest&m=114421940507106)" _graphviz-interest mailing list_. 442C5B16.5030808@research.att.com. – minopret Nov 14 '12 at 17:33
  • 1
    I see that my plan below for diagramming with GraphViz is similar to [gauden's plan for diagramming in NetworkX and matplotlib](http://stackoverflow.com/a/10814476/931925). – minopret Nov 14 '12 at 19:02

2 Answers2

5

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'.

Antti Huima
  • 25,136
  • 3
  • 52
  • 71
  • So suppose N = 100, and i R j is true for all i and j, what would the diagram look like? – Andrew Tomazos Apr 29 '12 at 20:28
  • You have 100 circles and they all overlap. – Antti Huima May 01 '12 at 07:17
  • However, as you can see in Wikipedia "[Venn diagram](http://en.wikipedia.org/wiki/Venn_diagram)", there are in fact algorithms, due to Venn and others, to draw more-or-less nicely an arbitary number N of regions (not all circles) in the plane that show all 2^N-1 intersection regions (plus the one region that is exterior to all of them). The problems with these constructions are the obvious ones: the aesthetic judgment of more or less, the large number 2^N of intersection regions, and the space that is necessary in order to make them all big enough. – minopret Nov 14 '12 at 17:48
3

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; .

minopret
  • 4,726
  • 21
  • 34