Return to search

Generating and drawing area-proportional Euler and Venn diagrams

An Euler diagram C = {c_1, c_2,..., c_n}
is a collection of n simple closed curves (i.e., Jordan curves) that partition the plane into connected subsets, called regions, each of which is enclosed by a unique combination of curves. Typically, Euler diagrams are used to visualize the distribution of discrete characteristics across a sample population; in this case, each curve represents a characteristic and each region represents the sub-population possessing exactly the combination of containing curves' properties. Venn diagrams are a subclass of Euler diagrams in which there are 2^n regions representing all possible combinations of curves (e.g., two partially overlapping circles).
In this dissertation, we study the Euler Diagram Generation Problem (EDGP), which involves constructing an Euler diagram with a prescribed set of regions. We describe a graph-theoretic model of an Euler diagram's structure and use this model to develop necessary-and-sufficient existence conditions. We also use the graph-theoretic model to prove that the EDGP is NP-complete. In addition, we study the related Area-Proportional Euler Diagram Generation Problem (w-EDGP), which involves constructing an Euler diagram with a prescribed set of regions, each of which has a prescribed area. We develop algorithms for constructing area-proportional Euler diagrams composed of up to three circles and rectangles, as well as diagrams with an unbounded number of curves and a region of common intersection. Finally, we present implementations of our algorithms that allow the dynamic manipulation and real-time construction of area-proportional Euler diagrams.

  1. http://hdl.handle.net/1828/128
Identiferoai:union.ndltd.org:uvic.ca/oai:dspace.library.uvic.ca:1828/128
Date11 June 2007
CreatorsChow, Stirling Christopher
ContributorsRuskey, Frank
Source SetsUniversity of Victoria
LanguageEnglish, English
Detected LanguageEnglish
TypeThesis
RightsAvailable to the World Wide Web

Page generated in 0.0017 seconds