In 2D, Venn and Euler diagrams consist of labelled simple closed curves and have been widely studied. The advent of 3D display and interaction mechanisms means that extending these diagrams to 3D is now feasible. However, 3D versions of these diagrams have not yet been examined. Here, we begin the investigation into 3D Euler diagrams by de ning them to comprise of labelled, orientable closed surfaces. As in 2D, these 3D Euler diagrams visually represent the set-theoretic notions of intersection, containment and disjointness. We extend the concept of wellformedness to the 3D case and compare it to wellformedness in the 2D case. In particular, we demonstrate that some data can be visualized with wellformed 3D diagrams that cannot be visualized with wellformed 2D diagrams. We also note that whilst there is only one topologically distinct embedding of wellformed Venn-3 in 2D, there are four such embeddings in 3D when the surfaces are topologically equivalent to spheres. Furthermore, we hypothesize that all data sets can be visualized with 3D Euler diagrams whereas this is not the case for 2D Euler diagrams, unless non-simple curves and/or duplicated labels are permitted. As this paper is the rst to consider 3D Venn and Euler diagrams, we include a set of open problems and conjectures to stimulate further research.
Euler diagrams represent intersection, containment and disjointness of sets. Currently, these diagrams are drawn in the plane and consist of labelled simple closed curves. These 2D Euler diagrams have been widely studied over the last few years and much progress has been made on their theoretical underpinning and techniques for automatically drawing them.
Here we introduce the concept of 3D Euler diagrams. We know of no other work de ning this type of 3D representation and, thus, this paper focusses on setting the groundwork for discussing this new diagrammatic type. Furthermore, it provides a platform to engage the community in discussion about the various issues in 3D Euler diagram research. 3D Euler diagrams consist of labelled orientable closed surfaces drawn in R3. An example of a 2D and a 3D Euler diagram representing the same information can be seen in gure 1. This 3D diagram, as well as all of the 3D Euler diagrams drawn in this paper, can be accessed from 3rd International Workshop on Euler Diagrams, July 2, 2012, Canterbury, UK. Copyright c 2012 for the individual papers by the papers' authors. Copying permitted for private and academic purposes. This volume is published and copyrighted by its editors. R
P
R
P
R www.eulerdiagrams.com/3D/workshop/. Using the freely available Autodesk Design Review software, one can rotate and explore the 3D diagrams.
We de ne 3D Venn diagrams as 3D Euler diagrams where all combinations of
surface intersections are present. An interesting comparison between 2D and 3D
is in the common Venn-3 case, i.e the Venn diagram representing exactly three
sets. It is known that there is only one topologically distinct embedding of
wellformed Venn-3 in 2D [
Whilst 3D Venn and Euler diagrams are interesting in their own right, we believe that there are also solid practical motivations for examining them. Firstly, the recent advances in hardware available for 3D display and interaction (eg. 3D televisions and Microsoft Kinect) support 3D visualization. As Venn and Euler diagrams form an important aspect of 2D visualization, it is reasonable to expect that they will also be important for 3D visualization.
Secondly, there are intrinsic bene ts to exploring 3D with respect to Euler
diagrams. When 2D Euler diagrams are de ned as consisting of (anything
equivalent to) simple closed curves without duplicated labels (for instance [
Wellformedness properties are a key aspect of drawing of Euler diagrams. In 2D, they relate to how the curves intersect and to the properties of the regions present. In 3D, we generalize them to how the surfaces intersect and the properties of the solids to which the surfaces give rise. The 2D Euler diagram on the left of gure 3 is not wellformed because it has a triple point of intersection between the curves. By contrast, the same data can be represented in a wellformed manner in 3D, as shown in the righthand side of gure 3; we will demonstrate, in section 4, that any way of drawing a 2D Euler diagram representing the same data breaks a wellformedness property. Often, there exists wellformed 3D Euler diagrams for data that has no wellformed 2D representation.
The remainder of this paper is as follows. Section 2 formally de nes 3D Euler diagrams and related concepts. Section 3 generalizes wellformedness properties of 2D Euler diagrams to the 3D context. Section 4 establishes that more data sets can be drawn wellformed with 3D Euler diagrams than with 2D Euler diagrams. We then go on to examine future work and propose open questions in section 5. Finally, section 6 concludes. 2
What is a 3D Euler Diagram?
3D Euler diagrams are formed from closed surfaces embedded in R3 rather than
closed curves embedded in R2. We refer the reader to [
In 2D Euler diagrams, zones are sets of points in the plane that are inside all curves in a given set and outside the rest of the curves in the diagram. In gure 1, both diagrams have ve zones. Zones are fundamentally important, since these correspond to the semantics of the diagram: between them, the present zones must represent all of the non-empty set intersections. We now generalize the notion of a zone to the 3D case: De nition 2. A zone in a 3D Euler diagram, d = (S; l), is a set of points, z, in R3 for which there exists a subset, S, of S such that 1. every point, pin , in z is inside all of the surfaces in S and outside all of the surfaces in S S, and 2. z is maximal with this property.
Such a zone, z, is described by des(z) = fl(s) : s 2 Sg. The set of zones in d is denoted Z(d).
In the visualization process, one starts with a description of the to-be-drawn diagram. A diagram description is a list of the set intersections that must be present in the diagram, given the sets to be visualized, thus precisely encapsulating the categories in which data items lie. For example, suppose we wish to visualize the sets P , Q, and R, and the intersections we wish to visualize are P \Q\R, Q\P \R, R\P \Q (i.e. the set intersections that comprise elements in exactly one of the three sets), along with P \ Q \ R, P \ R \ Q and Q \ R \ P (i.e. the set intersections that comprise elements that are in exactly two of the sets). Further, we also must visualize the set intersection that comprises elements in none of the three sets, namely P \ Q \ R. This is more succinctly represented as ;; P; Q; R; P Q; P R; QR, listing the non-complemented sets from each specied intersection, and is visualized by both diagrams in gure 3. More formally these diagrams have description f;; fP g; fQg; fRg; fP; Qg; fP; Rg; fQ; Rgg, but we will abuse notation as just illustrated.
De nition 3. A diagram description, D, is a subset of PL that includes ;. The description of a 3D Euler diagram, d = (S; l), is fdes(z) : z 2 Z(d)g:
The classic drawing problem, generalized to 3D, is given a diagram description, D, draw a 3D Euler diagram with description D. In 2D, this problem is often subject to a range of extra constraints that typically relate to the wellformedness properties. For instance, we may wish to nd a diagram that has no concurrency between surfaces. We generalize the wellformedness properties to 3D in the next section. 3
Wellformedness Properties of 3D Euler Diagrams
There are various wellformedness properties that can be applied to 2D Euler
diagrams [
First, consider the n-points properties. For the 2D case, a diagram is nonwellformed if it contains a triple point (i.e. a 3-point). The reason that the presence of 2-points does not render a diagram non-wellformed is because whenever two curves intersect, a 2-point is formed. However, given three curves that pairwise intersect it need not be the case that a 3-point is formed. Thus, 3-points are avoidable in 2D. However, 3-points are not avoidable in 3D. This is illustrated in gure 4. Here, three spheres intersect to form Venn-3. The cross-section of the diagram shown on the right of the gure illustrates that a three 3-point is formed.
Now consider now line concurrency. In 2D, diagrams that have two curves running concurrently along a line segment are not wellformed. However, in 3D, such a property is unavoidable: two surfaces that intersect and share common interior points necessarily share a common line segment. For instance, the Venn-3 diagram drawn with spheres on the left of gure 4 has line concurrency.
P
P Q
R Fig. 4. The necessity of 3-points in 3D.
Q R
n-point
P P R R R S P Q Q P
P Q
P R Q Q P R
Q R
P R
One of our key motivations for developing 3D Euler diagrams is that they allow more diagram descriptions to be drawn in a wellformed manner than is the case for 2D Euler diagrams. Recall that a 2D Euler diagram comprises a set of labelled simple closed curves such that no label is used on more than one curve. De nition 4. Let D be a diagram description. Then D can be drawn wellformed if there exists a Euler diagram with description D which satis es all of the wellformedness properties of table 1.
We now establish that every diagram description that can be drawn wellformed in 2D can be drawn wellformed in 3D. Our proof strategy is to convert a wellformed 2D diagram into a wellformed 3D diagram with the same description. To illustrate the approach, consider gure 5. Here, the wellformed 2D diagram is converted into a 3D diagram by rotating the 2D diagram around line that does not pass through any of the curves. Each resulting surface is a torus and the nal 3D diagram is shown on the right.
P R
Q
P R
Q
P R
Q Theorem 1. Let D be a diagram description. If D can be drawn wellformed in 2D then D can be drawn wellformed in 3D.
Proof (Sketch). Suppose that D can be drawn wellformed in 2D. Choose any wellformed 2D diagram, d2, with description D. Draw a line, , that does not pass through any curve in d2. Rotate d2 about by 2 to create a 3D Euler diagram, d3. Each closed curve, c2, in d2 gives rise to a torus, t3, in d3 and we label t3 the same as c2. It can be shown that each zone, z2, in d2 gives rise to a zone, z3, in d3 with the same description and that no other zones appear in d3. That is, the description of d3 is D. The wellformedness of d3 can be trivially established using the wellformedness of d2.
We now demonstrate that there are diagram descriptions that cannot be
drawn wellformed in 2D that can be drawn wellformed in 3D. Work by Flower
and Howse [
De nition 5. Given a diagram description, D, the super-dual of D is a graph, G = (V; E), where V = D is the set of vertices and, for every pair of vertices, v1 and v2, there is an edge between v1 and v2 if and only if v1 and v2 di er by a single label (recall elements of D, i.e. the vertices, are sets of labels).
Assuming we have a super-dual that is planar, we can draw that graph in the plane without edges crossing. Given such an embedding of the super-dual, we can attempt to form the required Euler diagram. An illustration of the process is given in gure 6. Here, we start with description ;; P; Q; P Q and turn it into the super-dual, shown on the left of gure 6. The curves of the 2D Euler diagram are constructed by enclosing the vertices appropriately. For example, to draw a curve labelled P we enclose the vertices that include P but no others. The curve labelled Q is similarly formed. Finally, we delete the super-dual and are left with the required 2D Euler diagram, shown on the right.
The preceding example is rather simple, but it is by examining the super-dual and, if necessary, its subgraphs that we can determine wellformed drawability in the 2D case. Now, the curves of a (wellformed) 2D Euler diagram are all simple which means that for each curve, c, the set of points inside c is a simply connected region. In terms of a super-dual, this implies that the maximal subgraph induced by the vertices that contain the label of c is connected and, moreover, that the subgraph induced by the vertices that do not contain the label of c is also connected. This key insight led Flower and Howse to de ne the connectivity conditions for graphs; these are used to establish properties of super-duals arising from diagram descriptions.
De nition 6 (Connectivity Conditions [
P
Q
P
Q P
PQ
Q
P
PQ
Q
Fig. 6. Constructing a 2D Euler diagram from the super-dual.
Theorem 2 (2D Connectivity Test [
The connectivity conditions are necessary for wellformed drawability in 3D: Theorem 3 (3D Connectivity Test). Let D be a diagram description whose super-dual fails connectivity conditions. Then there is no 3D Euler diagram, d, with description D that is wellformed.
Flower and Howse further introduce the face conditions, which we now
informally explain via an example; for full details we refer to [
P
PQ
PR
Q
R QR
Q
P
P
PQ
PR
Q
R QR
R
Q
P
R
P
Q
R Fig. 7. Failure of the face conditions.
For some diagram descriptions, but not the one just considered, it is possible
to remove edges from the super-dual whilst ensuring connectivity holds and
produce a subgraph, G, that has an embedding which passes the face conditions. A
further complication is the potential lack of planarity of the super-dual. Again,
we may be able to remove edges to create a planar subgraph G with the
properties just described. In either case, if such a G exists then D is drawable as a
wellformed 2D Euler diagram, otherwise it is not. This key result is captured in
the following theorem:
Theorem 4 (2D Drawability { Necessary and Su cient Conditions [
We can immediately generalize one side of this theorem to the 3D case: Theorem 5 (3D Drawability { Su cient Conditions). Let D be a diagram description with super-dual SG(D). If there exists a planar subgraph, G, of SG(D) obtained by removing edges from SG(D), which passes the connectivity conditions and has a plane embedding that passes the face conditions then there exists a wellformed 3D Euler diagram that is a drawing of D.
Proof. By theorem 4, a wellformed 2D Euler diagram exists. The result then follows from theorem 1.
We now demonstrate that there are diagram descriptions that are not drawable wellformed in 2D (they fail one of more of the conditions in theorem 4) but that are drawable wellformed in 3D. The three examples below fail the conditions of Theorem 4 in di erent ways. This shows that there are more diagram descriptions that can be drawn wellformed in 3D than 2D and that the conditions to determine drawability in 2D are not useful for determining drawability in the context of 3D diagrams. For these three examples, the wellformedness of the 3D representations suggests that they are more readable than the 2D representations and the 3D diagrams display a pleasing symmetry. Example 1: Figure 7 shows a planar super-dual that passes the connectivity conditions but fails the face conditions, so the corresponding 2D representation shown in gure 7 is not well-formed (it has a triple-point). All plane embeddings
R PQ RS QR P PS S PQ Q
PQ
R PQ RS QR P PS S PQ Q
PQ
P
R
R PQ S RS QR P PS S PQ Q
PQ
R
S Q P
Q
Q
R
P
S
Fig. 8. Failure of planarity of the super-dual.
PR
QR
PR
QR RT R RS
PQ
R T RT S R
RS PR QR P PPSTPTSTSTQT PQQ Q
of this graph fail the face conditions. Removing edges from this graph will never result in a graph that passes the connectivity and face conditions. Hence, there is no wellformed 2D Euler diagram with the given description. A wellformed 3D Euler diagram with this description can be seen in gure 7.
Example 2: Figure 8 shows a super-dual that is non-planar, since it is homeomorphic to K5;5, so some edge removal is necessary to achieve planarity. We demonstrate that any way in which edges can be removed to achieve planarity whilst maintaining connectivity does not produce a graph which passes the face conditions. If we remove an edge from the super-dual that is not incident to ; then we break the connectivity conditions. If we remove an edge which is incident to ; then the graph becomes planar and connectivity is preserved, so we then look for an embedding which passes the face conditions. However, any plane embedding of the graphs resulting from the removal of exactly one of these edges, shown here with the edge between ; and S removed, fails the face conditions. Continuing this kind of analysis, it can be demonstrated that there is no wellformed 2D Euler diagram with the given description. A wellformed 3D Euler diagram with the same description can be seen in gure 8.
Example 3: Figure 9 shows a super-dual that is non-planar, since it has a proper subgraph homeomorphic to K5;5, so again some edge removal is necessary to achieve planarity. However, all planar subgraphs fail the connectivity conditions. Take one edge as an example, say the edge between T and RT . This edge is in the maximal subgraph of the super-dual whose vertices include T . The removal of the T -RT edge would disconnect this subgraph, breaking connectivity. The same argument prevents removal of any edge not incident to ;. Thus, the only edges we can consider removing are those incident with ;. However, the subgraph obtained by removing the vertex ; is homeomorphic to K5;5. This implies that we cannot obtain a planar subgraph by removing edges from the super-dual whilst preserving connectivity. Hence, there is no wellformed 2D Euler diagram with the given description. A wellformed 3D Euler diagram with the same description can be seen in gure 9.
Thus, more diagram descriptions are drawable wellformed in 3D than in 2D. In particular, the face conditions need not be passed in order for us to have wellformed drawability in 3D and we need not have planarity of the dual.
There are numerous open questions in 3D. Following the previous section: Open Problem 1 What are necessary and su cient conditions for determining wellformed drawability in the 3D case?
We have demonstrated that the connectivity conditions are necessary, but there is no obvious generalization of the face conditions to the 3D case (the notion of a face does not translate to 3D graphs). We conjecture that a di erent approach is needed and it is very possible that this could provide a new perspective on wellformed drawability in the 2D case as well.
An important question is how the de nition of Euler diagrams needs to be relaxed in order to draw every diagram description. As discussed previously, in 2D we require either non-simple curves or duplicated label use. We believe that the de nition given in this paper for the 3D case is su cient for drawability in general, if we do not impose any wellformedness properties: Conjecture 1 For every diagram description there exists a 3D Euler diagram with that description.
We are con dent that this conjecture is true because we believe the following method for construction works in general. Given the diagram description D = f;; fP g; fQg; fP; Qg for each element, z, in D create one sphere for each label in z and draw them concurrently. For each pair of elements, z1 and z2, in D, if they share a non-empty set of labels, L = z1 \ z2, then join the spheres with labels in L arising from z1 and z2. This example can be seen in gure 10.
We focus now on a speci c class of Euler diagrams which is the widely known
family of Venn diagrams [
Four topologically distinct embeddings of Venn-3 are shown in the introduction, gure 2. To see that they are distinct, we make arguments about their zones. The rst (leftmost) Venn-3 has only simply connected zones. The second Venn-3 has exactly two zones that not simply connected, namely P and P R. The third Venn-3 has exactly two zones that are not simply connected, namely ; and R. The fourth (rightmost) Venn-3 also has exactly two zones that are not simply connected, namely QR and P QR. The four diagrams are pairwise topologically distinct because the non-simply connected zones are contained by di erent numbers of surfaces.
Conjecture 2 There are exactly four topologically distinct embeddings of wellformed 3D Venn-3 when the surfaces are all topologically equivalent to spheres.
A variety of other open problems can be stated for 3D Venn diagrams, some
of which have been answered for 2D Venn diagrams (see [
Returning to the more general case of Euler diagrams, there has been
considerable interest in drawing them with curves of particular shapes. For instance,
Stapleton et al. [
S
Q S P
R P
R
A nave method for converting a diagram drawn with circles into one drawn
with spheres is to use each circle to generate a sphere. However, this
construction approach need not lead to the required diagram description or preserve
wellformedness. This is demonstrated in gure 11: the leftmost Euler diagram is
drawn with circles, the 3D Euler diagram is obtained by converting the circles to
spheres and the remaining diagrams show cross-sections of the 3D Euler diagram.
Unfortunately, this created an extra zone, that inside only S and, moreover, this
zone is disconnected. We conjecture that there does not exist a wellformed 3D
diagram drawn with spheres with the same diagram description as gure 11.
However, we believe that some classes of diagram descriptions drawable
wellformed with circles can be drawn wellformed with spheres:
Conjecture 3 The class of inductively pierced descriptions, introduced in [
Finally, there has also been signi cant interest in drawing 2D Euler diagrams
in a so-called area-proportional manner. In the area-proportional 2D case, the
zones must have speci ed areas. Key publications on area-proportional Venn
and Euler diagram drawing include Chow and Rodgers [
De nition 8. A volume speci cation is a function, v: PL f;g ! R+ [ f0g. The diagram description induced by v is fz : v(z) 6= ; _ z = ;g: A 3D Euler diagram conforms to a volume speci cation, v, if its description is induced by v and its zones have the volumes speci ed by v.
Open Problem 5 What class of volume speci cations can be drawn in a wellformed manner? Open Problem 6 What class of volume speci cations can be drawn where the surfaces are all some speci ed shape? 6
In this paper we have introduced the concept of 3D Euler diagrams, formally de ning them as orientable closed surfaces which implies the surfaces are simple. We have compared them with 2D Euler diagrams and discovered that 3D Euler diagrams have some bene ts over 2D Euler diagrams in terms of drawability when wellformedness is considered. In particular, we have shown that there are more diagram descriptions that can be drawn wellformed with 3D diagrams than 2D diagrams and we conjecture that all diagram descriptions can be drawn in 3D without allowing non-simple surfaces and duplicate label use, unlike in 2D.
We established that there are four topologically distinct wellformed embeddings of 3D Venn-3, whereas there is only one such embedding in 2D. This demonstrates that there is more choice in terms of how we layout diagrams in 3D over 2D, which is likely to be bene cial when more sets need to be represented. This gives further insight into why more diagram descriptions can be drawn wellformed in 3D: we have greater control over which zones are topologically adjacent and topological adjacency impacts whether we can add a new surface (or curve in 2D) and maintain wellformedness.
By presenting a series of open questions and conjectures, we hope to stimulate research progress on 3D Euler diagrams. In some cases there is no obvious way to extend existing 2D results to the 3D case, such as Open Problem 1 concerning the drawability of wellformed diagrams. Hence, a di erent approach is likely to be required. It may be that results in the 3D case will allow more progress to be made in the 2D case.
With the advent of recent a ordable 3D display, interaction and printing devices, 3D visualization has the potential to be commonplace. We expect that 3D Euler diagrams will form a useful component in this eld.
Acknowledgement Gem Stapleton was partially supported by an Autodesk Education Grant.