Minimum-weight tree supports and tree-shaped area-proportional Euler diagrams
Boris Klemz · 2013
Euler diagrams allow the visual representation of set systems and their intersection relations. Every set is represented by a collection of closed curves such that elements of two or more collections intersect if and only if the intersection of the corresponding sets is non-empty. In the area-proportional case each intersection’s area conveys numerical information. There exist several well-formedness conditions for Euler diagrams, which formalize desirable aesthetic properties. In this thesis we explore a close relationship between hypergraphs and Euler diagrams to obtain an area-proportional representation of the latter. A support for a hypergraph H is a graph G on the same set of vertices such that each hyperedge of H induces a connected subgraph of G. Supports that are trees serve as a basic tool for our purpose and are called tree-supports. We present an efficient approach that generates an area-proportional Euler diagram if there exists a tree-support for the input’s hypergraph. The generated Euler diagrams are guaranteed to satisfy a set of well-formedness conditions. Particularly, all used curves are simple, exactly one curve is assigned to each set, there exists exactly one connected region in the plane for every set intersection and finally, all the regions are convex. Additionally, our tree-support minimizes the total number of concurrent curves that separate the pairs of internal regions that are placed next to each other in the plane. As a byproduct, we obtain an algorithm that, for a given hypergraph, computes a minimumweight tree-support for an arbitrary edge-weight function (if one exists). The algorithm has running time O(n2(m+log n)), where n is the number of vertices and m is the number of hyperedges. This improves the best known previous algorithm for this problem [KS03], which has a time complexity of O(n4m2).