Online region computations for Euler diagrams with relaxed drawing conventions

Euler diagrams are an accessible and effective visualisation of data involving simple set-theoretic relationships. Efficient algorithms to quickly compute the abstract regions of an Euler diagram upon curve addition and removal have previously been developed (the single marked point approach, SMPA), but a strict set of drawing conventions (called well-formedness conditions) were enforced, meaning that some abstract diagrams are not representable as concrete diagrams. We present a new methodology (the multiple marked point approach, MMPA) enabling online region computation for Euler diagrams under the relaxation of the drawing convention that zones must be connected regions. Furthermore, we indicate how to extend the methods to deal with the relaxation of any of the drawing conventions, with the use of concurrent line segments case being of particular importance. We provide complexity analysis and compare the MMPA with the SMPA. We show that these methods are theoretically no worse than other comparators, whilst our methods apply to any case, and are likely to be faster in practise due to their online nature. The machinery developed for the concurrency case could be of use in Euler diagram drawing techniques (in the context of the Euler Graph), and in computer graphics (e.g. the development of an advanced variation of a winged edge data structure that deals with concurrency). The algorithms are presented for generic curves; specialisations such as utilising fixed geometric shapes for curves may occur in applications which can enhance capabilities for fast computations of the algorithms' input structures. We provide an implementation of these algorithms, utilising ellipses, and provide time-based experimental data for benchmarking purposes.     

PaL diagrams: A linear diagram-based visual language

Linear diagrams have recently been shown to be more effective than Euler diagrams when used for set-based reasoning. However, unlike the growing corpus of knowledge about formal aspects of Euler and Venn diagrams, there has been no formalisation of linear diagrams. To fill this knowledge gap, we present and formalise Point and Line (PaL) diagrams, an extension of simple linear diagrams containing points, thus providing a formal foundation for an effective visual language. We prove that PaL diagrams are exactly as expressive as monadic first-order logic with equality, gaining, as a corollary, an equivalence with the Euler diagram extension called spider diagrams. The method of proof provides translations between PaL diagrams and sentences of monadic first-order logic.     

A normal form for spider diagrams of order

We develop a reasoning system for an Euler diagram based visual logic, called spider diagrams of order. We define a normal form for spider diagrams of order and provide an algorithm, based on the reasoning system, for producing diagrams in our normal form. Normal forms for visual logics have been shown to assist in proving completeness of associated reasoning systems. We wish to use the reasoning system to allow future direct comparison of spider diagrams of order and linear temporal logic.     

Nesting in Euler Diagrams: syntax,semantics and construction

This paper considers the notion of nesting in Euler diagrams, and how nesting affects the interpretation and construction of such diagrams. After setting up the necessary definitions for concrete Euler diagrams (drawn in the plane) and abstract diagrams (having just formal structure), the notion of nestedness is defined at both concrete and abstract levels. The concept of a dual graph is used to give an alternative condition for a drawable abstract Euler diagram to be nested. The natural progression to the diagram semantics is explored and we present a nested form for diagram semantics. We describe how this work supports tool-building for diagrams, and how effective we might expect this support to be in terms of the proportion of nested diagrams.     

Exact and approximate area-proportional circular Venn and Euler diagrams

Scientists conducting microarray and other experiments use circular Venn and Euler diagrams to analyze and illustrate their results. As one solution to this problem, this paper introduces a statistical model for fitting area-proportional Venn and Euler diagrams to observed data. The statistical model outlined in this paper includes a statistical loss function and a minimization procedure that enables formal estimation of the Venn/Euler area-proportional model for the first time. A significance test of the null hypothesis is computed for the solution. Residuals from the model are available for inspection. As a result, this algorithm can be used for both exploration and inference on real data sets. A Java program implementing this algorithm is available under the Mozilla Public License. An R function venneuler() is available as a package in CRAN and a plugin is available in Cytoscape.