Monday, April 30, 2012

Venn Diagram Drawing Algorithms

Someone was 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)

No comments:

Post a Comment