维恩图绘制算法 [英] Venn Diagram Drawing Algorithms

问题描述

有人问到GraphViz中子群集重叠的问题，并得到以下答复:

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.

维恩图绘制问题"的正式定义或示例是什么?为什么很难(我假设NP完全/困难)? (要点:画出一个已知的NP完全问题的约简)

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)

推荐答案

您有N个点和一个二元关系R，并且需要以图形方式表示该关系，以便每个节点都在欧几里得平面上由一个圆表示，因此当且仅当对于相应的节点n和n'，两个圆重叠时才保持n R n'.

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

这篇关于维恩图绘制算法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！