# EulerMerge: Simplifying Euler Diagrams Through Set Merges

Xinyuan Yan, Peter Rodgers, Peter Rottmann, Daniel Archambault, Jan-Henrik
Haunert, Bei Wang Xinyuan Yan and Bei Wang are with the University of Utah.
E-mails<EMAIL_ADDRESS><EMAIL_ADDRESS>Peter Rodgers is with the
University of Kent.
E-mail<EMAIL_ADDRESS>Peter Rottmann and Jan-Henrik Haunert are with
the University of Bonn.
E-mails: {rottmann<EMAIL_ADDRESS>Daniel Archambault is with the
Newcastle University.
E-mail<EMAIL_ADDRESS>
###### Abstract

Euler diagrams are an intuitive and popular method to visualize set-based
data. In a Euler diagram, each set is represented as a closed curve, and set
intersections are shown by curve overlaps. However, Euler diagrams are not
visually scalable and automatic layout techniques struggle to display real-
world data sets in a comprehensible way. Prior state-of-the-art approaches can
embed Euler diagrams by splitting a closed curve into multiple curves so that
a set is represented by multiple disconnected enclosed areas. In addition,
these methods typically result in multiple curve segments being drawn
concurrently. Both of these features significantly impede understanding. In
this paper, we present a new and scalable method for embedding Euler diagrams
using set merges. Our approach simplifies the underlying data to ensure that
each set is represented by a single, connected enclosed area and that the
diagram is drawn without curve concurrency, leading to well formed and
understandable Euler diagrams.

###### Index Terms:

Euler diagrams, set visualization, hypergraph visualization, scalability

##  1 Introduction

Set-based data are found in many real-world examples. In personalized
recommendation systems, sets capture multivariate relationships among users,
query topics, items, and item features [1]. In machine learning, sets are used
to model higher order label relations in classification [2]. They are also
used in humanities to correlate text collections and the topics they discuss
[3]. Set-based data are prevalent in biological systems [4] to encode multiway
relationships among entities in protein complexes, transcription factor and
microRNA regulation networks, protein function annotations, and metabolic
processes [5].

An intuitive way to visualize set-based data is through a Euler diagram, which
captures sets and their relationships. In a Euler diagram, sets are
represented by closed curves that enclose regions. The way the regions overlap
reveals the intersections between the sets. Representing sets using a Euler
diagram is visually intuitive; however, these approaches can suffer from
comprehensibility issues even with a small number of sets, and scaling is
considered to be limited to 10 sets [6]. Finding a visualization of such data
is equivalent to finding a planar embedding of the dual graph of a Euler
diagram [7]. However, for many such data sets, no planar embedding exists. In
these cases, previous algorithms to embed Euler diagrams represent a set by
splitting it into two or more closed curves [8, 9], resulting in the set not
being represented by a single _connected enclosed area_. Performing this split
has the advantage that all instances of set systems are embeddable, but has
the disadvantage that the diagram is much harder to understand, as the same
curve can appear in different parts of the diagram.

In addition, these prior layout methods typically introduce _concurrency_ ,
where multiple curves share a line segment. Both concurrency and disconnected
enclosed areas are violations of important _wellformedness conditions_ , which
are known to impede understanding [10].

We present a new method that simplifies a Euler diagram via set merges, so
increasing the scalability of data that the method can successfully visualize
compared to previous methods. In a nutshell, a set merge takes the union of
two or more sets in a set system and represents the resulting set as a single
closed curve. Our contributions are as follows:

  * •

We produce a Euler diagram that satisfies a number of wellformedness
conditions. In particular, our simplification process is oriented to ensure
that each set (or merged group of sets) is represented by a single connected
enclosed area, and that there is no concurrency.

  * •

We demonstrate via experiments that, typically, a small number of set merges
leads to Euler diagrams that are well formed and understandable.

We structure this paper as follows: In Sec. 2, we give related work on set
visualization and set merging. In Sec. 3, we explain the technical background
to Euler diagram embedding. We explain the set merging algorithm in detail in
Sec. 4. In Sec. 5, we compare our method with the state-of-the-art general
Euler diagram embedding method. In Sec. 6, we give a number of examples to
demonstrate the advantages of the method. We conclude with future work in Sec.
7.

##  2 Related Work

The visualization of set-based data has been an active area of research; see
[11, 12] for surveys. In this paper, we focus on static (not dynamic) set
systems, and we use the words “set system” and “hypergraph” interchangeably
with the understanding that these terms arise from different research
communities. Hypergraphs generalize graphs by allowing edges that contain more
than two nodes, which are called hyperedges. Hence, a hyperedge is a set and a
hypergraph is a set system.

###  2.1 Euler and Venn Diagrams

Various methods for embedding a set system using closed curves have been
developed. These methods vary by the type of shape applied, and are often
restricted by the data to be visualized.

Circles and ovals only. Methods have been developed to constrain the types of
shapes used in the Euler diagram to circles [13, 14, 15] or ovals [16, 17]. In
these cases, the diagram is represented only using these shapes, creating much
simpler diagrams with smooth contours. However, only a subset of set systems
is considered in these cases so many input cases are not embeddable. In our
work, we try to create a general technique that can embed all instances of
Euler diagrams after simplification.

Polygons. Polygons with areas have been used to represent set systems that are
superimposed on top of the set elements [18, 19]. Bubble Sets [20] use
marching squares to create contour lines around sets of elements, visualizing
how these sets interact. GMap [21, 22] considers graphs and creates one or
more polygons around areas of the graph that are in the same set. MosaicSets
[23] use hexagonal or square grid cells to represent a set system. Although
the constrained hypergraph embedding problem is NP-complete, the authors of
MosaicSets provided a method based on integer linear programming to produce a
solution. In our work, we simplify a set system through set merges and then
try to visualize its Euler diagram in a conventional way.

General closed curves. Visualizing set systems with closed curves [24]
typically produces visualizations that are intuitive to read based on
perceptual principles [25, 26] and experimental evidence [27, 28, 29]. Mäkinen
[30] introduced an edge-based and a subset-based approach to draw hypergraphs,
where hyperedges are drawn as smooth curves _connecting_ or _enclosing_ their
nodes, respectively.

However, a Euler diagram is not embeddable for all set systems [9, 8] (with a
single closed curve representing each set) as dual graphs derived from these
set systems cannot be drawn in a planar way. Other methods, such as SPEULER
[31], instead arrange set elements using a circular layout. However, in order
to have an embeddable diagram, SPEULER produces overlaps of two curves when
there are no elements within them. In the work described in this paper, we
merge a pair of sets into a single curve while maintaining the curve in one
place in the diagram, so that every set is embeddable.

Euler diagram refinement. Techniques also exist to refine a Euler diagram
drawing once it has been generated, improving its readability. For instance,
eulerForce [32] uses a force-directed algorithm to refine the set, whereas
EulerSmooth [33] uses curve shortening flows to achieve the same objective.
Our approach uses EulerSmooth in order to refine the boundaries of a drawn
diagram.

###  2.2 Other Set Visualization Methods

Many techniques are variations and extensions of node-link diagrams, using
geometric elements such as lines, circles, ovals, polygons, and closed curves
to connect or enclose set elements. Other concepts using tables or matrices
have also been developed. We also discuss related simplification methods.

Lines. Some techniques represent the sets as lines connecting points. Linear
diagrams [34, 35] represent intersecting sets as line segments: wherever
segments overlap, the corresponding sets share elements. LineSets [36]
represent set memberships as lines and connect the elements of a set by a
smooth and short curve. MetroSets [37] use a metro map metaphor and connect
elements in a set on a line using a metro map layout. Kelp diagrams and their
variants [38, 39] construct minimum cost paths to connect set elements. The
work on untangling Euler diagrams [40] constructs a strict hierarchy on top of
the set system and uses edges to connect areas disconnected when this
hierarchy is constructed. Arafat et al. [41] encoded hypergraphs via
complete-, star-, cycle-, and wheel-associated-graphs. Paquette et al. [42]
used a bipartite graph where hyperedges form two independent sets. Radial Sets
[43] use a network representation. Pairwise overlaps are visualized as edges
and overlaps of degree $\geq 3$ are shown as hyperedges. Similarly, Kerren and
Jusufi [44] used a radial layout of nodes and hyperedges are arcs that enclose
them. These methods produce highly readable representations of set systems. In
this work, we aim to increase the scalability and readability of Euler
diagrams through set merging.

Graph and hypergraph simplification. A number of approaches have been proposed
that simplify and summarize graphs [45, 46, 47]. Visualization of the
simplified graphs has been extensively explored [48, 49, 50, 51, 52, 53, 54,
55, 56], which may be applicable to the node-link diagrams of set systems.
Whereas our approach is related to graph coarsening (e.g., aggregating
subgraphs into single nodes to reduce the number of nodes), the input data,
underlying methods, and the resultant visualizations are different.

The work of Zhou et al. [57] simplifies hypergraphs by allowing nodes be
combined if they belong to almost the same set of hyperedges, and hyperedges
to be merged if they share almost the same set of nodes. However, it is
different from the our work in the simplification criteria, algorithm, and
visualization perspectives. Our set merging strategy takes properties of the
resulting Euler diagram layout into consideration, whereas the approach in
[57] uses a simplification method that is agnostic to the resultant drawing.

Oliver et al. [58] recently proposed a framework for visualizing scalable
hypergraphs, with a convex polygon-based layout. Their approach incorporates
an iterative, reversible simplification process and layout optimization. They
have a number of merging operations, including hyperedge merging. As with [57]
the simplification criteria, underlying algorithms and resultant visualization
differ markedly. Whereas their method attempts to reduce the unwanted overlap
of the convex polygons representing hyperedges, our approach guarantees that
there are no unwanted overlaps for the curves representing sets.

Tables and matrices. A number of scalable techniques use tables or matrices.
Kritz and Perlin [59] proposed the QUAD scheme, which is a matrix-based
encoding of hypergraphs where each hyperedge is a column and each node is an
element along a particular row. Lamy [60] visualized undirected graphs as
symmetric square matrices by transforming them into overlapping sets, and
displayed them with a rainbow box visualization. UpSet [61] uses a tabular
encoding to visualize sets, their intersections, and their attributes. OnSet
[62] focuses on visualizing the individual elements of the set system.
Intersection and union of sets can be visualized interactively. Valdivia et
al. [63] introduced Parallel Aggregated Ordered Hypergraph (PAOH), which is a
hybrid of an edge-and-matrix-based approach for visualizing hypergraphs. The
main advantage of these methods is that they are very scalable both in terms
of the number of sets that can be visualized and the number of elements. In
this paper, however, we focus on the intuitive representation of Euler
diagrams and provide techniques to make them scalable.

##  3 Technical Background

We review technical notions relevant to Euler diagrams, such as abstract
description, dual graph, and well-formedness conditions. Many of these
definitions are adapted from Stapleton et al. [17]. We delay our discussion of
a set system and its relation to a Euler diagram to Sec. 4.

Figure 1: Left: a simple Euler diagram with a connected zone highlighted in
pink. Right: a Euler diagram with a disconnected zone in pink.

Euler diagrams and zones. A closed curve $\gamma$ in the plane
${\mathbb{R}}^{2}$ is a continuous function
$\gamma\colon[0,1]\to{\mathbb{R}}^{2}$, where $\gamma(0)=\gamma(1)$. An _Euler
diagram_ is a pair ${\mathcal{E}}=({\Gamma},\pi)$, where ${\Gamma}$ is a
finite set of closed curves in ${\mathbb{R}}^{2}$, $L$ is a set of labels, and
$\pi\colon{\Gamma}\to L$ is a mapping that assigns to each curve
$\gamma\in{\Gamma}$ a label in $L$. A _minimal region_ of a Euler diagram is a
connected component of
${\mathbb{R}}^{2}-\bigcup_{\gamma\in{\Gamma}}{\mathrm{image}}(\gamma)$. A
_zone_ of a Euler diagram is a set of minimal regions that represents the
intersection of sets. The set of zones is referred to as the _abstract
description_ of the diagram.

For example, Fig. 1 (left) is a Euler diagram where the label set
$L=\\{A,B,C\\}$ and each label represents a set in a set system. The pink
region is both a minimal region and a zone, which is formed from the
intersection of $A$ and $B$. A zone may contain more than one minimal region,
for example, the two pink minimal regions in Fig. 1 (right) form a single
zone, as a result of the intersection of $A$ and $B$ without $C$.

Figure 2: Left: a diagram with a nonsimple curve. Right: a diagram with a
triple point.

Wellformedness conditions. a Euler diagram ${\mathcal{E}}$ may have a number
of desirable properties, referred to as _wellformedness conditions_ :

  * •

Simplicity: if all curves in ${\Gamma}$ are simple curves. A curve is simple
if it does not cross itself.

  * •

No concurrency: if no pairs of curves in ${\Gamma}$ run concurrently.

  * •

No triple points: if there are no triple points of intersection among the
curves in ${\Gamma}$.

  * •

Transversality: if two curves in ${\Gamma}$ intersect, they intersect
transversally.

  * •

Connected zones: if each zone of ${\mathcal{E}}$ is connected.

  * •

Unique curve labels: if $\pi$ is an injective function.

Further discussions of such properties are available [64, 10]. We illustrate
these conditions with examples extending from Figs. 1-4 in [17]. As shown in
Fig. 2, the left diagram contains a nonsimple curve and the right diagram
contains a triple point. In Fig. 3, the left diagram violates the unique curve
labels condition whereas the right diagram contains concurrency and violates
the transversality condition.

Unique to this paper, we further refine the condition of unique curve labels
into two conditions:

  * •

Genus free: if the area enclosed by curves of the same label in $\Gamma$ does
not contain any genus (that is, a hole).

  * •

Connected enclosed area: if the area enclosed by curves of the same label in
$\Gamma$ is connected.

For example, in Fig. 4, both diagrams violate the genus free condition. In
Fig. 3 (left), the connected enclosed area condition is violated because the
curve “C” is split into two components.

Figure 3: Left: a diagram with duplicated curve labels. Right: a diagram with
multiple concurrent curve segments (referred to as partial concurrency)
involving curves A, C, and D; and A and B intersect nontransversally. Figure
4: Two diagrams violating the genus free condition.

Euler graph and dual graph. An _Euler graph_ $G_{{\mathcal{E}}}$ constructed
from a Euler diagram ${\mathcal{E}}$ has vertices defined at all curve
intersection points, and edges defined as the curve segments that connect the
vertices. See Fig. 5 (middle) for an example Euler graph. By construction,
each face of $G_{{\mathcal{E}}}$ is a minimal region of ${\mathcal{E}}$. The
_dual graph_ of a Euler diagram ${\mathcal{E}}$ is the standard dual graph of
the Euler graph $G_{{\mathcal{E}}}$. See Fig. 5 (right) for an example dual
graph. The vertices of the dual graph represent the zones in the Euler diagram
and the edges of the dual graph connect adjacent zones [65]. The vertices are
labeled by the curves that enclose their corresponding zones, and edges are
labeled by the symmetric difference of their endpoints.

Figure 5: A two set Euler diagram (left) with its corresponding Euler graph
(middle). Right: the Euler diagram with its dual graph.

Using our set merging approach, we produce a Euler diagram that satisfies the
above wellformedness conditions except for “no triple points”, “genus free”,
and “transversality”. There is evidence that triple points and transversality
have little impact on understanding [10]. We consider the main cause of poor
interpretation with nonunique curve labels to be caused by violations of
connected enclosed area rather than genus free. Having genus present in a
diagram means that curves with the same label are inside other curves with the
same label, whereas the presence of a disconnected enclosed area means that
the curves with the same label can be anywhere in the diagram, and therefore
users may not spot all such curves when interpreting the diagram. Our approach
is designed to ensure that the resulting Euler diagrams have simple curves and
connected zones. We then further simplify with set merges to ensure connected
enclosed areas and avoid concurrency.

##  4 Algorithm

In this section, we describe our novel algorithm for simplifying Euler
diagrams with set merging. We first introduce notations essential to our
algorithmic description in Sec. 4.1, extending the work in Sec. 3 to ensure
that the notations are suitable for the algorithmic context. We use a running
example in Sec. 4.2 to demonstrate how our approach produces a Euler diagram
from an input set system. We describe three key steps in our algorithm in Sec.
4.4, Sec. 4.5, and Sec. 4.6, respectively. We further utilize a prior work on
curve rendering to visualize a simplified Euler diagram in Sec. 4.7.

The code is available under a GPL open source license from
https://github.com/tdavislab/EulerMerge. We use JGraphT [66], which provides
an implementation of the Boyer-Myrvold planarity testing algorithm [67]. This
algorithm also provides a Kuratowski subdivision [68] of a nonplanar graph.

###  4.1 Algorithm Preliminaries

a Euler diagram is a visual representation of a set system. A _set system_ is
a set of sets ${\mathcal{S}}=\\{S_{1},S_{2},...,S_{m}\\}$, where each set
$S_{i}\in{\mathcal{S}}$ ($1\leq i\leq m$) is a nonempty subset of a universe
$U=\bigcup_{i=1}^{m}S_{i}$. With an abuse of notation, for an element $u\in
U$, ${\mathcal{S}}(u)$ contains sets from ${\mathcal{S}}$ that contain $u$,
i.e., ${\mathcal{S}}(u)=\\{S_{i}\in{\mathcal{S}}\mid u\in S_{i}\\}$. We assume
a set system is always given with a label-assigning map ${{l}}$ and
${{l}}(S_{i})$ is the label associated with the set $S_{i}$.

Our algorithm merges sets in ${\mathcal{S}}$ through an iterative process. In
each iteration, two sets are selected from ${\mathcal{S}}$ and replaced in
${\mathcal{S}}$ by their union. During this process, the algorithm maintains a
set of zones ${{Z}}$, which at any time is uniquely defined as follows:
${{Z}}$ contains the empty set $z_{0}:=\emptyset$ and multiple nonempty sets
$z_{1},z_{2},\ldots,z_{n}$ that partition $U$, such that any two elements
$u,v\in U$ are contained in the same zone if and only if
${\mathcal{S}}(u)={\mathcal{S}}(v)$. In other words, elements of $U$ are in
the same zone if they are contained in the same subset of sets from
${\mathcal{S}}$.

We work with a graphical representation $G$ of the set of zones. We design our
algorithm such that, preferably after few iterations, $G$ will be the dual
graph of a well formed Euler diagram of the simplified set system. Although,
initially, $G$ may lack the property of a dual graph of a wellformed Euler
diagram, for simplicity, we refer to it as _dual graph_ throughout the whole
merging process.

Let $G=({{Z}},E,{{l}}_{{{Z}}},{{l}}_{E})$. With an abuse of notation, the
vertices ${{Z}}$ represent the zones and the edges $E$ model pairwise
relationships among the zones, where ${{l}}_{{{Z}}}$ and ${{l}}_{E}$ are
(mappings of) zone labels and edge labels, respectively. The zone label
${{l}}_{{{Z}}}(z)$ of each $z\in{{Z}}$ is formed by a subset of
${\mathcal{S}}$ that constitutes the zone. The edge label ${{l}}_{E}(e)$ of
each edge $e=\\{z_{i},z_{j}\\}\in E$ is the symmetric difference of the two
zone labels, i.e.,
${{l}}_{E}(e):={{l}}_{{{Z}}}(z_{i})\triangle{{l}}_{{{Z}}}(z_{j})$ (c.f., Fig.
5 right). These labels are updated along with the set system as the algorithm
progresses. Recalling the abstract description of a Euler diagram in Sec. 3,
the set of zone labels is often referred to as the _abstract description_ of
the set system.

###  4.2 A Running Example

We illustrate the set merging process with a running example. This is a set
system ${\mathcal{S}}$ from a movie database; more details on our real-world
data sets can be found in Sec. 6. Each set represents a movie, and its
elements represent the actors that appear in the movie. Therefore in a Euler
diagram, curves represent movies, and the curves overlap if the movies share
at least one actor.

For the running example, the director is _Bonowicz, Brett Ryan_. He has seven
movies in the database, forming a set system of seven sets:

  1. (a)

Garriage: A Documentary in 4 Chapters and an Epilogue (2004); actors: Caps,
Bonowicz, Fox, Kessler, Kostenbaudor, Kozlow.

  2. (b)

Last Days of Ki, The (2005); actors: Herbst, Stilwell, Trad-DeStefano, Ashkin,
Bonowicz, Chai, Chernyak, Dixon, Harpole, Lindo, Peters, Sawyer, Suppa.

  3. (c)

Interview for a Night Job (2004); actors: Dastoli, James, Vergara, Edwin.

  4. (d)

Pressing the Public Opinion (2004); actors: DeVries, Yeager, Bonowicz,
Chernyak, Coolman, Lindo, Moore, Nelson.

  5. (e)

Baseball and Glory (2006); actors: Caffrey, Dienstag, Seabright, Shults,
Chernyak, Coolman, Dastoli, Denniberg, Garcia, Grant, Leery, Myers, Reiber,
Sawyer, Shields, Tompkins, Weinstein.

  6. (f)

Signs and Voices (2004); actors: Hecht, Moore, Shepherd, Bonowicz, Dean.

  7. (g)

Banana Shell, The (2005); actors: Baksh, Ashkin, Coolman, Fernandez, Grant,
Gunn, Sawyer, Zawacki, Niki.

Its corresponding abstract description (set of zone labels) can be produced by
finding the nonempty intersections in the set system. That is, if an actor
$u\in U$ is in a collection of movies ${\mathcal{S}}(u)$ (and no other
movies), ${\mathcal{S}}(u)$ is added to the abstract description:

$\displaystyle\\{\emptyset,\\{a\\},\\{b\\},\\{c\\},\\{d\\},\\{e\\},\\{f\\},\\{g\\},\\{b,d\\},\\{b,g\\},$
$\displaystyle\\{c,e\\},\\{e,g\\},\\{b,d,e\\},\\{b,e,g\\},\\{d,e,g\\},\\{a,b,d,f\\}\\}.$

For example, the actor _Dastoli_ is in movies “c” and “e”—“Interview for a
Night Job (2004)” and “Baseball and Glory (2006)”—and no other sets, which
gives rise to an element $\\{c,e\\}$ in the abstract description, and a zone
with a label of $\\{c,e\\}$ (for simplicity, also referred to as “ce”).

###  4.3 An Overview of EulerMerge Algorithm

Our set merging algorithm (Algorithm. 1) contains three key steps. First,
given an input set system ${\mathcal{S}}$ equipped with set labels, it forms
an initial dual graph (Algorithm. 2). Second, it selectively merges pairs of
sets in ${\mathcal{S}}$ to produce a planar dual graph which is used to embed
a Euler diagram (Algorithm. 4). Finally, it applies additional set merges to
remove concurrencies (Algorithm. 5). The final dual graph gives rise to a well
formed Euler diagram which can be visualized using existing methods (e.g.,
[31, 32, 17, 40]).

The input to our EulerMerge algorithm is a set system ${\mathcal{S}}$ equipped
with (a mapping of) set labels ${{l}}$, and the output is a dual graph of a
Euler diagram $G$ with zone labels ${{l}}_{Z}$ and edge labels ${{l}}_{E}$;
for simplicity, these labels are sometimes omitted in the pseudocode.

Input : Set system ${\mathcal{S}}=\\{S_{1},S_{2},\dots,S_{m}\\}$

Output : dual graph $G=(V,E)$

$G\leftarrow\mathrm{InitialDualGraph}({\mathcal{S}})$;

$G\leftarrow\mathrm{NonPlanarToPlanar}(G)$;

$G\leftarrow\mathrm{ConcurrencyRemoval}(G)$;

return _$G$_

Algorithm 1 EulerMerge

###  4.4 Forming the Initial Dual Graph

Algorithm. 2 creates an initial dual graph $G$ for an input set system
${\mathcal{S}}$. First, the algorithm derives the abstract description from
${\mathcal{S}}$ (Sec. 4.1) by creating zones and zone labels based on
computing ${\mathcal{S}}(u)$ for each $u\in U$. Second, it creates edges and
edge labels of $G$. Two zones $z_{i}$ and $z_{j}$ in $G$ are connected with an
edge if their zone labels differ by one, i.e.,
$|{{l}}_{{{Z}}}(z_{i})\triangle{{l}}_{{{Z}}}(z_{j})|=1$. Such edges are
desirable because they result in a single (nonconcurrent) curve segment being
drawn in the embedded Euler diagram. Third, the algorithm computes an induced
graph for each set $S_{i}\in{\mathcal{S}}$, denoted as
$H\leftarrow\mathrm{Induced}(G,S_{i})$, which connects the zones in $G$ whose
label contain ${{l}}(S_{i})$. If $H$ is connected, it means that there are no
duplicate curve labels in the corresponding Euler diagram. If $H$ is not
connected (i.e., the number of connected components
$|\mathrm{Components}(H)|>1$), the algorithm adds edges between connected
components of $H$ to ensure that it becomes connected. Specifically, it adds
edges to $H$ (and subsequently $G$) that connect zones with the smallest
symmetric differences via the procedure $\mathrm{Connect}(G,H)$. However, this
operation may introduce concurrency when the labels of the two connected zones
differ by more than one element.

Algorithm. 2 may produce an initial dual graph $G$ that does not correspond to
a well formed Euler diagram. First, there may not be a planar dual graph for
the initial set system. Second, the constructive process for initializing a
dual graph is heuristic and may not produce a planar dual even if one exists.
However, using a heuristic process is justifiable as deciding whether a given
set system can be drawn as a Euler diagram is NP-complete [69]. Additionally,
$G$ may not correspond to a well formed Euler diagram because the diagram will
have concurrent edges. The next step in Sec. 4.5 aims to derive a planar dual
graph. The step following it in Sec. 4.6 will remove concurrency.

Input : Set system ${\mathcal{S}}=\\{S_{1},S_{2},\dots,S_{m}\\}$

Output : dual graph $G=(Z,E)$

$Z\leftarrow\emptyset$, $E\leftarrow\emptyset$,
$U\leftarrow\bigcup_{i=1}^{m}{S_{i}}$

//Creating zones and zone labels

for  _$u\in U$_ do

$z\leftarrow\emptyset$, ${{l}}_{z}\leftarrow\emptyset$

for  _$S_{i}\in{\mathcal{S}}$_ do

if  _$u\in S_{i}$_ then

$z\leftarrow z\bigcup S_{i}$,
${{l}}_{z}\leftarrow{{l}}_{z}\bigcup{{l}}(S_{i})$

end if

end for

$Z\leftarrow Z\bigcup z$, ${{l}}_{Z}(z)\leftarrow{{l}}_{z}$

end for

//Creating edges and edge labels

for  _$z_{i},z_{j}\in Z$_ do

if  _$|z_{i}\triangle z_{j}|=1$_ then

$E\leftarrow E\bigcup e(z_{i},z_{j})$,
${{l}}_{E}(e)\leftarrow{{l}}_{Z}(z_{i})\triangle{{l}}_{Z}(z_{j})$

end if

end for

$G\leftarrow(Z,E)$

//Ensuring an $S_{i}$ induced subgraph is connected

for  _$S_{i}\in{\mathcal{S}}$_ do

$H\leftarrow\mathrm{Induced}(G,S_{i})$

while  _$|\mathrm{Components}(H)| >1$_ do

$H\leftarrow\mathrm{Connect}(G,H)$

end while

end for

return _$G$_ ;

Algorithm 2 InitialDualGraph

For the running example, the initial dual graph formed from Algorithm. 2 can
be seen in Fig. 6(a). The vertices are formed from zones of the abstract
description. The zone labels are given as the concatenation of letters to more
easily fit on the circles. The zone representing $\emptyset$ is shown without
a label. The zones that have labels with single symmetric difference are
connected by edges. For example, “b” and “bd” are connected by an edge.
However, this operation might leave the subgraph induced from the set “a”
disconnected, thus resulting in a Euler diagram with “a” having a disconnected
enclosed area, hence the algorithm (via the $\mathrm{Connect}$ procedure)
links “a” and “abdf” with an edge. Another edge between “d” and “deg” is added
for the same reason for the induced graph from the set “d”. This dual graph is
nonplanar and does not give rise to a well formed Euler diagram. The set
merges from Sec. 4.5 are used to produce a planar dual graph.

###  4.5 Set Merging for Planarity

We apply a pairwise set merging process in Algorithm. 3 once we have obtained
an initial dual graph $G$. $G$ may not be planar, so our first priority is to
merge sets in the dual graph so that it becomes planar. We can then embed a
Euler diagram once $G$ has a planar layout.

As shown in Algorithm. 3, to merge a pair of sets $S_{1}$ and $S_{2}$, we
first replace any zone label and edge label containing ${{l}}(S_{2})$ with
${{l}}(S_{1})$. We then merge zones in the dual graph with identical labels.

Input : dual graph $G=(Z,E)$, Sets $S_{1}$ and $S_{2}$

Output : dual graph $G^{\prime}=(Z^{\prime},E^{\prime})$

$G^{\prime}\leftarrow G$;

//Replacing ${{l}}(S_{2})$ with ${{l}}(S_{1})$ in zone labels

for  _$z\in Z^{\prime}$_ do

if  _${{l}}(S_{2})\in{{l}}^{\prime}_{Z}(z)$_ then

${{l}}^{\prime}_{Z}(z)\leftarrow{{l}}^{\prime}_{Z}(z)\cup{{l}}(S_{1})\setminus{{l}}(S_{2})$

end if

end for

//Replacing ${{l}}(S_{2})$ with ${{l}}(S_{1})$ in edge labels

for  _$e\in E^{\prime}$_ do

if  _${{l}}(S_{2})\in{{l}}^{\prime}_{E}(e)$_ then

${{l}}^{\prime}_{E}(e)\leftarrow{{l}}^{\prime}_{E}(e)\cup{{l}}(S_{1})\setminus{{l}}(S_{2})$

end if

end for

//Merge zones with identical labels

for  _$z,z^{\prime}\in Z^{\prime}$_ do

if  _${{l}}^{\prime}_{Z}(z)={{l}}^{\prime}_{Z}(z^{\prime})$_ then

$G^{\prime}\leftarrow\mathrm{ZoneMerge}(G^{\prime},z,z^{\prime})$

end if

end for

return _$G^{\prime}$_ ;

Algorithm 3 PairwiseSetMerge

We can now describe two methods for deciding which sets to merge. The first is
to merge sets to form a planar dual graph using Algorithm. 4. We prioritize
the planarity objective over concurrency removal because we cannot embed a
Euler diagram without a planar dual. Furthermore, we can move toward planarity
and reduce concurrency simultaneously during this process.

Recall that a subdivision of a graph is a graph resulting from the subdivision
of its edges. Every nonplanar graph contains a Kuratowski subdivision [68]
(i.e., a subdivision of $K_{5}$ or $K_{3,3}$) as a subgraph. Moreover, for a
given nonplanar graph, such a subgraph can be found in linear time [67]. We
refer to such a subgraph as a _Kuratowski subgraph_ , denoted as $G^{K}$. As
shown in Algorithm. 3, we merge two sets present in such a subgraph until $G$
becomes planar.

Although achieving planarity is our top priority, we decide on the order of
pairwise set merges based on the reduction of concurrency because the two sets
are in a Kuratowski subdivision and merging them very likely also removes the
subdivision. In a limited number of cases (for instance, when the sets to be
merged are both in exactly the same zones), the subdivision remains, whereas
concurrency is greatly reduced by the set merges and so the second aim of the
merging process is satisfied.

We introduce a measure that quantifies the amount of concurrency in a dual
graph:

$\mathrm{Concurrency}(G)=\sum_{e\in E}|{{l}}_{E}(e)|-|E|.$

Recall that multiple sets that appear on an edge label give rise to concurrent
curve segments. $\mathrm{Concurrency}(G)$ measures the overall size of edge
labels. $\mathrm{Concurrency}(G)=0$ means that $G$ has no concurrency as all
edges are labeled with a single set. In Algorithm. 3, we merge two sets (whose
labels appear in $G^{K}$) that cause the most reduction in concurrency.

Input : dual graph $G=(Z,E)$

Output : dual graph $G^{\prime}=(Z^{\prime},E^{\prime})$

$G^{\prime}\leftarrow G$

while  _$!\mathrm{IsPlanar}(G^{\prime})$_ do

//Finding a Kuratowski subgraph in $G^{\prime}$

$G^{K}=(Z^{K},E^{K})\leftarrow\mathrm{KuratowskiSubdivision}(G^{\prime})$

//Collect the set of zone labels from $G^{K}$

$R\leftarrow\bigcup_{z\in Z}{{{l}}^{K}_{{{Z}}}(z)}$;

//Perform pairwise set merges with the largest reduction on concurrency

$G^{M}\leftarrow G^{\prime}$;

for  _$R_{i}\in R$_ do

for  _$R_{j}\in R$_ do

$G^{S}\leftarrow\mathrm{PairwiseSetMerge}(G^{\prime},R_{i},R_{j})$;

if  _$\mathrm{Concurrency}(G^{S}) <\mathrm{Concurrency}(G^{M})$_ then

$G^{M}\leftarrow G^{S}$;

end if

end for

end for

$G^{\prime}\leftarrow G^{M}$;

end while

return _$G^{\prime}$_

Algorithm 4 NonplanarToPlanar

In our running example, the initial dual graph is nonplanar and so we must
apply Algorithm. 4. In this case, we only need a single iteration as merging
sets “b” and “d” results in a planar dual, shown in Fig. 6(b). We use the set
label with the lowest lexicographical order during set merges. Here, merging
“b” and “d” (i.e., replacing “d” with “b”) leads to a merged set labeled as
“b”.

Figure 6: The merging process illustrated for a movie dataset for director:
Bonowicz, Brett Ryan. (a) The initial dual graph. (b) The first planar dual
graph after merging sets “a” and “d”. (c) The dual graph and first Euler
diagram without smoothing. (d) The first Euler diagram with smoothing. (e) The
dual graph and final Euler diagram after merging sets “a” and “b”. (f) The
final Euler diagram with set labels.

Set merges also lead to reduced concurrency. The dual graph in Fig. 6(a) has a
$\mathrm{Concurrency}$ of 6, whereas the dual graph in Fig. 6(b) has a
$\mathrm{Concurrency}$ of 2. For instance, concurrency was present because
zone “d” is connected to zone “deg”. Merging sets “b” and “d” leads to the
merging of zones “beg” and “deg”, thus removing the above concurrency. Once
the dual graph becomes planar, it can be used to embed a well formed Euler
diagram. The resultant embedding is shown in Fig. 6(c) and with improved
layout in Fig. 6(d). Details of the rendering process are described in Sec.
4.7.

###  4.6 Set Merging to Remove Concurrency

With a planar dual graph, we can apply additional set merges to remove the
remaining concurrency, see Algorithm. 5. We focus on our concurrency-removal
priority using a greedy approach, that is, by merging pairs of sets that
reduce the most amount of concurrency. We note that alternative strategies for
ordering pairwise set merges are also possible, as discussed in Sec. 7. The
final if statement, which ensures planarity by calling Algorithm. 4, is for
rare cases where nonplanar duals can be produced by set merging. No examples
where this has been called are present in the data in this paper.

Input : dual graph $G=(V,E)$

Output : dual graph $G^{\prime}=(V^{\prime},E^{\prime})$

$G^{\prime}\leftarrow G$

while  _$\mathrm{Concurrency}(G^{\prime}) >0$_ do

//Collect the set of zone labels

$R\leftarrow\bigcup_{z\in Z^{\prime}}{{{l}}_{{{Z}}^{\prime}}(z)}$;

$G^{M}\leftarrow G^{\prime}$;

for  _$R_{i}\in R$_ do

for  _$R_{j}\in R$_ do

$G^{S}\leftarrow\mathrm{PairwiseSetMerge}(G^{\prime},R_{i},R_{j})$;

if  _$\mathrm{Concurrency}(G^{S}) <\mathrm{Concurrency}(G^{M})$_ then

$G^{M}\leftarrow G^{S}$;

end if

end for

end for

$G^{\prime}\leftarrow G^{M}$;

end while

if  _ $!\mathrm{IsPlanar}(G^{\prime})$_ then

$G^{\prime}\leftarrow\mathrm{NonPlanarToPlanar}(G^{\prime})$

end if

return _$G^{\prime}$_

Algorithm 5 ConcurrencyRemoval

In the running example, the dual graph in Fig. 6(c) still contains
concurrency, e.g., between the connected zones “a” and “abf”, as the Euler
diagram curve segments “b” (orange) and “f” (yellow) run concurrently when
crossing the edge between “a” and “abf”. To remove all concurrency in this
case, we need only a single iteration by merging sets “a” and “b”, shown in
Fig. 6(e). In the Euler diagram where zone “a” was connected to zone “abf”,
“abf” is renamed as “af” with a single symmetric difference with “a”. As a
result of this merge no concurrency remains and so the merging process is
complete. The final Euler diagram with the movie names from the input is given
in Fig. 6(f). Here, one curve represents the merging of three movies. We have
now simplified the abstract representation and the Euler diagram, at the cost
of losing some details in the data set.

###  4.7 Rendering the Euler Diagram

We now explain how to draw a Euler diagram from the simplified dual graph and
how to visually improve the Euler diagram via smoothing. In particular, we
apply known algorithms for embedding the dual graph [8], followed by smoothing
using EulerSmooth [33] to refine the diagram boundaries.

The output dual graph from the $\mathrm{EulerMerge}$ algorithm (Algorithm. 1)
gives rise to a planar dual from which a Euler diagram without concurrency can
be embedded. We find a planar embedding for the dual graph, followed by a
process to create the curves. Here, the zones containing the same set label
are surrounded with a curve.

We first generate a planar layout of the dual. The vertex representing the
empty zone is positioned on the outside face. Planar layout algorithms often
produce layouts with closely spaced vertices and poor angular resolution.
Hence, we apply an edge crossing preserving force directed layout algorithm
[8]. Following a standard force directed layout using node repulsion and edge
attraction, we use an additional force to prevent edge crossings.

We then apply a general Euler diagram embedding algorithm [8]. As noted in
Sec. 4.1, the edges of the dual graph are labeled with the symmetric
difference of the zone labels. We route the curves of the Euler diagram so
that curves cross edges with the curve label. When rendering early examples of
dual graphs, before Algorithm. 5 is completed, when multiple curves cross an
edge, the curves become concurrent (i.e., they share a line segment). As shown
Fig. 6(c), the edge connecting zone “a” and zone “abf” (with an edge label of
“bf”) corresponds to curves “b” and “f” runnning concurrently when crossing
the edge.

Finally, EulerSmooth [33] refines the boundaries of sets in the diagram. It
can be applied to any planar dual graph and uses curve-shortening flow to
create smooth boundaries while retaining the structure of the diagram. No
zones are created or destroyed by the refinement process, which allows the
final diagrams to be rendered with smooth boundaries, increasing their
readability.

For the running example, we illustrate the rendering process by showing the
dual graph and the resultant Euler diagram during intermediate and final
steps. Fig. 6(c) shows the diagram after applying the embedding process from
[8], whereas Fig. 6(d) shows the curves after EulerSmooth [33]. All remaining
examples in this paper show Euler diagrams with EulerSmooth applied.

Finally, we compare against the prior state-of-the-art general Euler diagram
embedding [8], which we refer to as EulerGeneral. As shown in Fig. 7,
EulerGeneral produces a Euler diagram where sets “a” and “f” are represented
by disconnected enclosed areas with a $\mathrm{Concurrency}$ of 5.

Figure 7: a Euler diagram of the running example using the prior state-of-the-
art [8].

.

##  5 Evaluation

We compare our EulerMerge algorithm with the state-of-the-art general
embedding algorithm of Rodgers et al. [8] (referred to as EulerGeneral). Our
algorithm produces Euler diagrams that are well formed with _connected
enclosed areas_ and _no concurrency_ (see Sec. 3). It explicitly reduces the
number of sets (and zones) to be visualized. The EulerGeneral algorithm [8]
visualizes all sets (and zones) at the cost of violating the above well-
formedness conditions, where multiple curves may represent a given set in
different parts of the diagram, and more than one curve may follow the same
path.

On the other hand, both algorithms produce diagrams that meet the well-
formedness conditions of _simplicity_ and _connected zones_ by construction.
Neither meet the conditions of _transversality_ , _triple points_ , or _genus
free_. In both algorithms, _transversality_ is an artifact of the embedding
process where two curves that do not intersect are embedded in nontransverse
positions (i.e., they are shown to touch each other). Empirical results have
focused on removing disconnected curve labels and concurrency (rather than
triple points or transversality) because of their greater negative impact on
usability [10]. Furthermore, we consider _connected enclosed area_ to be a
more critical well-formedness condition than _genus free_. A violation of the
former separates regions representing the same set into different areas
throughout the diagram, whereas a violation of the latter creates holes/genera
in the diagram. We consider the latter case less confusing as curves with the
same label are nested and so contained in the same area of the diagram.
However, we give an example in Sec. 6 to show how our algorithm may be
extended to produce genus free diagrams.

We now compare the compromises that must be made when visualizing Euler
diagrams using both algorithms. We discuss the properties of the resulting
Euler diagrams followed by direct visual comparisons in Sec. 6. Our EulerMerge
algorithm produces a well formed diagram at the cost of set merges. We need to
consider the number of set merges required to produce a planar dual graph as
well as those required to remove the remaining concurrency. We therefore count
the number of set merging operations in Algorithm. 4 and Algorithm. 5. Using
EulerGeneral, we may not obtain a well formed diagram as duplicated curve
labels and concurrency appear in many cases. Hence we quantify the number of
duplicated curve labels as well as the amount of concurrency in the diagram.

We use two collections of real-world set systems for evaluation (Tab. I).
First, the MovieDB collection comes from the 2007 InfoVis contest [70]. A set
system from this collection focuses on the movies directed by a single
director, i.e., each set is a movie containing actors that appear in the
movie. Second, a set system from the Twitter Circles [71] collection contains
interests groups formed by Twitter users. For illustration purposes, we
include only diagrams that contain duplicated curve labels or concurrency.

Collection | #Set Systems | Mean #Sets | Mean #Zones
---|---|---|---
MovieDB | 225 | 4.4 | 7.78
Twitter Circles | 59 | 5.92 | 8.24
TABLE I: Real-world data summary with the number of set systems (#Set
Systems), and the average numbers of sets and zones (Mean #Sets and Mean
#Zones), respectively.

Using EulerMerge, we report in Tab. II the average number of set merges
required to produce a planar dual graph as well as those required to remove
the remaining concurrency. The average number of set merges is approximately
$\leq 2$, whereas concurrency reduction is over ten times more common than
planarity reduction for both collections.

Collection | #Planarity | #Concurrency | Total #Merges
---|---|---|---
MovieDB | 0.11 | 1.23 | 1.33
Twitter Circles | 0.07 | 1.97 | 2.04
TABLE II: With EulerMerge, the average number of set merges for achieving
planarity (#Planarity) and removing the remaining concurrency (#Concurrency),
together with the total number of merges (Total #Merges).

Using EulerGeneral, we report in Tab. III the average number of duplicated
curves and the average $\mathrm{Concurrency}$ count. The duplicated curve
labels occur is less than half of the diagrams generated, which may be
artificially reduced by the failure of the algorithm to visualize some set
systems, particularly complex ones.

Collection | #Duplicated Curve Labels | $\mathrm{Concurrency}$
---|---|---
MovieDB | 0.35 | 4.63
Twitter Circles | 0.41 | 6.19
TABLE III: With EulerGeneral, the average number of duplicated curve labels
(#Duplicated curve labels) and the average $\mathrm{Concurrency}$ count.

Fig. 8 compares EulerMerge with EulerGeneral by contrasting the number of set
merges needed to achieve a planar dual graph against (in EulerMerge) the
number of duplicated curve labels representing the same set (in EulerGeneral).
These numbers are broadly comparable, as the previous system removed edges
from the dual graph to achieve planarity. This removal has the effect of
requiring multiple curves to visualize a single set. As can be seen, the
maximum number of merges required to achieve planarity is 3, whereas the
maximum number of duplicated curve labels is 13 (both at the same example data
point). In general, Fig. 8, Tab. II, and Tab. III indicate that EulerMerge
requires a smaller number of set merges to achieve planarity thus avoiding
disconnected areas, compared to the number of disconnected areas created using
EulerGeneral (when merging is not applied).

Figure 8: The number of merges required to achieve planarity in EulerMerge
against the number of duplicated curve labels in EulerGeneral. The size of a
circle is proportional to the number of data items. Figure 9: Total number of
merges required to remove concurrency in EulerMerge (merges for achieving
planarity and merges for removing remaining concurrency) against the
concurrency count in EulerGeneral. The size of a circle is proportional to the
number of data items.

Fig. 9 compares EulerMerge against EulerGeneral by contrasting the number of
set merges required to remove concurrency (with EulerMerge) against the number
of concurrent curve segments required for visualizing the same data set (with
EulerGeneral). The number of merges counts the set merging operations used to
achieve planarity and remove concurrency after planarity is achieved. Both the
planarity merges and concurrency merges help reduce concurrency. As can be
seen, the maximum value for the two measures occurs in different data points,
with the maximum number of merges being 11 and the maximum concurrency count
being 53. The scatter plot in Fig. 9 and the summary in Tab. II and Tab. III
show that a smaller number of set merges are required to remove concurrency
with EulerMerge, compared to the amount of concurrency required in
EulerGeneral when merging is not applied.

##  6 Results

Here we show the results of our method when applied to examples taken from
real world data sets, including the Twitter and Movie data detailed in Sec. 5.

###  6.1 Twitter Data Example

Figure 10: The set merging process of a Twitter data set. (a) The original
dual graph. (b) The first planar dual graph (left) and its corresponding Euler
diagram (right) with concurrency. (c) From left to right: sets “a” and “f”
merge into “a”. (d) The final Euler diagram without concurrency.

Fig. 10 illustrates the process of applying our method to an example group of
users from the Twitter data, which comprises 13 interest groups, where each
user may belong to multiple groups. We represent the data as a set system
consisting of 13 sets with the names of sets shortened to single letters: “a”,
“b”, …, “k”. The 32 intersections of these sets represent groups of users with
shared interests.

To visualize this data as a Euler diagram with our algorithm, we first
construct a dual graph, as shown in Fig. 10(a). In this graph, vertices
represent zones, namely, the 32 nonempty intersections of sets. Edges are
created using Algorithm. 2 with the goal of minimizing concurrency as well as
keeping each set connected. However, the initial dual graph is nonplanar and,
thus, it is not possible to generate a Euler diagram from it. We therefore
employ Algorithm. 4 to merge sets until the graph can be embedded without edge
crossings. The first iteration merges sets “d” and “k”. The merged set is
labelled “d”. A second merge is required before reaching planarity, so “d” and
“g” are merged. Again the label of the shared set is “d”. The two merges
produce a planar dual graph with 11 sets and 21 intersections, see Fig. 10(b).
However, the result exhibits concurrency. For example, the edge connecting
vertices “f” and “dfm” in the dual graph differs by two sets and so there is a
concurrent curve segment in the Euler graph (the curves “d” and “m” share the
line segment). To eliminate concurrency, we continue to merge sets using
Algorithm. 5, which merges “a” and “f” resulting in a new set labelled “a”, as
shown in Fig. 10(c). The resulting Euler diagram has no concurrency. At the
same time, it has other issues regarding well-formedness, i.e., it contains a
triple point (towards the top right) and nontransversal intersecting
(touching) curves (e.g., curves “h” and “l”). However, this example
demonstrates that EulerMerge has achieved a desirable Euler diagram: after
three set merges, two for planarity and one for concurrency, we can visualize
this Twitter data set as a Euler diagram with connected enclosed areas and
without concurrency, see Fig. 10(d). This final diagram also lists the
original set names.

###  6.2 Movie Data Example (Director: Hooker, Keith)

Figure 11: The set merging process of a movie data set involving the director
Hooker, Keith. (a) The initial dual graph. (b) Planarity merges: merging sets
“a” and “c” into “a” and then merging “a” and “b” into “a”. (c) Concurrency
merges: merging “a” and “b” in to “a”. (d) The final diagram with the original
set names.

This data set consists of five sets in total. Each set represents a movie (“a”
= Animal Attraction (2004); “b” = Not Without My Hitler (2004); “c” = Aliens
Among Us (2004); “d” = The Return of Dr. Rod (2005), and “e” = The Other Side
of the Glass (2006)). We show set intersections where one or more actor
appears in those films and no other films. As shown in Fig. 11(a), the initial
dual graph is not planar. The simplification process merges once for planarity
(sets “a” and “c” merge into “a”) and merges once for concurrency removal
(sets “a” and “b” merge into “a”). Fig. 11(b) left shows the first planar dual
graph. Fig. 11(b) right shows the corresponding Euler diagram, which exhibits
concurrency. Fig. 11(c) shows the concurrency removal step, where sets “a” and
“b” in the left Euler diagram merge into “a” in the right Euler diagram. Fig.
11(d) gives the final Euler diagram with the original set names.

###  6.3 Southern Women Example

Figure 12: The merging history of Southern Women data set. Grey areas
represent the genera (holes). (a) The original dual graph. (b) The first
planar dual graph after merging sets “g” and “i”. (c) Left: the first Euler
diagram; right: four sets that contain holes. In the second merge of the
concurrency removal process, sets “f” and “h” in (d) merge into set “f” in
(e). The Euler diagram without concurrency is shown in (f). A manual process
identifies a merging of sets “a” and “b” into “a” to produce a genus-free
Euler diagram in (g). Figure 13: The Euler diagram of the Southern Women
dataset after simplification.

In this example, we showcase our algorithm with the Southern Women data set.
It characterizes 14 informal social events among 18 women over a period of
nine months in the 1930s in Natchez, Mississippi. It was collected by
ethnographers, and has been thoroughly analyzed in [72]. To visualize the
participation of each social event, we first transform this data into a set
system with 14 events as sets, denoted by “a”, “b”, …, “n”, and visualize the
combinations of events with one or more participants.

We first construct a dual graph from the set system using Algorithm. 2 as
shown in Fig. 12(a). We are unable to derive a Euler diagram due to its
nonplanarity. Thus, set merges based on Algorithm. 4 are used to achieve a
planar dual graph. As shown in Fig. 12(b), merging sets “g” and “i” into “g”
results in a planar dual graph, from which a Euler diagram can be embedded;
see Fig. 12(c). However, the Euler diagram still contains concurrency.

Next, we utilize Algorithm. 5 to iteratively merge sets to remove concurrency.
The Euler diagram is concurrency-free after the following 4 iterations: sets
“f” and “g” merging into “f”, sets “f” and “h” merging into “f”, sets “f” and
“k” merging into “f”, and sets “f” and “m” merging into “f”. The resulting
Euler Diagram is depicted in Fig. 12(f).

In addition, using this example, we demonstrate that our framework may be
extended to enable the removal of genera (holes) in Euler diagrams. As noted
previously, genus-free is a well-formedness condition. However, since genera
are typically easy to identify in a Euler diagram embedding, achieving a
genus-free diagram has not been considered as a priority in our current
algorithm given in Sec. 4.

If we are interested in enforcing a genus-free condition, genera removal might
follow a similar process to concurrency removal. We would first quantify
genera in the dual graph: a set with label “s” has a genus $>0$, if removing
the vertices (and connecting edges) with labels containing “s” leads to a
disconnected graph. A genus is formed from subgraphs without an outside
vertex, where its inner curves are routed to surround the vertices in the
subgraph. If we are left with $g$ connected subgraphs after such vertex
removals, the diagram has a genus of $g-1$. A measure of genus separation
between subgraphs $G_{1}$ and $G_{2}$ is the minimum semantic distance between
a vertex in $G_{1}$ and a vertex in $G_{2}$, minus 1. We can use this to
measure the genus separation of a single set, and then sum the measure for all
sets in the diagram to calculate the genus separation of the diagram.
Informally, the genus separation for a set “s” is the sum of minimum semantic
distances between a collection of pairs of such subgraphs induced from the set
such that the collection of pairs include each such subgraph induced from “s”
(e.g., $G_{1},…,G_{i}$).

It is then possible to test the merge of each pair of sets in the dual graph,
and the set merge that reduces this measure the most would be applied. Note we
cannot just count the number of genera before and after merging, because there
may be no set merge that reduces the number of genera in a single step.

Fig. 12(f) has a genus in set “d”. To reduce genera according to the above
proposed procedure, we proceed by merging sets “a” and “b” into “a”. We have
identified such a merge that maximally reduces the genus separation in the
diagram (e.g., from 1 to 0). The final diagram after merging for planarity,
concurrency-free, and genus-free is shown in Fig. 12(g) and Fig. 13,
respectively. In Fig. 12, gray areas highlight the genera in the diagram, and
to avoid confusion, each set in the final diagram is visualized by a colored
curve. In Fig. 13, each set in the final diagram is visualized by a colored
enclosing area.

##  7 Discussion and Future Work

This paper provides, for the first time, an algorithm that uses set merges to
simplify the layout of Euler diagrams to meet multiple well-formedness
conditions. Previous Euler diagram visualization frequently violates the well-
formedness conditions by producing diagrams with disconnected enclosed areas
and/or concurrency, which significantly impedes understanding [10]. Merging
just a few sets (often 3 or less) using EulerMerge results in a diagram
without split sets or concurrency, thus producing a simplified diagram that is
easier to comprehend than the none-well-formed alternative.

Merging two sets into one reduces the amount of detail available to the user
and so may be seen as a disadvantage. However, we see the simplification of a
complex set system/Euler diagram as a potential benefit, since the
visualization of over 10 sets using a Euler diagram is generally considered
infeasible [6]. If needed, with the integration of a suitable user interface,
the accepted visualization approach of “overview first, zoom and filter then
details-on-demand” [73] can be employed to reveal the missing details due to
the simplification process.

In terms of further work, it may be possible to consider zone merges instead
of set merges to obtain finer control over the layout of the diagram.
Different criteria for set merging may be considered. For instance, merging
two closely related sets, may be measured by transportation costs or similar
metrics. Additional wellformedness conditions could also be considered during
set merging, such as _genus free_ (discussed in Sec. 6) and _no triple
points_. It would be interesting to investigate whether merging sets always
reduces genera and/or maintains a genus-free diagram when the diagram is genus
free beforehand. Although there is evidence to show that triple points are
less cognitively problematic than concurrency or separated regions [10], we
could also apply a measure of triple points (for instance, derived from face
conditions [7]) and apply merging to reduce triple points. However, including
extra measures would increase the complexity of the algorithm. In particular,
reducing one well-formedness condition may increase another, hence a more
sophisticated means of integrating these potentially competing measures would
be required.

## Acknowledgments

We would like to thank Dagstuhl Seminar 22462 “Set Visualization and
Uncertainty” (November 13-18, 2022) for initializing this working group. We
would also like to thank Martin Nöllenburg for discussions on planarity. BW
was partially supported by DOE DE-SC0021015. For the purpose of open access,
the authors have applied a Creative Commons Attribution (CC-BY) license to any
Author Accepted Manuscript version arising from this submission.

## References

  * [1] X. Huang and X. Liu, “Incorporating a topic model into a hypergraph neural network for searching-scenario oriented recommendations,” _Applied Sciences_ , vol. 12, no. 15, p. 7387, 2022.
  * [2] Y. Wang, P. Li, and C. Yao, “Hypergraph canonical correlation analysis for multi-label classification,” _Signal Processing_ , vol. 105, pp. 258–267, 2014.
  * [3] K. Wade, D. Greene, C. Lee, D. Archambault, and P. Cunningham, “Identifying representative textual sources in blog networks,” _Proceedings of the International AAAI Conference on Web and Social Media_ , vol. 5, no. 1, pp. 393–400, Aug. 2021. [Online]. Available: https://ojs.aaai.org/index.php/ICWSM/article/view/14096
  * [4] S. Feng, E. Heath, B. Jefferson, C. Joslyn, H. Kvinge, H. D. Mitchell, B. Praggastis, A. J. Eisfeld, A. C. Sims, L. B. Thackray, S. Fan, K. B. Walters, P. J. Halfmann, D. Westhoff-Smith, Q. Tan, V. D. Menachery, T. P. Sheahan, A. S. Cockrell, J. F. Kocher, K. G. Stratton, N. C. Heller, L. M. Bramer, M. S. Diamond, R. S. Baric, K. M. Waters, Y. Kawaoka, J. E. McDermott, and E. Purvine, “Hypergraph models of biological networks to identify genes critical to pathogenic viral response,” _BMC Bioinformatics_ , vol. 22, no. 287, 2021.
  * [5] W. Zhou and L. Nakhleh, “Properties of metabolic graphs: biological organization or representation artifacts?” _BMC Bioinformatics_ , vol. 12, no. 132, 2011.
  * [6] B. Alsallakh, L. Micallef, W. Aigner, H. Hauser, S. Miksch, and P. Rodgers, “The state-of-the-art of set visualization,” _Computer Graphics Forum_ , vol. 35, no. 1, pp. 234–260, 2016.
  * [7] J. Flower and J. Howse, “Generating euler diagrams,” in _Diagrammatic Representation and Inference: Second International Conference, Diagrams 2002 Callaway Gardens, GA, USA, April 18–20, 2002 Proceedings 2_. Springer, 2002, pp. 61–75.
  * [8] P. Rodgers, L. Zhang, and A. Fish, “General euler diagram generation,” in _Diagrammatic Representation and Inference_ , G. Stapleton, J. Howse, and J. Lee, Eds. Berlin, Heidelberg: Springer Berlin Heidelberg, 2008, pp. 13–27.
  * [9] P. Simonetto and D. Auber, “Visualise undrawable euler diagrams,” in _2008 12th International Conference Information Visualisation_ , 2008, pp. 594–599.
  * [10] P. Rodgers, L. Zhang, and H. Purchase, “Wellformedness properties in euler diagrams: Which should be used?” _IEEE Transactions on Visualization and Computer Graphics_ , vol. 18, no. 7, pp. 1089–1100, 2011.
  * [11] B. Alsallakh, L. Micallef, W. Aigner, H. Hauser, S. Miksch, and P. Rodgers, “Visualizing sets and set-typed data: State-of-the-art and future challenges,” in _EuroVis - STARs_ , R. Borgo, R. Maciejewski, and I. Viola, Eds. The Eurographics Association, 2014.
  * [12] M. T. Fischer, A. Frings, D. A. Keim, and D. Seebacher, “Towards a survey on static and dynamic hypergraph visualizations,” in _2021 IEEE Visualization Conference (VIS)_ , 2021, pp. 81–85.
  * [13] H. A. Kestler, A. Müller, J. M. Kraus, M. Buchholz, T. M. Gress, H. Liu, D. W. Kane, B. R. Zeeberg, and J. N. Weinstein, “VennMaster: Area-proportional euler diagrams for functional go analysis of microarrays,” _BMC Bioinformatics_ , vol. 9, 2008.
  * [14] G. Stapleton, J. Flower, P. Rodgers, and J. Howse, “Automatically drawing euler diagrams with circles,” _Journal of Visual Languages & Computing_, vol. 23, no. 3, pp. 163–193, 2012.
  * [15] L. Wilkinson, “Exact and approximate area-proportional circular venn and euler diagrams,” _IEEE Transactions on Visualization and Computer Graphics_ , vol. 18, no. 2, pp. 321–331, 2012.
  * [16] L. Micallef and P. Rodgers, “eulerAPE: Drawing area-proportional 3-venn diagrams using ellipses,” _PLoS ONE_ , vol. 9, no. 7, p. e101717, 2014.
  * [17] G. Stapleton, P. Rodgers, J. Howse, and L. Zhang, “Inductively generating euler diagrams,” _IEEE Transactions on Visualization and Computer Graphics_ , vol. 17, no. 1, pp. 88–100, 2011.
  * [18] W. Evans, P. Rza̧żewski, N. Saeedi, C.-S. Shin, and A. Wolff, “Representing graphs and hypergraphs by touching polygons in 3D,” in _International Symposium on Graph Drawing and Network Visualization_ , 2019, pp. 18–32.
  * [19] B. Qu, E. Zhang, and Y. Zhang, “Automatic polygon layout for primal-dual visualization of hypergraphs,” _IEEE Transactions on Visualization and Computer Graphics_ , vol. 28, no. 1, pp. 633–642, 2021.
  * [20] C. Collins, G. Penn, and S. Carpendale, “Bubble sets: Revealing set relations with isocontours over existing visualizations,” _IEEE Transactions on Visualization and Computer Graphics_ , vol. 15, no. 6, pp. 1009–1016, 2009.
  * [21] A. Efrat, Y. Hu, S. G. Kobourov, and S. Pupyrev, “MapSets: Visualizing embedded and clustered graphs,” in _Graph Drawing_ , C. Duncan and A. Symvonis, Eds. Berlin, Heidelberg: Springer Berlin Heidelberg, 2014, pp. 452–463.
  * [22] E. R. Gansner, Y. Hu, and S. Kobourov, “GMap: Visualizing graphs and clusters as maps,” in _2010 IEEE Pacific Visualization Symposium (PacificVis)_ , 2010, pp. 201–208.
  * [23] P. Rottmann, M. Wallinger, A. Bonerath, S. Gedicke, M. Nöllenburg, and J.-H. Haunert, “MosaicSets: Embedding set systems into grid graphs,” _IEEE Transactions on Visualization and Computer Graphics_ , vol. 29, no. 1, pp. 875–885, 2023.
  * [24] L. Euler, “Lettres à une princesse d’allemagne,” _letters no. 102-108_ , 1761.
  * [25] K. Koffka, _Principles of Gestalt Psychology_. Harcourt Brace, 1935.
  * [26] S. E. Palmer, “Common region: A new principle of perceptual grouping,” _Cognitive Psychology_ , vol. 24, no. 3, pp. 436–447, 1992.
  * [27] A. Blake, G. Stapleton, P. Rodgers, L. Cheek, and J. Howse, “The impact of shape on the perception of euler diagrams,” in _Diagrammatic Representation and Inference_ , T. Dwyer, H. Purchase, and A. Delaney, Eds. Berlin, Heidelberg: Springer Berlin Heidelberg, 2014, pp. 123–137.
  * [28] L. Micallef, P. Dragicevic, and J.-D. Fekete, “Assessing the effect of visualizations on bayesian reasoning through crowdsourcing,” _IEEE Transactions on Visualization and Computer Graphics_ , vol. 18, no. 12, pp. 2536–2545, 2012.
  * [29] B. Saket, P. Simonetto, S. Kobourov, and K. Börner, “Node, node-link, and node-link-group diagrams: An evaluation,” _IEEE Transactions on Visualization and Computer Graphics_ , vol. 20, no. 12, pp. 2231–2240, 2014.
  * [30] E. Mäkinen, “How to draw a hypergraph,” _International Journal of Computer Mathematics_ , vol. 34, no. 3-4, pp. 177–185, 1990.
  * [31] R. Kehlbeck, J. Gortler, Y. Wang, and O. Deussen, “SPEULER: Semantics-preserving euler diagrams,” _IEEE Transactions on Visualization and Computer Graphics_ , vol. 28, no. 01, pp. 433–442, jan 2022.
  * [32] L. Micallef and P. Rodgers, “eulerForce: Force-directed layout for euler diagrams,” _Journal of Visual Languages & Computing_, vol. 25, no. 6, pp. 924–934, 2014. [Online]. Available: https://www.sciencedirect.com/science/article/pii/S1045926X14000810
  * [33] P. Simonetto, D. Archambault, and C. Scheidegger, “A simple approach for boundary improvement of euler diagrams,” _IEEE Transactions on Visualization and Computer Graphics_ , vol. 22, no. 1, pp. 678–687, 2016.
  * [34] L. Couturat, _Opuscules et fragments inédits de Leibniz_. Felix Alcan, 1903.
  * [35] P. Rodgers, G. Stapleton, and P. Chapman, “Visualizing sets with linear diagrams,” _ACM Transactions on Compututer-Human Interactaction_ , vol. 22, no. 6, sep 2015.
  * [36] B. Alper, N. Riche, G. Ramos, and M. Czerwinski, “Design study of linesets, a novel set visualization technique,” _IEEE Transactions on Visualization and Computer Graphics_ , vol. 17, no. 12, pp. 2259–2267, 2011.
  * [37] B. Jacobsen, M. Wallinger, S. Kobourov, and M. Nöllenburg, “Metrosets: Visualizing sets as metro maps,” _IEEE Transactions on Visualization and Computer Graphics_ , vol. 27, no. 2, pp. 1257–1267, 2021.
  * [38] K. Dinkla, M. J. van Kreveld, B. Speckmann, and M. A. Westenberg, “Kelp diagrams: Point set membership visualization,” _Computer Graphics Forum_ , vol. 31, no. 3pt1, pp. 875–884, 2012.
  * [39] W. Meulemans, N. H. Riche, B. Speckmann, B. Alper, and T. Dwyer, “KelpFusion: A hybrid set visualization technique,” _IEEE Transactions on Visualization and Computer Graphics_ , vol. 19, no. 11, pp. 1846–1858, 2013.
  * [40] N. H. Riche and T. Dwyer, “Untangling euler diagrams,” _IEEE Transactions on Visualization and Computer Graphics_ , vol. 16, no. 6, pp. 1090–1099, 2010.
  * [41] N. A. Arafat and S. Bressan, “Hypergraph drawing by force-directed placement,” in _International Conference on Database and Expert Systems Applications_ , 2017, pp. 387–394.
  * [42] J. Paquette and T. Tokuyasu, “Hypergraph visualization and enrichment statistics: how the EGAN paradigm facilitates organic discovery from big data,” in _Human Vision and Electronic Imaging XVI_ , B. E. Rogowitz and T. N. Pappas, Eds., vol. 7865, International Society for Optics and Photonics. SPIE, 2011, p. 78650E.
  * [43] B. Alsallakh, W. Aigner, S. Miksch, and H. Hauser, “Radial sets: Interactive visual analysis of large overlapping sets,” _IEEE Transactions on Visualization and Computer Graphics_ , vol. 19, no. 12, pp. 2496–2505, 2013.
  * [44] A. Kerren and I. Jusufi, “A novel radial visualization approach for undirected hypergraphs,” in _Proceedings of the 17th Eurographics Conference on Visualization, Short paper track_ , 2013.
  * [45] M. Purohit, B. A. Prakash, C. Kang, Y. Zhang, and V. Subrahmanian, “Fast influence-based coarsening for large networks,” in _Proceedings of the 20th ACM SIGKDD international conference on Knowledge discovery and data mining_ , 2014, pp. 1296–1305.
  * [46] K. Shin, A. Ghoting, M. Kim, and H. Raghavan, “SWeG: Lossless and lossy summarization of web-scale graphs,” in _The World Wide Web Conference_ , 2019, pp. 1679–1690.
  * [47] M. A. Beg, M. Ahmad, A. Zaman, and I. Khan, “Scalable approximation algorithm for graph summarization,” in _Pacific-Asia Conference on Knowledge Discovery and Data Mining_. Springer, 2018, pp. 502–514.
  * [48] Z. Shen, K.-L. Ma, and T. Eliassi-Rad, “Visual analysis of large heterogeneous social networks by semantic and structural abstraction,” _IEEE Transactions on Visualization and Computer Graphics_ , vol. 12, no. 6, pp. 1427–1439, 2006.
  * [49] K. Lee, H. Jo, J. Ko, S. Lim, and K. Shin, “SSumM: Sparse summarization of massive graphs,” _Proceedings of the 26th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining_, pp. 144–154, 2020.
  * [50] D. Koutra, U. Kang, J. Vreeken, and C. Faloutsos, “VoG: Summarizing and understanding large graphs,” _Proceedings of the 2014 SIAM international conference on data mining_ , pp. 91–99, 2014.
  * [51] N. Shah, D. Koutra, T. Zou, B. Gallagher, and C. Faloutsos, “TimeCrunch: Interpretable dynamic graph summarization,” _Proceedings of the 21th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining_ , pp. 1055–1064, 2015.
  * [52] C. Dunne and B. Shneiderman, “Motif simplification: improving network visualization readability with fan, connector, and clique glyphs,” _Proceedings of the SIGCHI Conference on Human Factors in Computing Systems_ , pp. 3247–3256, 2013.
  * [53] J. Abello, F. van Ham, and N. Krishnan, “ASK-GraphView: A large scale graph visualization system,” _IEEE Transactions on Visualization and Computer Graphics_ , vol. 12, no. 5, pp. 669–676, 2006.
  * [54] D. Archambault, T. Munzner, and D. Auber, “GrouseFlocks: Steerable exploration of graph hierarchy space,” _IEEE Transactions on Visualization and Computer Graphics_ , vol. 14, no. 4, pp. 900–913, 2008.
  * [55] ——, “Tugging graphs faster: Efficiently modifying path-preserving hierarchies for browsing paths,” _IEEE Transactions on Visualization and Computer Graphics_ , vol. 17, no. 3, pp. 276–289, 2011.
  * [56] S. Golodetz, A. Arnab, I. Voiculescu, and S. Cameron, “Simplifying TugGraph using zipping algorithms,” _Pattern Recognition_ , vol. 103, p. 107257, 2020.
  * [57] Y. Zhou, A. Rathore, E. Purvine, and B. Wang, “Topological simplifications of hypergraphs,” _IEEE Transactions on Visualization and Computer Graphics (TVCG)_ , 2022.
  * [58] P. Oliver, E. Zhang, and Y. Zhang, “Scalable hypergraph visualization,” _IEEE Transactions on Visualization and Computer Graphics_ , pp. 1–11, 2023.
  * [59] M. Kritz and K. Perlin, “A new scheme for drawing hypergraphs,” _International journal of computer mathematics_ , vol. 50, no. 3-4, pp. 131–134, 1994.
  * [60] J.-B. Lamy, “Visualizing undirected graphs and symmetric square matrices as overlapping sets,” _Multimedia Tools and Applications_ , vol. 78, no. 23, pp. 33 091–33 112, 2019.
  * [61] A. Lex, N. Gehlenborg, H. Strobelt, R. Vuillemot, and H. Pfister, “Upset: Visualization of intersecting sets,” _IEEE Transactions on Visualization and Computer Graphics_ , vol. 20, no. 12, pp. 1983–1992, 2014.
  * [62] R. Sadana, T. Major, A. Dove, and J. Stasko, “OnSet: A visualization technique for large-scale binary set data,” _IEEE Transactions on Visualization and Computer Graphics_ , vol. 20, no. 12, pp. 1993–2002, 2014.
  * [63] P. Valdivia, P. Buono, C. Plaisant, N. Dufournaud, and J.-D. Fekete, “Analyzing dynamic hypergraphs with Parallel Aggregated Ordered Hypergraph visualization,” _IEEE Transactions on Visualization and Computer Graphics_ , vol. 27, no. 1, pp. 1–13, 2021.
  * [64] G. Stapleton, P. Rodgers, J. Howse, and J. Taylor, “Properties of Euler diagrams,” _Electronic Communications of the EASST_ , vol. 7, 2007.
  * [65] P. Rodgers, “A survey of euler diagrams,” _Journal of Visual Languages & Computing_, vol. 25, no. 3, pp. 134–155, 2014.
  * [66] D. Michail, J. Kinable, B. Naveh, and J. V. Sichi, “Jgrapht—a java library for graph data structures and algorithms,” _ACM Trans. Math. Softw._ , vol. 46, no. 2, May 2020.
  * [67] J. M. Boyer and W. J. Myrvold, “On the cutting edge: Simplified ${O}(n)$ planarity by edge addition,” _Journal of Graph Algorithms and Applications_ , vol. 8, pp. 241–273, 2004.
  * [68] C. Kuratowski, “Sur le probleme des courbes gauches en topologie,” _Fundamenta mathematicae_ , vol. 15, no. 1, pp. 271–283, 1930.
  * [69] D. S. Johnson and H. O. Pollak, “Hypergraph planarity and the complexity of drawing venn diagrams,” _Journal of Graph Theory_ , vol. 11, no. 3, pp. 309–325, 1987. [Online]. Available: https://onlinelibrary.wiley.com/doi/abs/10.1002/jgt.3190110306
  * [70] R. Kosara, T. J. Jankun-Kelly, and E. Chlan, “IEEE InfoVis 2007 contest: InfoVis goes to the movies,” https://eagereyes.org/blog/2007/infovis-contest-2007-data.
  * [71] J. Leskovec and A. Krevl, “SNAP Datasets: Stanford large network dataset collection,” http://snap.stanford.edu/data, Jun. 2014.
  * [72] L. C. Freeman, “Finding social groups: A meta-analysis of the southern women data,” http://moreno.ss.uci.edu/86.pdf, 2003.
  * [73] B. Shneiderman, “The eyes have it: A task by data type taxonomy for information visualizations,” in _Proceedings 1996 IEEE symposium on visual languages_. IEEE, 1996, pp. 336–343.


# Quantum Fokker-Planck structure of the Lindblad equation

Mário J. de Oliveira  Universidade de São Paulo, Instituto de Física, Rua do
Matão, 1371, 05508-090 São Paulo, SP, Brazil

###### Abstract

We show that the quantum Fokker-Planck equation, obtained by a canonical
quantization of its classical version, can be transformed into an equation of
the Lindblad form. This result allows us to conclude that the quantum Fokker-
Planck equation preserves the trace and positivity of the density operator.
The Fokker-Planck structure gives explicit expression for the quantum
equivalence of probability current as well as the quantum equivalence of
detailed balance. We also propose expression for the rate of entropy
production and show that it does not vanish for a closed system except in
equilibrium.

##  I Introduction

The dynamics of quantum open systems lindblad1976 ; iche1978 ; dekker1979a ;
dekker1979b ; dekker1981 ; caldeira1981 ; caldeira1983a ; caldeira1983b ;
chang1985 ; gallis1993 ; munro1996 ; gardiner1999 ; banik2002 ; breuer2002 ;
caldeira2014 ; manzano2020  is usually formulated considering a system and its
environment. The equations of motion of the system is then derived by summing
out the degrees of freedom of the environment. The derivation is not
accomplished without assuming an approximation concerning the interactions of
the system with its environment. Usually, the environment is considered a
thermal system which means to say that the interaction with the system is
regarded as being of stochastic nature. Starting from the quantum Liouville
equation for the total system, which is the system proper and its environment,
the resulting evolution equation is a quantum Liouville equation supplemented
by a dissipation term $D$ breuer2002 ; caldeira2014 ; manzano2020 ,

$\frac{d\rho}{dt}=\frac{1}{i\hbar}[H,\rho]+D,$ (1)

where $H$ is the Hamiltonian of the system.

Taking into account that the variables of the environment acts as stochastic
variables, the reduced equation (1) describes a quantum Markov process which
means that the dynamics is described by a quantum dynamic semi-group. The most
general form of the generator $D$ that has the property of semi-group and that
preserves the trace and positivity of the density operator is of the Lindblad
form breuer2002 ; caldeira2014 ; manzano2020 ,

$D=\sum_{jk}a_{jk}(2A_{j}\rho A_{k}^{\dagger}-A_{k}^{\dagger}A_{j}\rho-\rho
A_{k}^{\dagger}A_{j}),$ (2)

where $a_{jk}$ are the entries of a Hermitian and positive matrix. The
equation (1) with $D$ in the form (2) is called the Lindblad equation.

An alternative approach to reach an equation for quantum open system is to
consider the classical Fokker-Planck-Kramers equation kampen1981 ; risken1989
; gardiner2009 ; tome2015 , which is known to describe open classical systems,
and carry out its canonical quantization oliveira2016 ; oliveira2018 ;
tome2023 . The resulting quantum Fokker-Planck (FP) equation that gives the
time evolution of the density operator $\rho$ is given by

$i\hbar\frac{d\rho}{dt}=[H,\rho]-\frac{1}{2}\sum_{j}[x_{j},J_{j}+J_{j}^{\dagger}],$
(3)

where $J_{j}$ is the quantum version of the probability current, given by

$J_{j}=-\gamma_{j}(\rho g_{j}+\frac{m}{i\hbar\beta_{j}}[x_{j},\rho]),$ (4)

and

$g_{j}=-\frac{m}{i\hbar\beta_{j}}(e^{\beta_{j}H}x_{j}e^{-\beta_{j}H}-x_{j}).$
(5)

As happens to its classical version, this equation describes the contact of a
system of interacting particles of mass $m$ with thermal reservoirs at
temperatures inversely proportional to $\beta_{j}$, and $\gamma_{j}$ measures
the strength of the interaction with the reservoirs. The positions and momenta
of the particles are denoted by $x_{j}$ and $p_{j}$. The first and second
terms of the current $J_{j}$ corresponds to the dissipation and fluctuation,
respectively. We remark that $g_{j}$, which is related to dissipation, is not
in general proportional to the momentum $p_{j}$ as in the classical
dissipation but becomes proportional to $p_{j}$ in the classical limit.

Equations similar to (3) were considered by Dekker dekker1981  and by Caldeira
and Leggett caldeira1983b ; caldeira2014 . However, there is a difference in
that the dissipation term of their equations is proportional to the momentum
whereas in equation (3), the dissipation term is proportional to a general
term $g_{j}$ which depends on the Hamiltonian of the system as can be seen in
equation (5). This form of $g_{j}$ is crucial if we wish to describe the
thermodynamic equilibrium, or in other words, if we wish that the system
thermalizes in the long run.

The quantum FP equation (3) can be written in a more symmetric form in terms
of annihilation and creation operator $a_{j}$ and $a_{j}^{\dagger}$ in which
case it reads

$i\hbar\frac{d\rho}{dt}=[H,\rho]-\sum_{j}([a_{j},J_{j}^{\dagger}]+[a_{j}^{\dagger},J_{j}]),$
(6)

where

$J_{j}=i\gamma_{j}(g_{j}\rho+\frac{1}{\beta_{j}}[a_{j},\rho]),$ (7)

and

$g_{j}=\frac{1}{\beta_{j}}(e^{-\beta H}a_{j}e^{\beta_{j}h}-a_{j}).$ (8)

It is worth writing $J_{j}$ in the form

$J_{j}=\frac{i\gamma_{j}}{\beta_{j}}(e^{-\beta H}a_{j}e^{\beta_{j}h}\rho-\rho
a_{j}).$ (9)

The quantum FP equation in either forms (3) or (6) is understood as describing
a quantum Markov process and in this sense it should be of the type given by
equations (1) and (2). The first term of the quantum FP equation which
corresponds to a unitary transformation is indeed the same. As to the second
non-unitary term, it is not of the Lindblad type given by (2). The main
purpose of the present paper is to show that the second term of the quantum FP
equation can be transformed into the Lindblad form, showing thus that the
quantum FP equation preserves the trace and positivity of the density operator
$\rho$.

##  II Quantum FP structure

We consider a Hilbert vector space and choose a basis consisting of the
eigenvectors of some Hermitian operator $L$. The eigenvectors associated to
the eigenvalue $\lambda_{i}$ of $L$ are denoted by $\phi_{i}$, that is,
$L\phi_{i}=\lambda_{i}\phi_{i}$. Taking into account that $L$ is Hermitian its
left eigenvectors are the adjoint vector $\phi_{i}^{\dagger}$. The operators
acting on the vectors of the Hilbert space such as $L$ itself can also be
understood as belonging to another vector space, the Liouville space, whose
complete basis consists of the operators $A_{ij}=\phi_{j}\phi_{i}^{\dagger}$.

The general expression of a non-unitary generator $D$ which preserve the trace
of $\rho$ and its complete positivity for any initial condition is of the
Lindblad form breuer2002 ,

$D=\sum_{ij,k\ell}a_{ij,k\ell}(2A_{ij}\rho
A_{k\ell}^{\dagger}-A_{k\ell}^{\dagger}A_{ij}\rho-\rho
A_{k\ell}^{\dagger}A_{ij}),$ (10)

where $a_{ij,k\ell}$ are the entries of a Hermitian and positive matrix. Our
point of depart is the following expression of the Lindblad type

$D=\sum_{ij,k\ell}b_{ij,k\ell}(2A_{ij}\rho
A_{k\ell}^{\dagger}-A_{k\ell}^{\dagger}A_{ij}\rho-\rho
A_{k\ell}^{\dagger}A_{ij})$
$+\sum_{ij,k\ell}c_{ij,k\ell}(2A_{ij}^{\dagger}\rho
A_{k\ell}-A_{k\ell}A_{ij}^{\dagger}\rho-\rho A_{k\ell}A_{ij}^{\dagger}),$ (11)

where $b_{ij,k\ell}$ and $c_{ij,k\ell}$ are the entries of Hermitian and
positive matrices, and are nonzero only when $i\leq j$ and $k\leq\ell$.

Defining the operators $B_{ij}$ by

$\alpha_{ij}B_{ij}=\sum_{k\ell}b_{ij,k\ell}^{*}A_{k\ell},$ (12)

where $\alpha_{ij}\geq 0$, the first summation can be written in the form

$\sum_{ij}\alpha_{ij}(A_{ij}\rho B_{ij}^{\dagger}+B_{ij}\rho
A_{ij}^{\dagger}-A_{ij}^{\dagger}B_{ij}\rho-\rho B_{ij}^{\dagger}A_{ij}).$
(13)

In an analogous manner we defined the operators $C_{ij}$ by

$\alpha_{ij}C_{ij}=\sum_{k\ell}c_{ij,k\ell}A_{k\ell},$ (14)

and the second summation becomes

$\sum_{ij}\alpha_{ij}(A_{ij}^{\dagger}\rho C_{ij}+C_{ij}^{\dagger}\rho
A_{ij}-A_{ij}C_{ij}^{\dagger}\rho-\rho C_{ij}A_{ij}^{\dagger}).$ (15)

Summing up these two terms, we reach the expression

$D=\sum_{ij}\alpha_{ij}\\{[A_{ij},\rho
B_{ij}^{\dagger}-C_{ij}^{\dagger}\rho]-[A_{ij}^{\dagger},B_{ij}\rho-\rho
C_{ij}]\\},$ (16)

and the Lindblad equation acquires the FP structure

$i\hbar\frac{d\rho}{dt}=[H,\rho]-\sum_{ij}\\{[A_{ij},J_{ij}^{\dagger}]+[A_{ij}^{\dagger},J_{ij}]\\},$
(17)

where $J_{ij}$ is given by

$J_{ij}=i\hbar\alpha_{ij}(B_{ij}\rho-\rho C_{ij}).$ (18)

The expression (17) for the Lindblad equation is particularly meaningful
because $J_{ij}$ represents the quantum version of the probability current.
Suppose that the right-hand side of (17) vanishes for a density operator
$\rho_{0}$, in which case the system is said to be in a stationary state. If
in addition the currents $J_{ij}(\rho_{0})$ vanish, in which case $[H,\rho]$
also vanishes, then the system will be in thermodynamic equilibrium. The
vanishing of the currents corresponds to the condition of detailed balance
since each term of the summation in (17) vanishes. The condition of detailed
balance is represented by

$B_{ij}\rho_{0}=\rho_{0}C_{ij},$ (19)

for some $\rho_{0}$.

##  III Contact with thermal reservoirs

There are various possibilities of choosing the operators $B_{ij}$ and
$C_{ij}$. The only restriction is that the coefficients of the expansions (12)
and (14) define Hermitian and positive matrices. The choices will depend on
the type of physical conditions one wants to describe. Here we choose these
operators with the purpose of describing a system in contact with several heat
reservoir at distinct temperatures. When the temperatures are all the same,
then in the stationary state the system will be in thermodynamic equilibrium
in which case the density operator is of the Gibbs form

$\rho_{0}=\frac{1}{Z}e^{-\beta H},$ (20)

where $\beta$ is inversely proportional to the temperature of the reservoirs.

We choose $C_{ij}$ and $B_{ij}$ so that

$B_{ij}e^{-\beta_{ij}H}=e^{-\beta_{ij}H}C_{ij},$ (21)

where $\beta_{ij}$ are constants and $H$ is the Hamiltonian. When $\beta_{ij}$
has the same value, independent of $i$ and $j$, the condition (21) guarantees
that the detailed balance condition (19) is fulfilled and the system will be
found in thermodynamic equilibrium. In other words, the system will thermalize
in the long run.

A simplification arises by choosing $C_{ij}=A_{ij}$ so that $B_{ij}$ is given
by

$B_{ij}=e^{-\beta_{ij}H}A_{ij}e^{\beta_{ij}H},$ (22)

and the current (18) becomes

$J_{ij}=i\hbar\alpha_{ij}(e^{-\beta_{ij}H}A_{ij}e^{\beta_{ij}H}\rho-\rho
A_{ij}),$ (23)

which has the form (9) as desired.

It is now left to show that the coefficients of the expansion of $B_{ij}$ in
terms of $A_{ij}$ are entries of a Hermitian and positive matrix. We recall
that $A_{ij}=\phi_{j}\phi_{i}^{\dagger}$ where $\phi_{i}$ are the eigenvectors
of $L$.

Let us denote by $\chi_{j}$ and $E_{j}$ the eigenvectors and eigenvalues of
the Hamiltonian, that is, $H\chi_{i}=E_{i}\chi_{i}$. The operators
$X_{ij}=\chi_{j}\chi_{i}^{\dagger}$ can be considered a complete basis of the
Liouville space. The change from this basis to the basis used above is given
by the unitary transformation

$A_{ij}=\sum_{k\ell}U_{ij,k\ell}X_{k\ell}.$ (24)

Replacing this expression in (22), we find

$B_{ij}=\sum_{ij}U_{ij,k\ell}e^{-\beta_{ij}(E_{k}-E_{\ell})}X_{k\ell}.$ (25)

Using

$X_{ij}=\sum_{k\ell}U_{ij,k\ell}^{\dagger}A_{k\ell},$ (26)

it can be written as

$B_{ij}=\sum_{k\ell}G_{ij,k\ell}A_{k\ell},$ (27)

where

$G_{k\ell,ij}^{*}=\sum_{mn}U_{ij,mn}e^{-\beta_{ij}(E_{m}-E_{n})}U_{mn,k\ell}^{\dagger}.$
(28)

From this expression it follows that $G_{k\ell,ij}^{*}=G_{ij,k\ell}$ and that
the matrix with elements $G_{ij,k\ell}$ is positive, finishing our
demonstration.

##  IV Entropy production

The Lindblad equation or its quantum FP version (17) is supposed to describe
the thermodynamic of quantum system in equilibrium or out of equilibrium. In
this sense it constitutes the basic equation of a stochastic quantum
thermodynamics oliveira2016 ; oliveira2018 ; tome2023 . A fundamental concept
in the description of systems out of thermodynamic equilibrium is the entropy
production which we discuss below.

The average energy $U$ is defined by

$U={\rm Tr}(H\rho),$ (29)

and its time evolution is obtained from the quantum FP equation (17), and is
given by

$\frac{dU}{dt}=\sum_{ij}\Phi_{ij}^{u},$ (30)

where

$\Phi_{ij}^{u}=-\frac{1}{i\hbar}\\{{\rm Tr}[H,A_{ij}]J_{ij}^{\dagger}+{\rm
Tr}[H,A_{ij}^{\dagger}]J_{ij}\\},$ (31)

and $\Phi^{u}$ is understood as the flux of energy to the system. The entropy
of the system is defined by

$S=-k{\rm Tr}(\rho\ln\rho),$ (32)

and its time variation is obtained from the FP equation (17), and is given by

$\frac{dS}{dt}=\Pi+\Phi,$ (33)

where

$\Pi=\frac{k}{i\hbar}\sum_{ij}{\rm
Tr}([\ln\rho-\ln\rho_{ij},A_{ij}]J_{ij}^{\dagger}+[\ln\rho-\ln\rho_{ij},A_{ij}^{\dagger}]J_{ij}),$
(34)

is understood as the rate of entropy production, and

$\Phi=\frac{k}{i\hbar}\sum_{ij}{\rm
Tr}([\ln\rho_{ij},A_{ij}]J_{ij}^{\dagger}+[\ln\rho_{ij},A_{ij}^{\dagger}]J_{ij})$
(35)

is understood as the flux of entropy to the system, where $\rho_{ij}$ is given
by

$B_{ij}\rho_{ij}=\rho_{ij}C_{ij}.$ (36)

For the case of a system in contact with several heat reservoirs,
$\ln\rho_{ij}$ is proportional to $-\beta_{ij}H$ and the flux of entropy can
be written in the form

$\Phi=\sum_{ij}\frac{1}{T_{ij}}\Phi_{ij}^{u},$ (37)

where $T_{ij}=1/k\beta_{ij}$ and can be understood as the temperature of the
heat reservoirs. We recall that $\Phi_{ij}^{u}$ is the energy flux, or heat
flux in the present case, from each heat reservoirs to the system

In the stationary state, the total flux of energy

$\Phi^{u}=\sum_{ij}\Phi_{ij}^{u}$ (38)

vanishes, but it does not mean that each flux $\Phi_{ij}^{u}$ vanishes because
the temperatures are not all the same. In this case the flux of entropy $\Phi$
does not vanish, and $\Pi=\Phi$. As a consequence, in the nonequilibrium
stationary state the production of entropy $\Pi$ is nonzero. If however
temperatures of the reservoirs are all the same, $T_{ij}=T$, then

$\Phi=\frac{1}{T}\Phi^{u},$ (39)

and in this case $\Phi$ vanishes and so does $\Pi$, which describes a system
in thermodynamic equilibrium.

##  V Isolated system

Usually one describes an isolated system by the Liouville equation. This is in
fact the point of depart of deriving the Lindblad equations for a given
system. The given system plus the environment are assumed to be described by
the Liouville equation because as a whole they are isolated, and the total
energy is a conserved quantity. If the system of interest is itself isolated,
then we could describe it by the Liouville equation, which means to regard the
dissipative term $D$ of equation (1) as nonexistent.

The mean feature of an isolated system that allows us to use the Liouville
equation is that the Hamiltonian is strictly conserved along a trajectory.
However, it is possible to impose a conservation of the Hamiltonian along a
stochastic trajectory in such a way that the dissipation term does not need to
be absent. Indeed, if we choose the operators $C_{ij}=B_{ij}=A_{ij}$ then

$J_{ij}(\rho)=i\hbar\alpha_{ij}[A_{ij},\rho],$ (40)

and if $A_{ij}$ commutes with the Hamiltonian $J_{ij}(H)=0$ and the
Hamiltonian will be strictly invariant.

In this case, $\Phi_{ij}^{u}$ vanishes identically and there will be no flux
of energy, as expected. The fluxes of entropy $\Phi_{ij}$ will also vanish
identically and there is no flux of entropy to or from the system. The rate of
entropy production $\Pi$ equals $dS/dt$ and is given by

$\Pi=\frac{k}{i\hbar}\sum_{ij}{\rm
Tr}([\ln\rho,A_{ij}]J_{ij}^{\dagger}+[\ln\rho,A_{ij}^{\dagger}]J_{ij}),$ (41)

It is nonzero but vanishes in the stationary state in which case it is also
the equilibrium state because $J_{ij}$ vanishes.

##  VI Conclusion

We have shown that the quantum FP equation can be transformed into an equation
that has the Lindblad equation. As the Lindblad equations preserves the trace
and positivity of the density operator so does the quantum FP equation. The
advantage of the FP form is that one easily recognizes the quantum equivalents
of the probability current and of the detailed balance condition. When the
detailed balance condition is not satisfied, the quantum system in the long
run will be found in a nonequilibrium stationary state. In this case the
production of entropy is nonzero and can be obtained by the expression
provided for the rate of entropy production. The Fokker-Planck form allows to
determine a dissipation term for the case in which the Hamiltonian of the
system is strictly constant, which can be understood as a closed system.

## References

  * (1) G. Lindblad, Commun. Math. Phys. 48, 119 (1976).
  * (2) G. Iche and P. Nozières, Physica A 91, 485 (1978).
  * (3) H. Dekker, Physica A 95, 311 (1979).
  * (4) H. Dekker, Phys. Lett. A 74, 15 (1979).
  * (5) H. Dekker, Phys. Rep. 80, 1 (1981).
  * (6) A. O. Caldeira and A. J. Leggett, Phys. Rev. Lett. 46, 211 (1981).
  * (7) A. O. Caldeira and A. J. Leggett, Ann. Phys. 149, 374 (1983).
  * (8) A. O. Caldeira and A. J. Leggett, Physica A 121, 587 (1983).
  * (9) L.-D. Chang and D. Waxman, J. Phys. C 18, 5873 (1985).
  * (10) M. R. Gallis, Phys. Rev. A 48, 1028 (1993).
  * (11) W. J. Munro and C. W. Gardiner, Phys. Rev. A 53, 2633 (1996).
  * (12) C. W. Gardiner and P. Zoller, Quantum Noise (Springer, Berlin, 1999); 2nd ed.
  * (13) S. K. Banik, B. C. Bag, and D. S. Ray, Phys. Rev. E 65, 051106 (2002).
  * (14) H.-P. Breuer and F. Petruccione, The Theory of Open Quantum Systems (Clarendon Press, Oxford, 2002).
  * (15) A. O. Caldeira, Introduction to Macroscopic Quantum Phenomena and Quantum Dissipation (Cambridge University Press, Cambridge, 2014).
  * (16) D. Manzano, “A short introduction to the Lindblad master equation”, AIP Advances 10, 025106 (2020).
  * (17) N. G. van Kampen, Stochastic Processes in Physics and Chemistry (North-Holland, Amsterdam, 1981).
  * (18) H. Risken, The Fokker-Planck Equation (Springer, Berlin, 1989); 2nd ed.
  * (19) C. Gardiner, Stochastic Methods (Springer, Berlin, 2009); 4th ed.
  * (20) T. Tomé and M. J. de Oliveira, Stochastic Dynamics and Irreversibility (Springer, Cham, 2015).
  * (21) M. J. de Oliveira, Phys. Rev. E 94, 012128 (2016).
  * (22) M. J. de Oliveira, Phys. Rev. E 97, 012105 (2018).
  * (23) T. Tomé and M. J. de Oliveira, Eur. Phys. J. Spec. Top. (2023).