Back to search

University of Victoria (Canada)

Generating and drawing area-proportional Euler and Venn diagrams

Abstract

dc:description.abstract

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.

Degree

thesis:*
Level thesis:degree_level
Doctor of Philosophy Ph.D.
Department thesis:degree_department
Department of Computer Science
Year dc:date.issued
2007

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Chow, Stirling Christopher
Advisor dc:contributor.supervisor
  • Ruskey, Frank

Subjects

dc:subject × 8

Rights

dc:rights
Statement dc:rights
  • Available to the World Wide Web
Language dc:language.iso
en, English

Identifiers

dc:identifier.*
Handle dc:identifier.uri
http://hdl.handle.net/1828/128

Chain of custody

source
Harvested from
University of Victoria (Canada)
Base URL
dspace.library.uvic.ca/server/oai/request
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
citation

Chow, Stirling Christopher. Generating and drawing area-proportional Euler and Venn diagrams. Doctor of Philosophy Ph.D. thesis, 2007. http://hdl.handle.net/1828/128