11institutetext: TU Dresden, Germany 22institutetext: Data Semantics (DaSe)
Laboratory, Wright State University, OH, USA 33institutetext: Center for
Genomic and Computational Biology, Duke University, Durham, NC, USA

# On the Ontological Modeling of Trees

David Carral 11 Pascal Hitzler 22 Hilmar Lapp 33 Sebastian Rudolph 11

###### Abstract

Trees – i.e., the type of data structure known under this name – are central
to many aspects of knowledge organization. We investigate some central design
choices concerning the ontological modeling of such trees. In particular, we
consider the limits of what is expressible in the Web Ontology Language, and
provide a reusable ontology design pattern for trees.

##  1 Introduction

Trees are fundamental data structures for knowledge organization. They make
their appearance in the form of taxonomies, meronomies, decision trees,
branching processes, etc. As such they are fundamental for ontological
knowledge representation.

At the same time, however, it is not possible to fully characterize trees in
the Web Ontology Language (OWL) [13, 14] (see Section 3). It is thus an
important research question how to represent trees in ontology modeling, and
to understand the pros and cons of different ways to do it.

We need to realize, of course, that trees in ontology modeling often serve a
different purpose than in programming. Operations on trees important in
programming include, for example, adding or deleting items or pruning of whole
sections; i.e., some of the important operations do actually change the tree.
For ontology modeling purposes, in contrast, it is more appropriate to think
of a tree as static and as something which is being queried. Typical queries
would be to identify roots or leaves, common ancestors, or descendants.

However, despite the importance of trees for knowledge organization, there is
currently no corresponding ontology design pattern available on
ontologydesignpatterns.org. In this paper, we will provide such a pattern, and
will also discuss different design choices as well as their respective
advantages and disadvantages.

The rest of the paper is structured as follows. In Section 2 we present a
particularly interesting use case which has informed our work, namely the use
of ontology modeling for evolutionary or phylogenetic trees. In Section 3 we
discuss the fundamental shortcomings of the Web Ontology Language (OWL)
regarding the modeling of trees.111The pattern is available from
http://ontologydesignpatterns.org/wiki/Submissions:Tree_Pattern In Section 4
we present a basic ontology design pattern for the modeling of trees. In
Section 5 we discuss the special case of $n$-bounded trees (e.g., with $n=2$
for binary trees). In Section 6 we conclude.

##  2 Phylogenetic Trees

One of the central tenets following from the theory of organismal evolution is
that all life is related through descent with modification [4]. That is,
populations of a biological species can over time diverge enough, due to
natural selection, adaptation, genetic drift, and other forces acting
differentially on different populations, that they form new species, some of
which persist and go on themselves to split, giving rise to new species, and
so forth. Speciation through diversification can sometimes be driven by new
ecologic opportunities, for example when new habitats are being colonized, a
process often referred to as adaptive radiation [27, 28]. One of the most
prominent research objectives in evolutionary science is to reconstruct, using
genetic and organismal trait data, the evolutionary history of different
organisms, species, or life forms; i.e., to reconstruct the lines of shared
descent by which organisms are connected [9, 30]. Such a reconstruction is
represented in the form of a phylogenetic tree, in which the leaves are often
called operational taxonomic units (OTUs) and represent the sampled entities,
and internal nodes represent ancestral entities, such as ancestral populations
from which descendent ones diverged. Phylogenetic reconstruction results in
unrooted trees; the root is normally not known (and cannot normally be
sampled), but reasonably accurate mechanisms for inducing a root exist [15,
19] (for example, by including in the reconstruction analysis a group of
species – a so-called “outgroup” – that are already known to fall outside of
the ingroup for which evolutionary patterns are being studied).

A phylogenetic tree represents important evolutionary hypotheses about shared
history. For example, two OTUs A and B are more closely related to each other
than to OTU C if A and B share a more recent common ancestor than they do with
C. The subtree descending from a node forms a clade, clades which share a
parent are called sister clades. One of the major objects of comparative
phylogenetics is to identify the properties and processes (organismal traits,
geographic range, tempo and mode of evolution, etc) by which one clade differs
from others, in particular its sisters, and how these properties change along
lines of descent in the tree [8, 22]. This gives rise to a number of important
queries when mapping data onto phylogenetic trees for (or as a result of)
analysis. Particularly ubiquitous operations on trees include the following:
(1) finding the most recent common ancestor of a given number of nodes
(usually leaf nodes); (2) enumerating the leaf nodes, or all nodes descending
from a given (internal) node; (3) enumerating the sequence of ancestors of a
node to the root; and (4) identifying the last ancestor of a node A from which
another node B is not also descended. We will come back to these and other
operations as part of the competency questions for our modeling in Section 4.

Operations (1) and (4) correspond to two principle ways in which the semantics
of clade concepts can be defined on a tree [23], whether using a concrete
instantiation of a tree, or a hypothetical one. In the field of phylogenetic
taxonomy [24], a clade concept defined by the most recent common ancestor of a
set of (usually leaf) nodes includes the common ancestor and is referred to as
a node-based definition. In contrast, a branch-based definition circumscribes
the clade as the last ancestor of a (usually leaf) node that excludes (i.e.,
does not have as a descendant) another node (also usually a leaf node). The
semantics of a clade concept defined in this way is such that the branch
subtending from the ancestor node to its parent is included (hence the name
“branch-based”). To understand this, remember that a phylogenetic tree is a
model of evolutionary lines of descent reconstructed from sampled data. In
reality, there may be lines of descent which were not observed (sampled), for
example because all organisms from those lines are now extinct, but which, had
they been observed, would originate from the subtending branch and which would
therefore still be included in the clade because they would branch off after
the lineage to be excluded.

It is worth noting that spurred in part by the exponentially increasing amount
of data available for phylogenetic reconstruction, very large trees
encompassing up to tens of thousands of taxa have recently become available
[10, 6, 7, 29, 16], culminating in the initial publication of the synthesized
Open Tree of Life with about 2 million tips [11]. Such encompassing trees open
up unprecedented opportunities for comparative phylogenetic research. However,
this also means that our knowledge about the evolution of life is changing at
increasing pace and breadth, which makes it necessary to efficiently map clade
definitions from one tree to another, or from one revision of the Open Tree of
Life to a future one. A recent initiative, termed “phyloreferencing”
(http://phyloref.org) aims to accomplish this by using machine reasoning over
ontological representations of the semantics of both clade definitions and
phylogenetic trees [3, 21, 25]. In the rest of this paper, we abstract from
the specific use case and look at the task of ontological modeling of trees in
general.

##  3 Fundamental Limitations Regarding Tree Modeling

In order to investigate to what degree tree-based properties can be expressed
using common KR formalisms, we first need to formally define what structures
we denote by the notion “tree”.

###### Definition 1

A _rooted directed branching tree_ (short: _tree_) is defined as a directed
graph $T=(V,E)$ where $V$ is a set called _vertices_ or _nodes_ and
$E\subseteq V\times V$ is the set of edges, satisfying the following
properties:

  1. 1.

There is exactly one node $r\in V$ called _root_ , which has no incoming
edges, i.e., $E\cap(V\times\\{r\\})=\emptyset$.

  2. 2.

Every node $v\in V\setminus\\{r\\}$ that is not the root has exactly one
incoming edge, i.e., there exists exactly one $v^{\prime}\in V$ such that
$(v^{\prime},v)\in E$. We then call $v^{\prime}$ the parent of $v$ and $v$ the
child of $v^{\prime}$.

  3. 3.

Every node $v\in V$ can be reached from the root traversing edges, i.e., there
is a number $n\geq 0$ and a sequence $(v)_{i\in\\{0,\ldots,n\\}}$ such that
$r=v_{0}$, $v=v_{n}$, and for all $i\in\\{0,\ldots,n-1\\}$ we have
$(v_{i},v_{i+1})\in E$.

A node without children will be called _leaf node_. A _binary tree_ is a tree
where every node that is not a leaf has exactly two children. An _$n$ -ary
tree_ is a tree where every node that is not a leaf has exactly $n$ children.
An _$n$ -bounded tree_ is a tree where every node has at most $n$ children. A
tree is _finite_ if $V$ is finite.

When modeling trees using some logic-based KR language, we would like to
achieve that we can create a knowledge base which has exactly all (finite)
trees as its models (possibly using additional auxiliary vocabulary), in other
words, we would like to characterize or axiomatize the class of all (finite)
trees.

Unfortunately, it is not too hard to show that this is not possible by any KR
formalism that is expressible in first order predicate logic (FOL). A very
helpful tool for showing this is the well-known compactness theorem of first-
order logic[5].

######  Theorem 3.1 (Compactness of FOL)

A set $\Phi$ of FOL sentences is satisfiable if and only if every finite
subset of $\Phi$ is.

We now use this theorem to show our negative result.

###### Proposition 1

Let $\psi$ be a FOL sentence (using the binary predicate “$edge$”) such that
every finite tree $T=(V,E)$ corresponds to some model $\mathcal{I}$ of $\psi$,
i.e., $(V,E)\cong(\Delta^{\mathcal{I}},edge^{\mathcal{I}})$. Then, $\psi$ also
has a model which does not correspond to any (finite or infinite) tree.

###### Proof

Consider the following sequence $(\varphi_{i})_{i\in\mathbb{N}}$ of FOL
sentences (where $a$ is a fresh constant):

  * $\varphi_{1}:=\exists x_{1}.edge(x_{1},a)$

  * $\varphi_{2}:=\exists x_{1}\exists x_{2}.edge(x_{2},x_{1})\wedge edge(x_{1},a)$

  * $\varphi_{3}:=\exists x_{1}\exists x_{2}\exists x_{3}.edge(x_{3},x_{2})\wedge edge(x_{2},x_{1})\wedge edge(x_{1},a)$

  * $\vdots$

In words, $\varphi_{k}$ expresses that the node $a$ has an incoming edge-path
of length $k$. Now let $\Phi:=\\{\psi\\}\cup\\{\varphi_{k}\mid
k\in\mathbb{N}\\}$. Obviously, every finite subset of $\Phi$ is satisfiable
(intuitively, just pick an arbitrary large finite tree and then pick $a$ such
that it is “deep enough” in the tree). Then, by compactness of FOL, $\Phi$
itself must be satisfiable. However, in a model $\mathcal{I}$ of $\Phi$ the
element $a^{\mathcal{I}}$ cannot be reachable from the root, since then it
would have an incoming edge-path of maximal length which cannot be the case by
construction of $\Phi$. Hence $\mathcal{I}$ cannot correspond to a tree. By
construction, $\mathcal{I}$ is also a model of $\psi$.∎

This result shows, that trees (finite or infinite) are not fully axiomatizable
in FOL and any attempt to do so will only be approximate (although practically
useful).

On the other hand, trees are axiomatizable when we extend FOL (or just DLs for
that matter) by a transitive closure operator for binary predicates. Assume
that, for every binary predicate (or in DL terms: role) $p$, we allow for a
binary predicate/role name $p^{+}$ and define its semantics such that
$(p^{+})^{\mathcal{I}}$ is the transitive closure of $p^{\mathcal{I}}$. Then
the conditions of Definition 1 can be expressed using the following axioms:

$\displaystyle\\{\text{root}\\}$
$\displaystyle\sqsubseteq\neg\exists\text{edge}^{-}.\top$ (1)
$\displaystyle\neg\\{\text{root}\\}$
$\displaystyle\sqsubseteq{=}1\,\text{edge}^{-}.\top$ (2)
$\displaystyle\neg\\{\text{root}\\}$
$\displaystyle\sqsubseteq\exists(\text{edge}^{-})^{+}.\\{\text{root}\\}$ (3)

To axiomatize the class of binary trees, the following axiom can be added:

$\displaystyle\top$
$\displaystyle\sqsubseteq\neg\exists\text{edge}.\top\sqcup{{=}2}\,\text{edge}.\top$
(4)

In order to impose finiteness, one can axiomatize (as an auxiliary additional
structure) a finite linear order with a starting element and an ending element
and the successor role:

$\displaystyle\\{\text{start}\\}$
$\displaystyle\sqsubseteq\neg\exists\text{succ}^{-}.\top$ (5)
$\displaystyle\neg\\{\text{start}\\}$
$\displaystyle\sqsubseteq{=}1\,\text{succ}^{-}.\top$ (6)
$\displaystyle\neg\\{\text{start}\\}$
$\displaystyle\sqsubseteq\exists(\text{succ}^{-})^{+}.\\{\text{start}\\}$ (7)

$\displaystyle\\{\text{end}\\}$
$\displaystyle\sqsubseteq\neg\exists\text{succ}.\top$ (8)
$\displaystyle\neg\\{\text{end}\\}$
$\displaystyle\sqsubseteq{=}1\,\text{succ}.\top$ (9)
$\displaystyle\neg\\{\text{end}\\}$
$\displaystyle\sqsubseteq\exists(\text{succ})^{+}.\\{\text{end}\\}$ (10)

Transitive closures, of course, are not part of the OWL specification [13],
i.e., this characterization cannot be used when modeling in the Web Ontology
Language. Description logics featuring regular expressions over roles have,
however, been considered since the early days of DL research [1] and decision
and query answering procedures have been described for very expressive DLs
with that feature [2].

##  4 A Simple Tree Pattern

The repository of ontology design patterns on ontologydesignpatterns.org does
not contain any pattern for trees. There is also none for graphs which could
have been used to specialize a trees pattern. The repository contains a
pattern for lists,
though,222http://ontologydesignpatterns.org/wiki/Submissions:List and a list
pattern could be generalizable to a tree pattern.

The schema diagram for this list pattern is depicted in Figure 1. It reuses
the sequence
pattern333http://ontologydesignpatterns.org/wiki/Submissions:Sequence which
seems to be the relevant part for our purposes. We depict the sequence pattern
schema diagram in Figure 2 and all non-tautological axioms are given in Figure
3.444Generated with the OWLAPI LaTeX renderer [26]. The axiomatization appears
to be rather minimalistic, e.g., “follows” should be transitive over
“directlyFollows”, and for a sequence we should also use cardinality
restrictions to limit the number of followers and predecessors. We will return
to this later on.

Figure 1: List pattern schema diagram from ontologydesignpatterns.org Figure
2: Sequence pattern schema diagram from ontologydesignpatterns.org
directlyFollows $\displaystyle\sqsubseteq\text{follows}$ directlyFollows
$\displaystyle\equiv\text{directlyPrecedes}^{-}$ directlyPrecedes
$\displaystyle\sqsubseteq\text{precedes}$ precedes
$\displaystyle\equiv\text{follows}^{-}$ TransitiveProperty
$\displaystyle(\text{follows})$ TransitiveProperty
$\displaystyle(\text{precedes})$ Figure 3: Axioms for the sequence pattern
from Figure 2. We omitted axioms that were tautologies.

The list pattern just cited provides basic building blocks for a simple tree
pattern. However, we opt to change the names of the properties: It seems to be
more appropriate to use “hasChild” and “hasDescendant” rather than
“directlyPrecedes” and “precedes”, and to use “hasParent” and “hasAncestor”
rather than “directlyFollows” and “follows.”

Before proceeding with the tree pattern, we present a set of competency
questions [17] which seem representative to us and include operationes raised
as important in Section 2:

  1. 1.

Determine the root.

  2. 2.

Determine all ancestors of a given node.

  3. 3.

Determine all leaves.

  4. 4.

Determine all descendants of a given node.

  5. 5.

Determine all descendants of a given node which are leaves.

  6. 6.

Given two nodes, determine whether one is a descendant of the other.

  7. 7.

Given two nodes, determine all commmon ancestors.

  8. 8.

Given two nodes, determine the latest common ancestor.

  9. 9.

Given two nodes $x$ and $y$, determine the earliest ancestor of $x$ which is
not an ancestor of $y$.

We next give our proposal for a simple tree pattern. Afterwards we will
discuss our design choices. The schema diagram is given in Figure 4. However,
the axiomatization is really much more important; it can be found in Figure 6.
Note that some additional desired axioms, such as
$\text{hasParent}\sqsubseteq\text{hasAncestor}$ and transitivity of
hasAncestor can be inferred from the ones stated.

Figure 4: Schema diagram for the simple tree pattern. Unlabelled arrows are
subclass relationships. RootNode $\displaystyle(a)$ LeafNode
$\displaystyle(d)$ LeafNode $\displaystyle(e)$ LeafNode $\displaystyle(f)$
TreeNode $\displaystyle(b)$ TreeNode $\displaystyle(c)$ hasChild
$\displaystyle(a,b)$ hasChild $\displaystyle(a,c)$ hasChild
$\displaystyle(b,d)$ hasChild $\displaystyle(b,e)$ hasChild
$\displaystyle(c,f)$ hasSibling $\displaystyle(b,c)$ hasSibling
$\displaystyle(d,e)$ hasOutDegree $\displaystyle(a,2)$ hasOutDegree
$\displaystyle(b,2)$ hasOutDegree $\displaystyle(c,1)$ hasOutDegree
$\displaystyle(d,0)$ hasOutDegree $\displaystyle(e,0)$ hasOutDegree
$\displaystyle(f,0)$ Figure 5: Example ABox for a tree. LeafNode
$\displaystyle\sqsubseteq\text{TreeNode}$ (11) RootNode
$\displaystyle\sqsubseteq\text{TreeNode}$ (12) TreeNode
$\displaystyle\sqsubseteq\forall\text{hasOutDegree}.\text{xsd:positiveInteger}$
(13) TreeNode
$\displaystyle\sqsubseteq\mathord{=}1\text{hasOutDegree}.\text{xsd:positiveInteger}$
(14) LeafNode $\displaystyle\equiv\text{TreeNode}\sqcap\phantom{x}$
$\displaystyle\phantom{\equiv}\quad\forall\text{hasOutDegree}.\\{0^{\wedge\wedge}\text{xsd:positiveInteger}\\}$
(15) $\displaystyle\text{TreeNode}\sqcap\neg\text{LeafNode}$
$\displaystyle\equiv\text{TreeNode}\sqcap\phantom{x}$
$\displaystyle\phantom{\equiv}\quad\forall\text{hasOutDegree}.\\{x^{\wedge\wedge}\text{xsd:positiveInteger}\mid
1\leq x\\}$ (16) hasChild $\displaystyle\equiv\text{hasParent}^{-}$ (17)
hasDescendant $\displaystyle\equiv\text{hasAncestor}^{-}$ (18) hasChild
$\displaystyle\sqsubseteq\text{hasDescendant}$ (19)
$\displaystyle\text{hasDescendant}\circ\text{hasDescendant}$
$\displaystyle\sqsubseteq\text{hasDescendant}$ (20) TreeNode
$\displaystyle\sqsubseteq\forall\text{hasChild}.\text{TreeNode}$ (21)
$\displaystyle\text{TreeNode}\sqcap\neg\text{LeafNode}$
$\displaystyle\equiv\text{TreeNode}\sqcap\exists\text{hasChild}.\text{TreeNode}$
(22) TreeNode
$\displaystyle\sqsubseteq\forall\text{hasDescendant}.\text{TreeNode}$ (23)
TreeNode $\displaystyle\sqsubseteq\forall\text{hasParent}.\text{TreeNode}$
(24) TreeNode
$\displaystyle\sqsubseteq\forall\text{hasSibling}.\text{TreeNode}$ (25)
$\displaystyle\text{TreeNode}\sqcap\neg\text{RootNode}$
$\displaystyle\equiv\text{TreeNode}\sqcap\mathord{=}1\text{hasParent}.\top$
(26) TreeNode
$\displaystyle\sqsubseteq\forall\text{hasAncestor}.\text{TreeNode}$ (27)
RootNode
$\displaystyle\equiv\text{TreeNode}\sqcap\neg\exists\text{hasParent}.\top$
(28) LeafNode
$\displaystyle\equiv\text{TreeNode}\sqcap\neg\exists\text{hasChild}.\top$ (29)
Irreflexive $\displaystyle(\text{hasChild})$ (30) Irreflexive
$\displaystyle(\text{hasParent})$ (31) Irreflexive
$\displaystyle(\text{hasDescendant})$ (32) Irreflexive
$\displaystyle(\text{hasAncestor})$ (33) hasSibling
$\displaystyle\equiv\text{hasSibling}^{-}$ (34) Irreflexive
$\displaystyle(\text{hasSibling})$ (35) Figure 6: Axioms for the tree pattern
from Figure 4.

Before we proceed, let us first make a concrete example how this pattern
informs the graph structure of the ABox. Given a tree such as

$\textstyle{a\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{b\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{c\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{d}$$\textstyle{e}$$\textstyle{f}$

we encode it using the ABox from Figure 5; note that we omit redundant
statements which can be inferred from the axioms.

The axioms from Figure 6 should be self-explanatory. Axiom (16) uses a
datatype facet. The complete set of axioms is not in OWL DL because axioms
(32) and (33) declare irreflexivity for non-simple roles. If it is desireable
to stay within OWL DL, these axioms could be omitted.

Our pattern and axiomatization include some terms which may appear to be
redundant. Indeed, we could have omitted the use of hasParent and hasAncestor
as these are simply inverses of hasChild and hasDescendant, respectively.
Other aspects, however, are not redundant.

The property hasOutDegree may appear to be redundant, as it captures the
number of children of a node. However, it is not redundant as far as the OWL
model is concerned, because the underlying open world assumption makes it
impossible to count the number of children. This could of course be addressed
using a (local) closed world extension of OWL, such as in [20], however the
current standard does not support this. For the same reason, membership in the
classes RootNode and LeafNode cannot be inferred.

The case of the hasSibling property is more intricate. Again it would naively
appear as if it were redundant. However, we have not been able yet to
axiomatize it in the general case; for special cases where it is possible see
Section 5. A naive attempt by means of a rule555This rule can be converted
into OWL DL using rolification, see [18].

$\text{hasParent}(x,y)\wedge\text{hasChild}(y,z)\to\text{hasSibling}(x,z)$

is insufficient because for addressing some competency questions we require
irreflexivity of hasSibling, while the rule above renders hasSibling to be
non-simple, which is not allowed together with irreflexivity in OWL DL.

Let us return to the competency questions listed earlier; it turns out we can
address them all even when omitting the irreflexivity axioms for hasDescendant
and hasAncestor, such that our model stays within OWL DL. Questions 1 and 3
can be addressed using the RootNode and LeafNode classes. Questions 2 and 4
are straightforward, as is question 5 using the LeafNode class. Question 6 can
be solved with two queries using the hasDescendant property.

The remaining questions are more intricate. Given two nodes $x$ and $y$,
Question 7 can be addressed via

$\exists\text{hasDescendant}.\\{x\\}\sqcap\exists\text{hasDescendant}.\\{y\\}.$

Question 8 seems to require use of the hasSibling property. For readability we
first give the solution as first-order predicate logic formula:

$\displaystyle\phantom{\wedge}\text{hasChild}(z,w)\wedge(w=x\vee\text{hasDescendant}(w,x))$
$\displaystyle\wedge\text{hasSibling}(w,v)\wedge(v=y\vee\text{hasDescendant}(v,y)).$

Conversion of this into OWL following the approach laid out in [18] results in
the class description

$\displaystyle\exists\text{hasChild}.($
$\displaystyle(\\{x\\}\sqcup\exists\text{hasDescendant}.\\{x\\})$
$\displaystyle\sqcap(\exists\text{hasSibling}.(\\{y\\}\sqcup\exists\text{hasDescendant}.\\{y\\})).$

In a similar fashion, Question 9 can be addressed using the class description

$(\\{x\\}\sqcup\exists\text{hasDescendant}.\\{x\\})\sqcap(\exists\text{hasSibling}.(\\{y\\}\sqcup\exists\text{hasDescendant}.\\{y\\})).$

Note that irreflexivity of hasSibling is required for the class descriptions
just given. Or to be more precise, what is required is that there is no node
$z$ in the tree for which $\text{hasSibling}(z,z)$ is declared or can be
inferred; note that this is in fact a weaker requirement than what we get by
declaring irreflexivity. As a consequence, the irreflexivity declaration for
hasSibling can actually be omitted from the axiomatization without impact on
the just given solution to Question 9; however we prefer to keep the
irreflexivity declaration in the axiomatization as it disambiguates the model
[12]. As mentioned earlier, we have not been able to find a solution to infer
the (irreflexive) hasSibling relationship in the general case using OWL
axioms, thus we require it as a primitive. We will revisit this in the next
section, though.

Let us finally use our tree pattern to recover a list pattern based on it. The
schema diagram can be found in Figure 7. We keep only one property, hasNext,
which corresponds to hasChild, and hasSuccessor, which corresponds to
hasDescendant. The root becomes the first list item, the leaves become the
last list item. The outdegree is always 1 unless it’s the last list item, so
we also omit this information. The corresponding axiomatization, as derived
from the tree axiomatization above, can be found in Figure 8. As before, Axiom
(46) causes the pattern to fall outside OWL DL, and if this is undesirable,
this axiom should be omitted.

Figure 7: Schema diagram for the simple list pattern, derived from the tree
pattern.  FirstListItem $\displaystyle\sqsubseteq\text{ListItem}$ (36)
LastListItem $\displaystyle\sqsubseteq\text{ListItem}$ (37) ListItem
$\displaystyle\sqsubseteq\forall\text{hasNext}.\text{ListItem}$ (38) ListItem
$\displaystyle\sqsubseteq\forall\text{hasNext}^{-}.\text{ListItem}$ (39)
$\displaystyle\text{ListItem}\sqcap\neg\text{LastListItem}$
$\displaystyle\equiv\text{ListItem}\sqcap\mathord{=}1\text{hasNext}.\text{ListItem}$
(40) $\displaystyle\text{ListItem}\sqcap\neg\text{FirstListItem}$
$\displaystyle\equiv\text{ListItem}\sqcap\mathord{=}1\text{hasNext}^{-}.\text{ListItem}$
(41) FirstListItem
$\displaystyle\equiv\text{ListItem}\sqcap\neg\exists\text{hasNext}^{-}.\top$
(42) LastListItem
$\displaystyle\equiv\text{ListItem}\sqcap\neg\exists\text{hasNext}.\top$ (43)
hasNext $\displaystyle\sqsubseteq\text{hasSuccessor}$ (44)
$\displaystyle\text{hasNext}\circ\text{hasSuccessor}$
$\displaystyle\sqsubseteq\text{hasSuccessor}$ (45) Irreflexive
$\displaystyle(\text{hasSuccessor})$ (46) Figure 8: Axioms for the lists
pattern from Figure 7.

##  5 Trees With Bounded Arity

In this section, we look at $n$-bounded trees as a special case, and present a
set of OWL axioms that can be employed to model these.

###### Definition 2

A _rooted directed branching $n$-bounded tree_ (short: _$n$ -bounded tree_) is
a tree $T=(V,E)$ where every node has at most $n$ outgoing edges; i.e., for
every $v\in V$, $|E\cap(\\{v\\}\times V)|\leq n$.

In the previous section, we have discussed why we needed to include an
explicit hasSibling relation in our model, namely because we were unable to
axiomatically define it in OWL. If we know that the trees under consideration
are $n$-bounded, though, we can in fact infer the hasSibling relation.

To this end, we introduce a set of additional axioms (see Figure 9) that, if
combined with the axioms from Figure 6 can be used to axiomatize the structure
of an $n$-bounded tree. Key to this are axioms (50) and (51), which together
limit the number of children per node to a maximum of $n$.

Note that, if these axioms are considered, we can indeed automatically infer
the hasSibling relationship: Having an upper bound on the number of children
per node, we can use a finite set of concept names $\text{Child}_{i}$ to
differentiate the children of any given node in the tree. Note how, due to
(50) and (51), every $n$-ary tree node is typed by one and only one class
$\text{Child}_{i}$. Moreover, axioms in (52) enforce that at most one child of
every node is in the class $\text{Child}_{i}$ for every $i=1,\ldots,n$. Using
axioms in (54), we automatically infer that each child of every node is
connected to itself via some property $R_{i}$ for some $i=1,\ldots,n$. Using
axiom (55), we can infer the hasSibling relation.

$\displaystyle n\text{-BoundedTreeNode}$
$\displaystyle\sqsubseteq\text{TreeNode}$ (47) $\displaystyle
n\text{-BoundedTreeNode}$
$\displaystyle\sqsubseteq\forall\text{hasAncestor}.n\text{-BoundedTreeNode}$
(48) $\displaystyle n\text{-BoundedTreeNode}$
$\displaystyle\sqsubseteq\forall\text{hasDescendant}.n\text{-BoundedTreeNode}$
(49) $\displaystyle n\text{-BoundedTreeNode}$
$\displaystyle\sqsubseteq\text{Child}_{1}\sqcup\ldots\sqcup\text{Child}_{n}$
(50) $\displaystyle\\{\text{Child}_{i}\sqcap\text{Child}_{j}$
$\displaystyle\sqsubseteq\bot\mid 1\leq i<j\leq n\\}$ (51)
$\displaystyle\\{n\text{-BoundedTreeNode}$
$\displaystyle\sqsubseteq\mathord{\leq}1\text{hasChild}.\text{Child}_{i}\mid
1\leq i\leq n\\}$ (52) $\displaystyle n\text{-BoundedTreeNode}$
$\displaystyle\sqsubseteq\mathord{\leq}n\text{hasChild}.n\text{-BoundedTreeNode}$
(53) $\displaystyle\\{\text{Child}_{i}$ $\displaystyle\sqsubseteq\exists
R_{\text{i}}.\textsf{Self}\mid 1\leq i\leq n\\}$ (54)
$\displaystyle\\{R_{\text{i}}\circ\text{hasParent}\circ\text{hasChild}\circ
R_{\text{j}}$ $\displaystyle\sqsubseteq\text{hasSibling}\mid 1\leq i<j\leq
n\\}$ (55) Figure 9: Axioms for the $n$-bounded Tree Pattern: These need to be
added to the axioms from Figure 6

Note, though, that hasSibling is non-simple, i.e. the declaration of
irreflexivity for hasSibling from Figure 6 violates regularity. If the
ontology shall fall within OWL DL, the irreflexivity axiom should be removed.

Note also, that the approach just spelled out may not be practical for large
$n$, as the number of models to be checked, e.g. by a tableaux-based reasoner,
will increase exponentially with $n$ due to the disjunction in (50).

##  6 Conclusions

We have presented a general ontology design pattern for trees together with an
axiomatization which makes it possible to answer non-trivial competency
questions as they arise in practice. We have also presented a list pattern
derived from this tree pattern. We have furthermore discussed limitations of
OWL for the modeling of trees, and have provided an alternative axiomatization
for the more specific case that the tree is known to be $n$-bounded.

Of course, our approach is still rather straightforward and there exist cases
where our model will not suffice. For example, in the application domain
discussed in Section 2, it is often desirable to attach additional information
to parent-child relationships (i.e., edges), e.g. temporal information. This
cannot be done in our current model but would require a reification of the
edges using established techniques, and of course this change may affect the
treatment of our competency questions. This remains to be investigated.

_Acknowledgements._ Pascal Hitzler and Hilmar Lapp acknowledge support by the
National Science Foundation (NSF) under awards 1440202 “Earthcube Building
Blocks: Collaborative Proposal: GeoLink – Leveraging Semantics and Linked Data
for Data Sharing and Discovery in the Geosciences”, and DBI-1458484 “An
Ontology-Based System for Querying Life in a Post-Taxonomic Age”,
respectively.

## References

  * [1] Baader, F.: Augmenting concept languages by transitive closure of roles: An alternative to terminological cycles. In: Mylopoulos, J., Reiter, R. (eds.) Proceedings of the 12th International Joint Conference on Artificial Intelligence. Sydney, Australia, August 24-30, 1991. pp. 446–451. Morgan Kaufmann (1991), http://ijcai.org/Proceedings/91-1/Papers/069.pdf
  * [2] Calvanese, D., Eiter, T., Ortiz, M.: Regular path queries in expressive description logics with nominals. In: Boutilier, C. (ed.) IJCAI 2009, Proceedings of the 21st International Joint Conference on Artificial Intelligence, Pasadena, California, USA, July 11-17, 2009. pp. 714–720 (2009), http://ijcai.org/Proceedings/09/Papers/124.pdf
  * [3] Cellinese, N., Lapp, H.: An Ontology-Based system for querying life in a Post-Taxonomic age (2015), https://figshare.com/articles/An_Ontology_Based_System_for_Querying_Life_in_a_Post_Taxonomic_Age/1401984
  * [4] Darwin, C.: On the Origin of Species. John Murray, London, 6 edn. (1859)
  * [5] Dawson Jr., J.W.: The compactness of first-order logic:from Gödel to Lindström. History and Philosophy of Logic 14(1), 15–37 (1993)
  * [6] Driskell, A.C., Ané, C., Burleigh, J.G., McMahon, M.M., O’meara, B.C., Sanderson, M.J.: Prospects for building the tree of life from large sequence databases. Science 306(5699), 1172–1174 (12 Nov 2004), http://dx.doi.org/10.1126/science.1102036
  * [7] Dunn, C.W., Hejnol, A., Matus, D.Q., Pang, K., Browne, W.E., Smith, S.A., Seaver, E., Rouse, G.W., Obst, M., Edgecombe, G.D., Sørensen, M.V., Haddock, S.H.D., Schmidt-Rhaesa, A., Okusu, A., Kristensen, R.M., Wheeler, W.C., Martindale, M.Q., Giribet, G.: Broad phylogenomic sampling improves resolution of the animal tree of life. Nature 452(7188), 745–749 (Apr 2008), http://dx.doi.org/10.1038/nature06614
  * [8] Felsenstein, J.: Phylogenies and the comparative method. Am. Nat. 125(1), 1–15 (1985), http://www.jstor.org/stable/10.2307/2461605
  * [9] Felsenstein, J.: Inferring Phylogenies. Sinauer Associates, 2 edn. (4 Sep 2003)
  * [10] Goloboff, P., Catalano, S., Mirande, J., Szumik, C., Arias, J., Källersjö, M., Farris, J.: Phylogenetic analysis of 73 060 taxa corroborates major eukaryotic groups. Cladistics 25(3), 211 (2009), http://dx.doi.org/10.1111/j.1096-0031.2009.00255.x
  * [11] Hinchliff, C.E., Smith, S.A., Allman, J.F., Burleigh, J.G., Chaudhary, R., Coghill, L.M., Crandall, K.A., Deng, J., Drew, B.T., Gazis, R., Gude, K., Hibbett, D.S., Katz, L.A., Laughinghouse, 4th, H.D., McTavish, E.J., Midford, P.E., Owen, C.L., Ree, R.H., Rees, J.A., Soltis, D.E., Williams, T., Cranston, K.A.: Synthesis of phylogeny and taxonomy into a comprehensive tree of life. Proc. Natl. Acad. Sci. U. S. A. 112(41), 12764–12769 (13 Oct 2015), http://dx.doi.org/10.1073/pnas.1423041112
  * [12] Hitzler, P., Krisnadhi, A.: On the roles of logical axiomatizations for ontologies. In: Hitzler, P., Gangemi, A., Janowicz, K., Krisnadhi, A., Presutti, V. (eds.) Ontology Engineering with Ontology Design Patterns – Foundations and Applications, Studies on the Semantic Web, vol. 25, pp. 73–80. IOS Press (2016)
  * [13] Hitzler, P., Krötzsch, M., Parsia, B., Patel-Schneider, P.F., Rudolph, S. (eds.): OWL 2 Web Ontology Language Primer (Second Edition). W3C Recommendation (11 December 2012), http://www.w3.org/TR/owl2-primer/
  * [14] Hitzler, P., Krötzsch, M., Rudolph, S.: Foundations of Semantic Web Technologies. CRC Press/Chapman & Hall (2010)
  * [15] Huelsenbeck, J.P., Bollback, J.P., Levine, A.M.: Inferring the root of a phylogenetic tree. Syst. Biol. 51(1), 32–43 (Feb 2002), http://dx.doi.org/10.1080/106351502753475862
  * [16] Jarvis, E.D., Mirarab, S., Aberer, A.J., Li, B., Houde, P., Li, C., Ho, S.Y.W., Faircloth, B.C., Nabholz, B., Howard, J.T., Suh, A., Weber, C.C., da Fonseca, R.R., Li, J., Zhang, F., Li, H., Zhou, L., Narula, N., Liu, L., Ganapathy, G., Boussau, B., Bayzid, M.S., Zavidovych, V., Subramanian, S., Gabaldón, T., Capella-Gutiérrez, S., Huerta-Cepas, J., Rekepalli, B., Munch, K., Schierup, M., Lindow, B., Warren, W.C., Ray, D., Green, R.E., Bruford, M.W., Zhan, X., Dixon, A., Li, S., Li, N., Huang, Y., Derryberry, E.P., Bertelsen, M.F., Sheldon, F.H., Brumfield, R.T., Mello, C.V., Lovell, P.V., Wirthlin, M., Schneider, M.P.C., Prosdocimi, F., Samaniego, J.A., Vargas Velazquez, A.M., Alfaro-Núñez, A., Campos, P.F., Petersen, B., Sicheritz-Ponten, T., Pas, A., Bailey, T., Scofield, P., Bunce, M., Lambert, D.M., Zhou, Q., Perelman, P., Driskell, A.C., Shapiro, B., Xiong, Z., Zeng, Y., Liu, S., Li, Z., Liu, B., Wu, K., Xiao, J., Yinqi, X., Zheng, Q., Zhang, Y., Yang, H., Wang, J., Smeds, L., Rheindt, F.E., Braun, M., Fjeldsa, J., Orlando, L., Barker, F.K., Jønsson, K.A., Johnson, W., Koepfli, K.P., O’Brien, S., Haussler, D., Ryder, O.A., Rahbek, C., Willerslev, E., Graves, G.R., Glenn, T.C., McCormack, J., Burt, D., Ellegren, H., Alström, P., Edwards, S.V., Stamatakis, A., Mindell, D.P., Cracraft, J., Braun, E.L., Warnow, T., Jun, W., Gilbert, M.T.P., Zhang, G.: Whole-genome analyses resolve early branches in the tree of life of modern birds. Science 346(6215), 1320–1331 (12 Dec 2014), http://dx.doi.org/10.1126/science.1253451
  * [17] Krisnadhi, A., Hitzler, P.: Modeling with ontology design patterns: Chess games as a worked example. In: Hitzler, P., Gangemi, A., Janowicz, K., Krisnadhi, A., Presutti, V. (eds.) Ontology Engineering with Ontology Design Patterns: Foundations and Applications, Studies on the Semantic Web, vol. 25, pp. 3–22. IOS Press, Amsterdam (2016)
  * [18] Krisnadhi, A., Maier, F., Hitzler, P.: OWL and rules. In: Polleres, A., d’Amato, C., Arenas, M., Handschuh, S., Kroner, P., Ossowski, S., Patel-Schneider, P.F. (eds.) Reasoning Web. Semantic Technologies for the Web of Data – 7th International Summer School 2011, Galway, Ireland, August 23-27, 2011, Tutorial Lectures. Lecture Notes in Computer Science, vol. 6848, pp. 382–415. Springer (2011)
  * [19] Maddison, W.P., Donoghue, M.J., Maddison, D.R.: Outgroup analysis and parsimony. Syst. Biol. 33(1), 83–103 (1 Mar 1984), https://academic.oup.com/sysbio/article-abstract/33/1/83/1669598/Outgroup-Analysis-and-Parsimony?redirectedFrom=fulltext
  * [20] Martínez, D.C., Janowicz, K., Hitzler, P.: A logical geo-ontology design pattern for quantifying over types. In: Cruz, I.F., Knoblock, C.A., Kröger, P., Tanin, E., Widmayer, P. (eds.) SIGSPATIAL 2012 International Conference on Advances in Geographic Information Systems (formerly known as GIS), SIGSPATIAL’12, Redondo Beach, CA, USA, November 7-9, 2012\. pp. 239–248. ACM (2012)
  * [21] Michael Keesey, T.: A mathematical approach to defining clade names, with potential applications to computer storage and processing. Zool. Scr. 36(6), 607–621 (Nov 2007), http://dx.doi.org/10.1111/j.1463-6409.2007.00302.x
  * [22] O’Meara, B.C.: Evolutionary inferences from phylogenies: A review of methods. Annu. Rev. Ecol. Evol. Syst. 43(1), 267–85 (Nov 2011), http://dx.doi.org/10.1146/annurev-ecolsys-110411-160331
  * [23] de Queiroz, K., Gauthier, J.: Phylogeny as a central principle in taxonomy: Phylogenetic definitions of taxon names. Syst. Biol. 39(4), 307–322 (1 Dec 1990), https://academic.oup.com/sysbio/article-abstract/39/4/307/1646987/Phylogeny-as-a-Central-Principle-in-Taxonomy
  * [24] de Queiroz, K., Gauthier, J.: Phylogenetic taxonomy. Annu. Rev. Ecol. Syst. 23(1), 449–480 (1 Nov 1992), https://doi.org/10.1146/annurev.es.23.110192.002313
  * [25] Sereno, P.C.: The logical basis of phylogenetic taxonomy. Syst. Biol. 54(4), 595–619 (Aug 2005), http://dx.doi.org/10.1080/106351591007453
  * [26] Shimizu, C., Hitzler, P., Horridge, M.: Rendering OWL in description logic syntax. In: Proceedings of the ESWC 2017 Poster and Demo Session (2017), to appear
  * [27] Simpson, G.G.: Tempo and Mode in Evolution. Columbia University Press, New York (1949)
  * [28] Simpson, G.G.: The Major Features of Evolution. Columbia University Press, New York (1953)
  * [29] Smith, S.A., Beaulieu, J.M., Donoghue, M.J.: Mega-phylogeny approach for comparative biology: an alternative to supertree and supermatrix approaches. BMC Evol. Biol. 9, 37 (11 Feb 2009), http://dx.doi.org/10.1186/1471-2148-9-37
  * [30] Swofford, D.L., Olsen, G.J., Waddell, P.J., Hillis, D.M.: Phylogenetic inference. In: Hillis, D.M., Moritz, C., Mable, B.K. (eds.) Molecular systematics, pp. 407–514. Sinauer Associates, Inc., 2 edn. (1996), http://www.citeulike.org/group/1390/article/768694


IdentityMatrixSymb=I,DSymb=d,IntegrateDifferentialDSymb=d

# Scalar Representation of 2D Steady Vector Fields

Holger Theisel
Department of Computer Science
University of Magdeburg
Magdeburg, Germany
<EMAIL_ADDRESS>
& Michael Motejat
Department of Computer Science
University of Magdeburg
Magdeburg, Germany
<EMAIL_ADDRESS>
& Janos Zimmermann
Department of Computer Science
University of Magdeburg
Magdeburg, Germany
<EMAIL_ADDRESS>
& Christian Rössl
Department of Computer Science
University of Magdeburg
Magdeburg, Germany
<EMAIL_ADDRESS>

###### Abstract

We introduce a representation of a 2D steady vector field ${\mathbf{v}}$ by
two scalar fields $a$, $b$, such that the isolines of $a$ correspond to stream
lines of ${\mathbf{v}}$, and $b$ increases with constant speed under
integration of ${\mathbf{v}}$. This way, we get a direct encoding of stream
lines, i.e., a numerical integration of ${\mathbf{v}}$ can be replaced by a
local isoline extraction of $a$. To guarantee a solution in every case,
gradient-preserving cuts are introduced such that the scalar fields are
allowed to be discontinuous in the values but continuous in the gradient.
Along with a piecewise linear discretization and a proper placement of the
cuts, the fields $a$ and $b$ can be computed. We show several evaluations on
non-trivial vector fields.

_Keywords_ Visualization $\cdot$ scalar fields $\cdot$ vector fields

##  1 Introduction

Scalar fields and vector fields are perhaps the most common data classes in
(Scientific) Visualization. For both classes, a huge amount of visualization
techniques has been developed over the last decades. Vector fields are usually
the more complicated data class because firstly they contain more data per
point in the domain and secondly transportation issues of particles are
involved. Because of this, scalar field visualization is much further
developed than vector field visualization.

A general approach to vector field visualization is to derive one (ore more)
scalar fields from a vector field, and then apply scalar field visualization
on them. While many scalar fields have been proposed to visualize vector
fields (like vector magnitude, divergence, FTLE,…), all of them come with a
loss of information. In particular, they do not encode the transport of
particles, i.e., the location of particles after a certain integration time
cannot be computed (neither directly nor indirectly by numerical integration)
from these scalar fields.

Flow visualization has a variety of goals and applications, ranging from
understanding of fundamental flow phenomena to the analysis of concrete
simulations or measurements. We identify generic problems that frequently
occur in various applications of flow visualization:

  * •

The integration problem: many algorithms in vector field visualization are
based on the numerical integration of stream lines / particle trajectories.
While stream line integration is numerically well-understood, it is still
source of error because of error accumulation during the integration. Error
accumulation is an issue for every numerical stream lines integration
technique, no matter how involved it is.

  * •

The connectivity problem: many algorithms rely on an efficient approach to
answer the following question: given two points
${\mathbf{x}}_{1},{\mathbf{x}}_{2}$, does a streamline starting from
${\mathbf{x}}_{1}$ hit the point ${\mathbf{x}}_{2}$? If not, on which side (in
2D) and at which distance the line passes by?

These two problems are generic: they appear in many visualization techniques.
Having efficient solutions for them would affect different existing
visualization techniques.

In this paper, we follow the established path of finding scalar fields
representing vector fields. However, our new approach is to find scalar fields
that solve both the integration problem and the connectivity problem. In other
words: we search for derived scalar fields such that both integration and
connectivity can be solved by a local lookup, a procedure much faster and less
error prone than numerical stream line integration. In particular, we want to
find a scalar field such that the stream lines of the vector field correspond
to isolines of the scalar field.

Unfortunately, in general a scalar field with isolines following stream lines
of vector fields does not exist. To overcome this, we weaken our goal by
allowing gradient-preserving cuts and a special treatment of critical points.
With this, we find scalar representations of vector fields that directly
encode particle transportation. We apply our approach to introduce a strictly
local (i.e., without any numerical integration) image based flow visualization
technique.

### Notation

We consider a 2D steady vector field ${\mathbf{v}}({\mathbf{x}})$ over a
simple connected limited domain $D\subset{\mathrm{I}\\!\mbox{R}}^{2}$ with
disk topology where $\delta D$ is the boundary curve of $D$. We assume that
$\delta D$ is given as a closed differentiable parametric curve
${\mathbf{d}}(s)$. Let $\phi({\mathbf{x}},\tau)$ denote the flow map of
${\mathbf{v}}$, i.e., $\phi({\mathbf{x}},\tau)$ is the location to be landed
by integrating ${\mathbf{v}}$ starting from ${\mathbf{x}}$ over an integration
time $\tau$. Let ${\mathbf{J}}$ be the Jacobian matrix of ${\mathbf{v}}$, and
let

$\displaystyle\overline{{\mathbf{v}}}({\mathbf{x}})=\frac{{\mathbf{v}}}{\mathopen{}\left|\left|{{\mathbf{v}}}\parbox[h][0.0pt]{0.0pt}{}\right|\right|}\;,\;\overline{{\mathbf{w}}}({\mathbf{x}})=\begin{pmatrix}0&-1\\\
1&0\end{pmatrix}\cdot\overline{{\mathbf{v}}}$

be the normalized and normalized perpendicular field of ${\mathbf{v}}$.
Further, $\nabla a$ denotes the gradient of a scalar field $a$, while
$\nabla_{\perp}a=\begin{pmatrix}0&-1\\\ 1&0\end{pmatrix}\nabla a$ denotes its
co-gradient.

##  2 Problem description and analysis

Given a 2D steady vector field ${\mathbf{v}}({\mathbf{x}})$, we search for two
smooth and differentiable scalar fields $a({\mathbf{x}})$, $b({\mathbf{x}})$
with the following properties:

$\displaystyle\nabla a$ $\displaystyle\neq$ $\displaystyle{\mathbf{0}}$ (1)
$\displaystyle{\mathbf{v}}^{T}\nabla a$ $\displaystyle=$ $\displaystyle 0$ (2)
$\displaystyle{\mathbf{v}}^{T}\nabla b$ $\displaystyle=$ $\displaystyle 1$ (3)

for all ${\mathbf{x}}\in D$. (1) and (2) make sure that a stream line of
${\mathbf{v}}$ is an isoline of $a$. (3) makes sure that $b$ increases with
unit speed under integrating a stream line. This way, stream line integration
in ${\mathbf{v}}$ reduces to isocurve intersection of $a$ and $b$ by

$a(\phi({\mathbf{x}},\tau))=a({\mathbf{x}})\;\;\;,\;\;\;b(\phi({\mathbf{x}},\tau))=b({\mathbf{x}})+\tau.$
(4)

Unfortunately, a field $a$ fulfilling (1), (2) does in general not exist. The
simplest counterexample is the linear field
${\mathbf{v}}({\mathbf{x}})=(x,y)^{T}$ for which no smooth field $a$ can
exist. In general, if ${\mathbf{v}}$ is divergence-free, a field $a$ exists:
the stream function. Also for the field $b$, existence is not ensured: for
divergence-free ${\mathbf{v}}$, a contradiction in $b$ is created on a closed
stream line after one turn.

In order to cope with the problem, we allow a certain weakening of the
conditions for $a,b$ that allow a unique solution but still allow to solve the
integration and connectivity problem by an isovalue lookup. In particular, we
introduce two concepts: gradient preserving cuts and a special treatment of
areas around critical points.

##  3 Related work

We divide the review of existing work in four parts: vector field
visualization, scalar field visualization, scalar field representation of
vector fields, and finding optimal cuts in shape processing.

#### Vector field visualization

Vector field visualization is one of the core topics in Scientific
Visualization. While in many cases the vector data describe flow phenomena,
other effects represented by vector field data exist as well, such as
dynamical systems or magnetic fields. A variety of techniques for vector field
visualization has been developed, ranging from texture based techniques
Laramee et al. (2004) over feature extraction Post et al. (2003); Günther and
Theisel (2017), topological methods Pobitzer et al. (2011a); Salzbrunn et al.
(2008) until illustrative techniques Brambilla et al. (2012). Most relevant
for our work are topological techniques because they develop a partition of
the vector fields in to critical points and separatrices of of relevance for
the new approaches.

Topological methods for 2D vector fields have been introduced to the
visualization community in Helman and Hesselink (1989). Later they were
extended to higher order critical points Scheuermann et al. (1998), boundary
switch points de Leeuw and van Liere (1999a), and closed separatrices
Wischgoll and Scheuermann (2001). In addition, topological methods have been
applied to simplify de Leeuw and van Liere (1999a, b); Tricoche et al. (2000,
2001), smooth Westermann et al. (2001), compress Lodha et al. (2000); Suresh
Lodha and Renteria (2003); Theisel et al. (2003a) and construct Theisel
(2002); Weinkauf et al. (2004a) vector fields. 3D topological feature are
considered in Globus et al. (1991); Helman and Hesselink (1991); Mahrous et
al. (2003, 2004); Theisel et al. (2003b); Weinkauf et al. (2004b). State-of-
the-Art-Reports on topological methods for flow visualization can be found in
Laramee et al. (2007); Pobitzer et al. (2011b); Wang et al. (2016); Heine et
al. (2016).

Topological methods can be applied only to steady vector fields because they
require integration over an infinitely long integration time. For unsteady
fields, Lagrangian Coherent Structures (LCS) have been established to find
regions of homogeneous flow behavior. One of the most prominent approaches for
this is the computation of ridge structures in FTLE fields, as introduced by
Haller Haller (2001); Haller and Yuan (2000). To consider spatial separation
only, Pobitzer et al. Pobitzer et al. (2012) weighted FTLE values by their
angle to the separation direction. FTLE ridges were proposed for a variety of
applications Haller (2002); Lekien et al. (2005); Shadden et al. (2009);
Weldon et al. (2008). Shadden et al. Shadden et al. (2005) showed that ridges
of FTLE are approximate material structures, i.e., they converge to material
structures for increasing integration times. This fact was used in Sadlo and
Weiskopf (2010); Uffinger et al. (2013) to extract topological structures and
in Lipinski and Mohseni (2010) to accelerate the FTLE computation in 2D flows.
Also in the visualization community, different approaches have been proposed
to increase performance, accuracy and usefulness of FTLE as a visualization
tool Günther et al. (2016); Garth et al. (2009, 2007); Sadlo and Peikert
(2009, 2007); Sadlo et al. (2011).

In recent years approaches have evolved that aim at finding suitable moving
frames of the underlying coordinate system to study the flow Bhatia et al.
(2014); Wiebel et al. (2007) or develop Galilean invariant detectors directly
Bujack et al. (2016). This way, finite-time studies of time-dependent fields
is lead back to a topological analysis of a derived steady field.

We also note that discrete versions of vector field topology have been
developed based on either Forman‘s discrete Morse theory Forman (2001);
Reininghaus and Hotz (2011) or Morse decomposition Mischaikow et al. (2007).
Other approaches use edge maps Bhatia et al. (2012) or robustness
considerations for critical points treatment Skraba et al. (2016); Wang et al.
(2013).

#### Scalar field visualization

Scalar fields are another well-researched standard data class in Scientific
Visualization. A variety of techniques has been developed for scalar fields,
ranging from isosurface extraction over direct volume rendering to feature
extraction. In particular, topological features have been proven successful.
We mention Morse-Smale complexes and the Reeb graph.

The Morse-Smale complex is a topological structure representing the gradient-
flow behavior of a scalar field. Of particular interest for visualization are
combinatorial approaches based on piecewise linear scalar fields as introduced
in Edelsbrunner et al. (2001) and later extended in several ways Bremer et al.
(2004); Edelsbrunner et al. (2003); Gyulassy et al. (2005); Lewiner et al.
(2004); Gyulassy et al. (2015, 2007). The combinatorial approach makes the
extraction of Morse-Smale complexes relevant because it allows effective
algorithms with guarantees about their correctness.

The Reeb graph considers components of contours and their topological changes.
They have been applied to control the removal of topological features Cignoni
et al. (2000); Carr et al. (2004); Guskov and Wood (2001); Takahashi et al.
(2004); Carr et al. (2003); Tierny et al. (2012).

#### Vector field approximation by scalar fields

Scalar fields are simpler structures than vector fields. So, it is not
surprising that research came up with approaches to represent vector fields
(in particular flow fields and vorticity fields) as scalar fields. The Clebsch
map Clebsch (1859) represents divergence-free velocity and vorticity fields as
a certain combination of gradients of scalar fields. Such representations have
been used to visualize Kotiuga (1991), analyze Jeong and Hussain (1995) and
simplify flows Brandenburg (2010); He and Yang (2016, 2016). Unfortunately,
such representations cannot be exact in the general case Graham and Henyey
(2000), resulting in either approximate representations Chern et al. (2017) or
applications restricting to certain subclasses of divergence-free vector
fields Angelidis and Singh (2007); von Funck et al. (2006).

#### Optimal cuts on shapes

Many algorithms in Geometry processing require open surfaces with well-defined
boundaries, such as surface parametrization Zigelman et al. (2002); Hormann et
al. (2008) or quad-remeshing Ebke et al. (2016); Campen and Kobbelt (2014).
For closed input surfaces, cutting algorithms are necessary. Since the
placement of the cuts influences the result of the algorithms, "optimal" cuts
are searched. Several criteria for optimality have been proposed and applied
Erickson and Har-Peled (2002).

##  4 Solution on simple vector fields

In this section, we provide a solution for $a$, $b$ for simple vector fields.

###### Definition 1

A vector field ${\mathbf{v}}$ to be simple if it fulfills the following
property: for every ${\mathbf{x}}\in D$ we reach the boundary after a finite
integration time both in forward and backward integration.

From this it follows that ${\mathbf{v}}$ has neither critical points nor
closed orbits.

For simple vector fields, the search for $a,b$ can be interpreted as a domain
transformation of ${\mathbf{v}}$ in the domain $D$ to the constant vector
field $(0,1)^{T}$ in the new domain $D^{\prime}$. Figure 1 gives an
illustration.

Figure 1: Finding the fields $a,b$ can be interpreted as searching for a
domain transformation of ${\mathbf{v}}$ to $(0,1)^{T}$.

Note that (1)–(3) does not give unique solutions for $a,b$. Among all
solutions for $a,b$, we search for the ones the with

$\displaystyle\int_{D}(\|\nabla a\|-\|{\mathbf{v}}\|)^{2}d{\mathbf{x}}$
$\displaystyle\to$ $\displaystyle\min$ (5) $\displaystyle\int_{D}\|\nabla
b\|^{2}d{\mathbf{x}}$ $\displaystyle\to$ $\displaystyle\min.$ (6)

Given a point ${\mathbf{x}}\in D$, let $\tau_{0}({\mathbf{x}})$,
$\tau_{1}({\mathbf{x}})$ be the integration time to reach the boundary of $D$
starting from ${\mathbf{x}}$ in backward and forward direction respectively,
i.e.:

$\displaystyle\tau_{0}({\mathbf{x}})\leq 0\leq\tau_{1}({\mathbf{x}})$ (7)
$\displaystyle\phi({\mathbf{x}},\tau_{0}({\mathbf{x}})),\phi({\mathbf{x}},\tau_{1}({\mathbf{x}}))\in\delta
D$ (8) $\displaystyle\phi({\mathbf{x}},\tau)\notin\delta D\mbox{ for
}\tau\in\;]\tau_{0}({\mathbf{x}}),\tau_{1}({\mathbf{x}})[.$ (9)

Further, we define the end points of the integration from ${\mathbf{x}}$ as
${\mathbf{d}}_{0}({\mathbf{x}})=\phi({\mathbf{x}},\tau_{0}({\mathbf{x}}))$ and
${\mathbf{d}}_{1}({\mathbf{x}})=\phi({\mathbf{x}},\tau_{1}({\mathbf{x}}))$.
Also, we define the boundary points in terms of the parametrization $s$ for
the boundary curve ${\mathbf{s}}(s)$:
$s_{0}({\mathbf{x}}),s_{1}({\mathbf{x}})$ are defined by

${\mathbf{d}}(s_{0}({\mathbf{x}}))={\mathbf{d}}_{0}({\mathbf{x}})\;\;\;,\;\;\;{\mathbf{d}}(s_{1}({\mathbf{x}}))={\mathbf{d}}_{1}({\mathbf{x}}).$
(10)

Figure 2 gives an illustration.

Figure 2: Definition of $\tau_{0}({\mathbf{x}}),\tau_{1}({\mathbf{x}})$,
${\mathbf{d}}_{0}({\mathbf{x}}),{\mathbf{d}}_{1}({\mathbf{x}})$.

Since ${\mathbf{v}}$ is simple, there is a unique
$\tau_{0},\tau_{1},{\mathbf{d}}_{0},{\mathbf{d}}_{1},s_{0},s_{1}$ for every
${\mathbf{x}}\in D$. Also, (4) gives that it is sufficient to compute $a,b,$
on the boundary of $D$ only by

$\displaystyle a({\mathbf{x}})$ $\displaystyle=$ $\displaystyle
a({\mathbf{d}}_{0}({\mathbf{x}}))=a({\mathbf{d}}_{1}({\mathbf{x}}))$ (11)
$\displaystyle b({\mathbf{x}})$ $\displaystyle=$ $\displaystyle
b({\mathbf{d}}_{0}({\mathbf{x}}))-\tau_{0}({\mathbf{x}})=b({\mathbf{d}}_{1}({\mathbf{x}}))-\tau_{1}({\mathbf{x}})$
(12)

###  4.1 Computing $a$, $b$

The computation of both $a$ and $b$ is done in the following steps:

  1. 1.

Compute $a_{s}(s)=\frac{d\;a({\mathbf{d}}(s))}{d\;s}$, and
$b_{s}(s)=\frac{d\;b({\mathbf{d}}(s))}{d\;s}$, i.e., the derivatives of $a,b$
along the boundary curve.

  2. 2.

Compute $a(s)=a({\mathbf{d}}(s))$, $b(s)=b({\mathbf{d}}(s))$ by integrating
$a_{s}(s),b_{s}(s)$, respectively.

  3. 3.

Compute $a({\mathbf{x}})$, $b({\mathbf{x}})$ in the inner domain by applying
(11), (12).

### Computing $a$

For ${\mathbf{x}}\in D$, we compute the separating function Friederici et al.
(2017) along the stream as

$s_{l}({\mathbf{x}},\tau)=\int_{\tau_{0}({\mathbf{x}})}^{\tau}\overline{{\mathbf{w}}}(\phi)^{T}{\mathbf{J}}(\phi)\;\overline{{\mathbf{w}}}(\phi)\;dr$
(13)

with $\phi=\phi({\mathbf{x}},t)$ that describes the behavior of "adjacent"
isolines in $a$. We search for the scalar $s_{m}({\mathbf{x}})$ minimizing

$\int_{\tau_{0}({\mathbf{x}})}^{\tau_{1}({\mathbf{x}})}\left(e^{-s_{l}({\mathbf{x}},\tau)-s_{m}({\mathbf{x}})}-\|{\mathbf{v}}(\phi({\mathbf{x}},\tau))\|\right)^{2}d\tau\to\min.$
(14)

Fortunately, this has a closed form solution for $s_{m}({\mathbf{x}})$:

$s_{m}({\mathbf{x}})=\ln\left(\frac{\int_{\tau_{0}({\mathbf{x}})}^{\tau_{1}({\mathbf{x}})}(e^{-s_{l}({\mathbf{x}},\tau)})^{2}d\tau}{\int_{\tau_{0}({\mathbf{x}})}^{\tau_{1}({\mathbf{x}})}\|{\mathbf{v}}(\phi({\mathbf{x}},\tau))\|e^{-s_{l}({\mathbf{x}},\tau)}d\tau}\right).$
(15)

Finally, we compute

$s({\mathbf{x}})=s_{l}({\mathbf{x}},0)+s_{m}({\mathbf{x}}).$ (16)

The field $s({\mathbf{x}})$ steers the gradient of $a$ by

$\nabla a=e^{-s}\overline{{\mathbf{w}}}.$ (17)

### Computing $b$

If $b$ is set on a stream line, we need to set it on the "adjacent" stream
line as well. In other words, we need to study and optimize the behavior of
$\nabla b$. It turns out that – similar to $a$ – we have one degree of freedom
to steer $\nabla b$ along the stream line. In the best case we would have
$(\nabla a)^{T}\nabla b=0$. However, if we set this property in
${\mathbf{x}}$, it does not advect along the stream line.

At a point ${\mathbf{x}}$, we consider a point ${\mathbf{y}}$ in its
neighborhood and observe ${\mathbf{y}}-{\mathbf{x}}$ under the local
(changing) coordinate system
$(\overline{{\mathbf{v}}},\overline{{\mathbf{w}}})$:

$p=\overline{{\mathbf{v}}}^{T}({\mathbf{y}}-{\mathbf{x}})\;,\;q=\overline{{\mathbf{w}}}^{T}({\mathbf{y}}-{\mathbf{x}})\;,\;r=\frac{p}{q}=\tan\alpha.$
(18)

Figure 3 gives an illustration of the setup.

Figure 3: setup of local moving coordinate system.

We assume that $({\mathbf{y}}-{\mathbf{x}})$ is the direction of the co-
gradient of $b$. We observe how, $p,q,r$ behave over stream line integration:

$\displaystyle\frac{dp}{d\tau}$ $\displaystyle=$
$\displaystyle\overline{{\mathbf{v}}}^{T}{\mathbf{J}}\overline{{\mathbf{v}}}\,p+(\overline{{\mathbf{v}}}^{T}{\mathbf{J}}\overline{{\mathbf{w}}}+\overline{{\mathbf{w}}}^{T}{\mathbf{J}}\overline{{\mathbf{v}}})\,q$
(19) $\displaystyle\frac{dq}{d\tau}$ $\displaystyle=$
$\displaystyle\overline{{\mathbf{w}}}^{T}{\mathbf{J}}\overline{{\mathbf{w}}}\,q$
(20) $\displaystyle\frac{dr}{d\tau}$ $\displaystyle=$
$\displaystyle(\overline{{\mathbf{v}}}^{T}{\mathbf{J}}\overline{{\mathbf{v}}}-\overline{{\mathbf{w}}}^{T}{\mathbf{J}}\overline{{\mathbf{w}}})\,r+(\overline{{\mathbf{v}}}^{T}{\mathbf{J}}\overline{{\mathbf{w}}}+\overline{{\mathbf{w}}}^{T}{\mathbf{J}}\overline{{\mathbf{v}}}).$
(21)

With (21) we can compute the optimal $r$ along a stream line by

$\int_{\tau_{0}({\mathbf{x}})}^{\tau_{1}({\mathbf{x}})}(r(\phi({\mathbf{x}},\tau)))^{2}d\tau\to\min.$
(22)

This should be linear in $r$. Note again that $r$ defines the direction of the
co-gradient of $b$. Together with (3), $\nabla b$ is uniquely defined.

##  5 Gradient-preserving cuts

Keep in mind that the approach to compute $a$ and $b$ in section 4 works only
on simple vector fields. To make it applicable to every vector field, we
introduce gradient-preserving cuts.

In the following we give a definition of gradient-preserving cuts of a 2D
scalar field along a cutting curve ${\mathbf{c}}(t)$:

###### Definition 2

Given is a 2D scalar field $s(x,y)$ and a regularly parametrized curve
${\mathbf{c}}(t)$ in the domain of $s$. We assume $s$ to be at least $C^{1}$
continuous outside ${\mathbf{c}}$. The field $s$ has a gradient-preserving cut
along ${\mathbf{c}}$ if

  1. 1.

$s$ is undefined on ${\mathbf{c}}$.

  2. 2.

$\lim_{{\mathbf{x}}\to{\mathbf{c}}(t),left}s({\mathbf{x}})-\lim_{{\mathbf{x}}\to{\mathbf{c}}(t),right}s({\mathbf{x}})=h$

  3. 3.

$\lim_{{\mathbf{x}}\to{\mathbf{c}}(t),left}\nabla
s({\mathbf{x}})=\lim_{{\mathbf{x}}\to{\mathbf{c}}(t),right}\nabla
s({\mathbf{x}})$

where $\lim_{{\mathbf{x}}\to{\mathbf{c}}(t),left}$ considers all points
${\mathbf{x}}$ being "left" of the curve, i.e.,
$\det(\dot{{\mathbf{c}}}(t),({\mathbf{x}}-{\mathbf{c}}(t))>0$ and
$\dot{{\mathbf{c}}}$ is the tangent vector of ${\mathbf{c}}$. Further, $h$ is
a non-zero constant.

Definition 2 states that along ${\mathbf{c}}(t)$, $s$ has a well-defined
discontinuity but nevertheless a continuous gradient. Figure 4 shows an
example of a gradient-preserving cut of a 1D function $s(x)$.

Figure 4: left: 1D field with gradient-preserving cut; right: its derivative.

Figure 5 shows a 2D gradient-preserving cut in a scalar field as hight field
along with isolines. Note that the isolines appear continuously even though
the field has a cut.

Figure 5: left: 2D field with gradient-preserving cut as height field; right:
isocontours

Since scalar fields with gradient-preserving cuts are gradient continuous,
they have continuous gradient and co-gradient fields. Hence, the potential
advances still hold under slight modifications of the algorithms: for
isocontouring approaches to integrate a co-gradient field, the consideration
of an offset $h$ of isovalues across the cutting curve is necessary. For an
integration of a gradient ascent/descent, a special treatment across the
cutting curve is necessary.

##  6 Treatment of critical points

Consider the 2D linear vector field
${\mathbf{v}}({\mathbf{x}})={\mathbf{J}}\,{\mathbf{x}}$ which has a critical
point at the origin. Depending on an eigenanalysis of the Jacobian
${\mathbf{J}}$, we discuss the following cases (let $\lambda_{1},\lambda_{2}$
be the eigenvalues of ${\mathbf{J}}$ and ${\mathbf{r}}_{1},{\mathbf{r}}_{2}$
the corresponding eigenvectors):

Case 1: ${\mathbf{v}}$ has a saddle, i.e., $\lambda_{1}<0<\lambda_{2}$. In
this case it is a straightforward exercise in algebra to that the scalar field

$s({\mathbf{x}})=\det({\mathbf{x}},{\mathbf{r}}_{1})^{-\lambda_{1}}\det({\mathbf{x}},{\mathbf{r}}_{2})^{\lambda_{2}}$
(23)

with $p^{q}=\mbox{sign}(p)\,\|p\|^{q}$ fullfills 2., i.e.,
${\mathbf{v}}^{T}\nabla s=0$. Note that (23) does not even need a gradient-
preserving cut to fullfill 2. Figure 6 illustrates this for the example field
${\mathbf{v}}_{1}=\left(\begin{array}[]{cc}-2&\frac{3}{2}\\\
0&1\end{array}\right){\mathbf{x}}$ by showing the LIC image of ${\mathbf{v}}$
(left), $s$ as height field (middle), and isocontours of $s$ (right).

Figure 6:  Linear vector field ${\mathbf{v}}_{1}$ containing a saddle; LIC
image of ${\mathbf{v}}_{1}$ (left), $s$ as height field (middle), isocontours
of $s$ (right).

Case 2: ${\mathbf{v}}$ has a source or a sink with real eigenvalues of
${\mathbf{v}}$, i.e., $\lambda_{1}\leq\lambda_{2}<0$ or
$0<\lambda_{1}\leq\lambda_{2}$. In this case the scalar field

$s({\mathbf{x}})=\arctan\left(\det({\mathbf{x}},{\mathbf{r}}_{1})^{-\lambda_{1}}\det({\mathbf{x}},{\mathbf{r}}_{2})^{\lambda_{2}}\right)$
(24)

fulfills 2. Moreover, here we have a gradient-preserving cut starting from the
origin that is due to the arctan function. Figure 7 illustrates this for the
vector field ${\mathbf{v}}_{2}=\left(\begin{array}[]{cc}2&-\frac{1}{2}\\\
0&1\end{array}\right){\mathbf{x}}$.

Figure 7: Linear vector field ${\mathbf{v}}_{2}$ with two positive real
eigenvalues of ${\mathbf{J}}$; LIC image of ${\mathbf{v}}_{2}$ (left), $s$ as
height field (middle), isocontours of $s$ (right).

Case 3: ${\mathbf{v}}$ is a source or a sink with imaginary eigenvalues of
${\mathbf{J}}$, i.e., a swirling behavior around the critical point. In this
case, the scalar field

$s({\mathbf{x}})=\alpha\arctan\left(\frac{{\mathbf{a}}^{T}{\mathbf{x}}}{\beta\,{\mathbf{b}}^{T}{\mathbf{x}}}\right)+\beta\,\ln({\mathbf{x}}^{T}\,{\mathbf{C}}\,{\mathbf{x}})$
(25)

with

$\displaystyle{\mathbf{R}}=\left(\begin{array}[]{cc}0&-1\\\
1&0\end{array}\right)\;\;\;,\;\;\;\widehat{{\mathbf{J}}}=\frac{1}{2}\left({\mathbf{R}}\,{\mathbf{J}}+({\mathbf{R}}\,{\mathbf{J}})^{T})\right)\;\;\;,\;\;\;\alpha=\mbox{Trace}({\mathbf{J}})$
(28)
$\displaystyle\beta=\sqrt{\|\det\widehat{{\mathbf{J}}}\|}\;\;\;,\;\;\;{\mathbf{a}}^{T}=(1,0)\,\widehat{{\mathbf{J}}}\;\;\;,\;\;\;{\mathbf{b}}^{T}=(1,0)\,{\mathbf{R}}\;\;\;,\;\;\;{\mathbf{C}}=\widehat{{\mathbf{J}}}.$

Figure 8 illustrates this for the field
${\mathbf{v}}_{3}=\left(\begin{array}[]{cc}1&4\\\
-2&3\end{array}\right){\mathbf{x}}$.

Figure 8: Vector field ${\mathbf{v}}_{3}$ with imaginary eigenvalues of the
Jacobian; LIC image of (left), $s$ as height field (middle), isocontours of
$s$ (right).

Based on these cases, we formulate the following:

###### Corollary 1

Every 2D linear vector field can be described as co-gradient field of a scalar
field $a$ with a gradient-preserving cut.

##  7 Placement of the cuts

Cuts must be placed such that all critical points are covered and the vector
field ${\mathbf{v}}$ is divided into a set of simple vector fields. To this
end, we set the cuts manually by defining a polygon connecting all critical
points and to connect to one additional point at the boundary of the domain. A
similar approach for defining cuts has been applied in Theisel et al. (2004)
to compute isolated closed stream lines.

##  8 Discretization and solution

We assume a piecewise linear vector field over a triangulation of the domain
$D$. We search for piecewise scalar fields $a$, $b$ over the same
triangulation, i.e., the unknown scalar values $a$, $b$ at the vertices of the
triangulation. The general algorithm is as follows:

  1. 1.

Set the cuts in the domain $D$.

  2. 2.

Compute $a$, $b$ along the boundary of $D$, i.e.,

$a(s)=a({\mathbf{d}}(s))\;\;\;,\;\;\;b(s)=b({\mathbf{d}}(b)).$ (29)

  3. 3.

For every inner point ${\mathbf{x}}$ on the triangulation, compute
$a({\mathbf{x}})$ and $b({\mathbf{x}})$ by applying (11), (12).

More information is necessary for step 2. We compute all boundary switch
points Weinkauf et al. (2004c) on the boundary of $D$ that divide the boundary
in alternating areas of inflow and outflow, respectively. We consider outflow
areas only and compute $a$, $b$ by applying (13)–(22). For inflow areas, the
corresponding values $a$, $b$ are computed by applying (11), (12),
respectively.

##  9 Results

We apply our approach to a number of test fields. Figure 9 shows a piecewise
linear vector field with 3 swirling sources and a saddle. Figure 9(right)
shows a LIC image of the field as well as the cuts. Figure 9(left) shows the
computed piecewise linear field $a$ as height field. Also the underlying
triangulation for the piecewise linear fields are shown. The projected lines
in figure 9(left) show isolines of $a$ that correspond to stream lines of
${\mathbf{v}}$. Note that we can see a clear discontinuity of $a$ at the cuts,
but no discontinuities are visible in the isolines, which is due to the
gradient-preservation property.

Figure 9: Vector field with 3 swirling sources and a saddle; 3d image of the
constructed scalar field (left), LIC of the vector field (right).

Figure 10 shows the approach for a vector field with 2 sources, 2 sinks and 2
saddles.

Figure 10: Vector field with 2 sources, 2 sinks and 2 saddles; 3d image of the
constructed scalar field (left), LIC of the vector field (right).

##  10 Conclusion

We presented a principal solution to represent 2D vector fields as scalar
fields. Further research is necessary concerning the comparison of accuracy of
isoline extraction of $a$ vs. a standard numerical stream line integration of
${\mathbf{v}}$. Also, further and more complex datas sets need to be
evaluated.

An extension to 2D time-dependent as well as to 3D vector fields is non-
trivial, but there is no fundamental reason that prevents the extension. We
leave this extension to future research.

## Acknowledgements

This work was partially supported by DFG grant TH 692/17-1.

## References

  * Laramee et al. [2004] Robert S. Laramee, Helwig Hauser, Helmut Doleisch, Benjamin Vrolijk, Frits H. Post, and Daniel Weiskopf.  The state of the art in flow visualization: Dense and texture-based techniques.  _Computer Graphics Forum_ , 23(2):203–221, 2004\.  ISSN 1467-8659.  doi:10.1111/j.1467-8659.2004.00753.x.  URL http://dx.doi.org/10.1111/j.1467-8659.2004.00753.x.
  * Post et al. [2003] Frits H. Post, Benjamin Vrolijk, Helwig Hauser, Robert S. Laramee, and Helmut Doleisch.  The State of the Art in Flow Visualisation: Feature Extraction and Tracking.  _Computer Graphics Forum_ , 2003.  ISSN 1467-8659.  doi:10.1111/j.1467-8659.2003.00723.x.
  * Günther and Theisel [2017] Tobias Günther and Holger Theisel.  The state of the art in vortex extraction.  _Computer Graphics Forum_ , 2017.
  * Pobitzer et al. [2011a] Armin Pobitzer, Ronald Peikert, Raphael Fuchs, Benjamin Schindler, Alexander Kuhn, Holger Theisel, Kresimir Matkovic, and Helwig Hauser.  The State of the Art in Topology?Based Visualization of Unsteady Flow.  _Computer Graphics Forum_ , 2011a.  ISSN 1467-8659.  doi:org:443/handle/10.1111/v30i6pp1789-1811.
  * Salzbrunn et al. [2008] T. Salzbrunn, H. Jänicke, T. Wischgoll, and Gerik Scheuermann.  The state of the art in flow visualization: Partition-based techniques.  In H. Hauser, S. Strassburger, and H. Theisel, editors, _Simulation and Visualization 2008_ , pages 75–92. SCS Publishing House, SCS Publishing House, 2008.
  * Brambilla et al. [2012] Andrea Brambilla, Robert Carnecky, Ronald Peikert, Ivan Viola, and Helwig Hauser.  Illustrative Flow Visualization: State of the Art, Trends and Challenges.  In Marie-Paule Cani and Fabio Ganovelli, editors, _Eurographics 2012 - State of the Art Reports_. The Eurographics Association, 2012.  doi:10.2312/conf/EG2012/stars/075-094.
  * Helman and Hesselink [1989] James L. Helman and Lambertus Hesselink.  Representation and display of vector field topology in fluid flow data sets.  _IEEE Computer_ , 22(8):27–36, 1989.
  * Scheuermann et al. [1998] Gerik Scheuermann, Heinz Krüger, Martin Menzel, and Alyn P. Rockwood.  Visualizing non-linear vector field topology.  _IEEE Transactions on Visualization and Computer Graphics_ , 4(2):109–116, 1998.
  * de Leeuw and van Liere [1999a] Wim de Leeuw and Robert van Liere.  Collapsing flow topology using area metrics.  In _Proc. IEEE Visualization ’99_ , pages 149–354, 1999a.
  * Wischgoll and Scheuermann [2001] Thomas Wischgoll and Gerik Scheuermann.  Detection and visualization of closed streamlines in planar flows.  _IEEE Transactions on Visualization and Computer Graphics_ , 7(2):165–172, 2001.
  * de Leeuw and van Liere [1999b] Wim de Leeuw and Robert van Liere.  Visualization of global flow structures using multiple levels of topology.  In _Data Visualization 1999. Proc. VisSym 99_ , pages 45–52, 1999b.
  * Tricoche et al. [2000] Xavier Tricoche, Gerik Scheuermann, and Hans Hagen.  A topology simplification method for 2D vector fields.  In _Proc. IEEE Visualization_ , pages 359–366, 2000.
  * Tricoche et al. [2001] Xavier Tricoche, Gerik Scheuermann, and Hans Hagen.  Continuous topology simplification of planar vector fields.  In _Proc. IEEE Visualization_ , pages 159 – 166, 2001.
  * Westermann et al. [2001] Rüdiger Westermann, Christopher Johnson, and Thomas Ertl.  Topology-preserving smoothing of vector fields.  _IEEE Transactions on Visualization and Computer Graphics_ , 7(3):222–229, 2001.
  * Lodha et al. [2000] Suresh K. Lodha, Jose C. Renteria, and Krishna M. Roskin.  Topology preserving compression of 2D vector fields.  In _Proc. IEEE Visualization_ , pages 343–350, 2000.
  * Suresh Lodha and Renteria [2003] Nikolai M. Faaland Suresh Lodha and Jose C. Renteria.  Topology preserving top-down compression of 2D vector fields using bintree and triangular quadtrees.  _IEEE Transactions on Visualization and Computer Graphics_ , 9(4):433–442, 2003.
  * Theisel et al. [2003a] Holger Theisel, Christian Rössl, and Hans-Peter Seidel.  Compression of 2D vector fields under guaranteed topology preservation.  _Computer Graphics Forum (Eurographics 2003)_ , 22(3):333–342, 2003a.
  * Theisel [2002] Holger Theisel.  Designing 2D vector fields of arbitrary topology.  _Computer Graphics Forum (Eurographics 2002)_ , 21(3):595–604, 2002.
  * Weinkauf et al. [2004a] Tino Weinkauf, Holger Theisel, Hans-Christian Hege, and Hans-Peter Seidel.  Topological construction and visualization of higher order 3D vector fields.  _Computer Graphics Forum (Proc. Eurographics)_ , 23(3):469–478, 2004a.
  * Globus et al. [1991] Al Globus, Creon Levit, and Tom A. Lasinski.  A tool for visualizing the topology of three-dimensional vector fields.  In _Proc. IEEE Visualization_ , pages 33–40, 1991.
  * Helman and Hesselink [1991] James L. Helman and Lambertus Hesselink.  Visualizing vector field topology in fluid flows.  _IEEE Computer Graphics and Applications_ , 11:36–46, 1991\.
  * Mahrous et al. [2003] Karim M. Mahrous, Janine C. Bennett, Bernd Hamann, and Kenneth I. Joy.  Improving topological segmentation of three-dimensional vector fields.  In _Data Visualization (Proc. VisSym)_ , pages 203–212, 2003.
  * Mahrous et al. [2004] Karim M. Mahrous, Janine C. Bennett, Gerik Scheuermann, Bernd Hamann, and Kenneth I. Joy.  Topological segmentation in three-dimensional vector fields.  _IEEE Transactions on Visualization and Computer Graphics_ , 10(2):198–205, 2004.
  * Theisel et al. [2003b] Holger Theisel, Tino Weinkauf, Hans-Christian Hege, and Hans-Peter Seidel.  Saddle connectors - an approach to visualizing the topological skeleton of complex 3D vector fields.  In _Proc. IEEE Visualization 2003_ , pages 225–232, 2003b.
  * Weinkauf et al. [2004b] Tino Weinkauf, Holger Theisel, Hans-Christian Hege, and Hans-Peter Seidel.  Boundary switch connectors for topological visualization of complex 3D vector fields.  In _Data Visualization (Proc. VisSym)_ , pages 183–192, 2004b.
  * Laramee et al. [2007] Robert S. Laramee, Helwig Hauser, Lingxiao Zhao, and Frits H. Post.  Topology-based flow visualization, the state of the art.  In Helwig Hauser, Hans Hagen, and Holger Theisel, editors, _Topology-based Methods in Visualization_ , Mathematics and Visualization, pages 1–19. Springer, 2007.  ISBN 978-3-540-70822-3.  doi:10.1007/978-3-540-70823-0_1.  URL http://dx.doi.org/10.1007/978-3-540-70823-0_1.
  * Pobitzer et al. [2011b] Armin Pobitzer, Ronald Peikert, Raphael Fuchs, Benjamin Schindler, Alexander Kuhn, Holger Theisel, Kresimir Matkovic, and Helwig Hauser.  The state of the art in topology-based visualization of unsteady flow.  _Computer Graphics Forum_ , 30(6):1789–1811, 2011b.  ISSN 1467-8659.
  * Wang et al. [2016] Wentao Wang, Wenke Wang, and Sikun Li.  From numerics to combinatorics: a survey of topological methods for vector field visualization.  _Journal of Visualization_ , pages 1–26, 2016.
  * Heine et al. [2016] Christian Heine, Heike Leitte, Mario Hlawitschka, Federico Iuricich, Leila De Floriani, Gerik Scheuermann, Hans Hagen, and Christoph Garth.  A survey of topology-based methods in visualization.  In _Computer Graphics Forum_ , volume 35, pages 643–667. Wiley Online Library, 2016.
  * Haller [2001] George Haller.  Distinguished material surfaces and coherent structures in three-dimensional fluid flows.  _Physica D_ , 149:248–277, 2001.
  * Haller and Yuan [2000] George Haller and Guo-Cheng Yuan.  Lagrangian coherent structures and mixing in two-dimensional turbulence.  _Physica D_ , 147(3-4):352–370, 2000.  ISSN 0167-2789.  doi:http://dx.doi.org/10.1016/S0167-2789(00)00142-1.
  * Pobitzer et al. [2012] Armin Pobitzer, Ronald Peikert, Raphael Fuchs, Holger Theisel, and Helwig Hauser.  Filtering of FTLE for visualizing spatial separation in unsteady 3D flow.  In _Topological Methods in Data Analysis and Visualization II_ , pages 237–253. Springer, 2012.
  * Haller [2002] George Haller.  Lagrangian coherent structures from approximate velocity data.  _Physics of Fluids_ , 14(6), 2002.  doi:http://dx.doi.org/10.1063/1.1477449.
  * Lekien et al. [2005] Francois Lekien, Chad Coulliette, Arthur J. Mariano, Edward H. Ryan, Lynn K. Shay, George Haller, and Jerry Marsden.  Pollution release tied to invariant manifolds: A case study for the coast of Florida.  _Physica D_ , 210(1):1–20, 2005.
  * Shadden et al. [2009] Shawn C. Shadden, Francois Lekien, Jeffrey D. Paduan, Francisco P. Chavez, and Jerrold E. Marsden.  The correlation between surface drifters and coherent structures based on high-frequency radar data in Monterey Bay.  _Deep Sea Research Part II: Topical Studies in Oceanography_ , 56(3-5):161–172, 2009.  ISSN 0967-0645.  doi:DOI: 10.1016/j.dsr2.2008.08.008.  URL http://www.sciencedirect.com/science/article/B6VGC-4TJ1HH1-3/2/9f098e9e2684e5cd8f53e69ab3c59c26.
  * Weldon et al. [2008] Matthew J. Weldon, Thomas M. Peacock, Gustaaf Jacobs, Moneer Helu, and George Haller.  Experimental and numerical investigation of the kinematic theory of unsteady separation.  _Journal of Fluid Mechanics_ , 611, 2008.  doi:10.1017/S0022112008002395.
  * Shadden et al. [2005] Shawn C. Shadden, Francois Lekien, and Jerrold E. Marsden.  Definition and properties of Lagrangian coherent structures from finite-time Lyapunov exponents in two-dimensional aperiodic flows.  _Physica D_ , 212(7):271–304, 2005.  ISSN 0167-2789.  doi:http://dx.doi.org/10.1016/S0167-2789(00)00199-8.
  * Sadlo and Weiskopf [2010] Filip Sadlo and Daniel Weiskopf.  Time-Dependent 2D Vector Field Topology: An Approach Inspired by Lagrangian Coherent Structures.  _Computer Graphics Forum_ , 29(1):88–100, 2010\.
  * Uffinger et al. [2013] Markus Uffinger, Filip Sadlo, and Thomas Ertl.  A time-dependent vector field topology based on streak surfaces.  _IEEE Transactions on Visualization and Computer Graphics_ , 19(3):379–392, 2013.
  * Lipinski and Mohseni [2010] Doug Lipinski and Kamran Mohseni.  A ridge tracking algorithm and error estimate for efficient computation of Lagrangian coherent structures.  _Chaos: An Interdisciplinary Journal of Nonlinear Science_ , 20(1):017504, 2010.  doi:10.1063/1.3270049.  URL http://link.aip.org/link/?CHA/20/017504/1.
  * Günther et al. [2016] Tobias Günther, Alexander Kuhn, and Holger Theisel.  MCFTLE: Monte Carlo rendering of finite-time Lyapunov exponent fields.  _Computer Graphics Forum (Proc. EuroVis)_ , 35(3):381–390, 2016.
  * Garth et al. [2009] Christoph Garth, Xavier Tricoche Guo-Shi Li, Charles D. Hansen, and Hans Hagen.  Visualization of coherent structures in transient 2D flows.  In _Proceedings of TopoInVis 2007_ , pages 1–13, 2009.
  * Garth et al. [2007] Christoph Garth, Florian Gerhardt, Xavier Tricoche, and Hans Hagen.  Efficient computation and visualization of coherent structures in fluid flow applications.  _IEEE Transactions on Visualization and Computer Graphics_ , 13(6):1464–1471, 2007.  ISSN 1077-2626.  doi:http://doi.ieeecomputersociety.org/10.1109/TVCG.2007.70551.
  * Sadlo and Peikert [2009] Filip Sadlo and Ronald Peikert.  Visualizing Lagrangian coherent structures and comparison to vector field topology.  In _Proceedings of TopoInVis 2007_ , pages 15–30, 2009.
  * Sadlo and Peikert [2007] Filip Sadlo and Ronald Peikert.  Efficient visualization of Lagrangian coherent structures by filtered AMR ridge extraction.  _IEEE Transactions on Visualization and Computer Graphics (Proceedings Visualization)_ , 13(6):1456–1463, 2007.
  * Sadlo et al. [2011] Filip Sadlo, Alessandro Rigazzi, and Ronald Peikert.  Time-Dependent Visualization of Lagrangian Coherent Structures by Grid Advection.  In _Proceedings of TopoInVis 2009_ , pages 151–165. Springer, 2011\.
  * Bhatia et al. [2014] Harsh Bhatia, Valerio Pascucci, Robert M. Kirby, and Peer-Timo Bremer.  Extracting features from time-dependent vector fields using internal reference frames.  _Computer Graphics Forum (Proc. EuroVis)_ , 33(3):21–30, June 2014.
  * Wiebel et al. [2007] Alexander Wiebel, Christoph Garth, and Gerik Scheuermann.  Computation of localized flow for steady and unsteady vector fields and its applications.  _IEEE Transactions on Visualization and Computer Graphics_ , 13(4):641–651, 2007.
  * Bujack et al. [2016] Roxana Bujack, Mario Hlawitschka, and Kenneth I Joy.  Topology-inspired galilean invariant vector field analysis.  In _2016 IEEE Pacific Visualization Symposium (PacificVis)_ , pages 72–79. IEEE, 2016.
  * Forman [2001] Robin Forman.  A user’s guide to discrete morse theory.  In _Proc. of the 2001 Internat. Conf. on Formal Power Series and Algebraic Combinatorics, A special volume of Advances in Applied Mathematics_ , page 48, 2001.
  * Reininghaus and Hotz [2011] Jan Reininghaus and Ingrid Hotz.  Combinatorial 2d vector field topology extraction and simplification.  In Valerio Pascucci, Xavier Tricoche, Hans Hagen, and Julien Tierny, editors, _Topological Methods in Data Analysis and Visualization_ , pages 103 – 114. 2011.  ISBN 978-3-642-15013-5.  doi:10.1007/978-3-642-15014-2_9.
  * Mischaikow et al. [2007] K. Mischaikow, E. Zhang, P. Pilarczyk, G. Chen, and R. S. Laramee.  Vector field editing and periodic orbit extraction using morse decomposition.  _IEEE Transactions on Visualization & Computer Graphics_, 13:769–785, 07 2007.  ISSN 1077-2626.  doi:10.1109/TVCG.2007.1021.  URL doi.ieeecomputersociety.org/10.1109/TVCG.2007.1021.
  * Bhatia et al. [2012] Harsh Bhatia, Shreeraj Jadhav, Peer-Timo Bremer, Guoning Chen, Joshua A. Levine, Luis Gustavo Nonato, and Valerio Pascucci.  Flow visualization with quantified spatial and temporal errors using edge maps.  _IEEE Trans. Vis. Comput. Graph._ , 18(9):1383–1396, 2012.  doi:10.1109/TVCG.2011.265.  URL https://doi.org/10.1109/TVCG.2011.265.
  * Skraba et al. [2016] Primoz Skraba, Paul Rosen, Bei Wang, Guoning Chen, Harsh Bhatia, and Valerio Pascucci.  Critical point cancellation in 3d vector fields: Robustness and discussion.  _Transactions on Visualization and Computer Graphics_ , 2016.
  * Wang et al. [2013] Bei Wang, Paul Rosen, Primoz Skraba, Harsh Bhatia, and Valerio Pascucci.  Visualizing robustness of critical points for 2d time-varying vector fields.  _Comput. Graph. Forum_ , 32(3):221–230, 2013\.  doi:10.1111/cgf.12109.  URL https://doi.org/10.1111/cgf.12109.
  * Edelsbrunner et al. [2001] Herbert Edelsbrunner, John Harer, and Afra Zomorodian.  Hierarchical morse complexes for piecewise linear 2-manifolds.  In _Proceedings of the Seventeenth Annual Symposium on Computational Geometry_ , SCG ’01, pages 70–79, New York, NY, USA, 2001. ACM.  ISBN 1-58113-357-X.  doi:10.1145/378583.378626.  URL http://doi.acm.org/10.1145/378583.378626.
  * Bremer et al. [2004] Peer-Timo Bremer, Herbert Edelsbrunner, Bernd Hamann, and Valerio Pascucci.  A topological hierarchy for functions on triangulated surfaces.  _IEEE Trans. Vis. Comput. Graph._ , 10(4):385–396, 2004.  doi:10.1109/TVCG.2004.3.  URL https://doi.org/10.1109/TVCG.2004.3.
  * Edelsbrunner et al. [2003] Herbert Edelsbrunner, John Harer, Vijay Natarajan, and Valerio Pascucci.  Morse-smale complexes for piecewise linear 3-manifolds.  In _Proceedings of the 19th ACM Symposium on Computational Geometry, San Diego, CA, USA, June 8-10, 2003_ , pages 361–370, 2003.  doi:10.1145/777792.777846.  URL http://doi.acm.org/10.1145/777792.777846.
  * Gyulassy et al. [2005] Attila Gyulassy, Vijay Natarajan, Valerio Pascucci, Peer-Timo Bremer, and Bernd Hamann.  Topology-based simplification for feature extraction from 3d scalar fields.  In _16th IEEE Visualization Conference, VIS 2005, Minneapolis, MN, USA, October 23-28, 2005_ , pages 535–542, 2005.  doi:10.1109/VISUAL.2005.1532839.  URL https://doi.org/10.1109/VISUAL.2005.1532839.
  * Lewiner et al. [2004] Thomas Lewiner, Hélio Lopes, and Geovan Tavares.  Applications of forman’s discrete morse theory to topology visualization and mesh compression.  _IEEE Trans. Vis. Comput. Graph._ , 10(5):499–508, 2004.  doi:10.1109/TVCG.2004.18.  URL https://doi.org/10.1109/TVCG.2004.18.
  * Gyulassy et al. [2015] Attila Gyulassy, Harsh Bhatia, Peer-Timo Bremer, and Valerio Pascucci.  Computing accurate morse-smale complexes from gradient vector fields.  In _Green in Software Engineering_ , pages 205–218. 2015.  doi:10.1007/978-3-662-44900-4_12.  URL https://doi.org/10.1007/978-3-662-44900-4_12.
  * Gyulassy et al. [2007] Attila Gyulassy, Vijay Natarajan, Valerio Pascucci, and Bernd Hamann.  Efficient computation of morse-smale complexes for three-dimensional scalar functions.  _IEEE Trans. Vis. Comput. Graph._ , 13(6):1440–1447, 2007.  doi:10.1109/TVCG.2007.70552.  URL https://doi.org/10.1109/TVCG.2007.70552.
  * Cignoni et al. [2000] Paolo Cignoni, D. Constanza, Claudio Montani, Claudio Rocchini, and Roberto Scopigno.  Simplification of tetrahedral meshes with accurate error evaluation.  In _IEEE Visualization 2000, October 8-13, 2000, Hilton Hotel, Salt Lake City, Utah, USA, Proceedings._ , pages 85–92, 2000.  doi:10.1109/VISUAL.2000.885680.  URL https://doi.org/10.1109/VISUAL.2000.885680.
  * Carr et al. [2004] Hamish Carr, Jack Snoeyink, and Michiel van de Panne.  Simplifying flexible isosurfaces using local geometric measures.  In _15th IEEE Visualization 2004 Conference, VIS 2004, Austin, TX, USA, October 10-15, 2004_ , pages 497–504, 2004.  doi:10.1109/VISUAL.2004.96.  URL https://doi.org/10.1109/VISUAL.2004.96.
  * Guskov and Wood [2001] Igor Guskov and Zoë J. Wood.  Topological noise removal.  In _Proceedings of the Graphics Interface 2001 Conference, Ottawa, Ontario, Canada, June 7-9, 2001_ , pages 19–26, 2001.  URL http://www.graphicsinterface.org/proceedings/2001/121/.
  * Takahashi et al. [2004] Shigeo Takahashi, Gregory M. Nielson, Yuriko Takeshima, and Issei Fujishiro.  Topological volume skeletonization using adaptive tetrahedralization.  In _2004 Geometric Modeling and Processing (GMP 2004), Theory and Applications, 13-15 April 2004, Beijing, China_ , pages 227–236, 2004.  doi:10.1109/GMAP.2004.1290044.  URL https://doi.org/10.1109/GMAP.2004.1290044.
  * Carr et al. [2003] Hamish Carr, Jack Snoeyink, and Ulrike Axen.  Computing contour trees in all dimensions.  _Comput. Geom._ , 24(2):75–94, 2003.  doi:10.1016/S0925-7721(02)00093-7.  URL https://doi.org/10.1016/S0925-7721(02)00093-7.
  * Tierny et al. [2012] Julien Tierny, Joel Daniels II, Luis Gustavo Nonato, Valerio Pascucci, and Cláudio T. Silva.  Interactive quadrangulation with reeb atlases and connectivity textures.  _IEEE Trans. Vis. Comput. Graph._ , 18(10):1650–1663, 2012.  doi:10.1109/TVCG.2011.270.  URL https://doi.org/10.1109/TVCG.2011.270.
  * Clebsch [1859] A. Clebsch.  Ueber die integration der hydrodynamischen gleichungen.  _Journal für die reine und angewandte Mathematik_ , 56:1–10, 1859.  URL http://eudml.org/doc/147740.
  * Kotiuga [1991] Peter Kotiuga.  Clebsch potentials and the visualization of three-dimensional solenoidal vector fields.  27:3986 – 3989, 10 1991.
  * Jeong and Hussain [1995] Jinhee Jeong and Fazle Hussain.  On the identification of a vortex.  _Journal of Fluid Mechanics_ , 285:69?94, 1995.  doi:10.1017/S0022112095000462.
  * Brandenburg [2010] Axel Brandenburg.  Magnetic field evolution in simulations with euler potentials.  _Monthly Notices of the Royal Astronomical Society_ , 401(1):347–354, 2010.  ISSN 1365-2966.  doi:10.1111/j.1365-2966.2009.15640.x.  URL http://dx.doi.org/10.1111/j.1365-2966.2009.15640.x.
  * He and Yang [2016] Pengyu He and Yue Yang.  Construction of initial vortex-surface fields and clebsch potentials for flows with high-symmetry using first integrals.  _Physics of Fluids_ , 28(3):037101, 2016.  doi:10.1063/1.4943368.
  * Graham and Henyey [2000] C. Robin Graham and Frank S. Henyey.  Clebsch representation near points where the vorticity vanishes.  _Physics of Fluids_ , 12(4):744–746, 2000.  doi:10.1063/1.870331.
  * Chern et al. [2017] Albert Chern, Felix Knöppel, Ulrich Pinkall, and Peter Schröder.  Inside fluids: Clebsch maps for visualization and processing.  _ACM Trans. Graph._ , 36(4):142:1–142:11, July 2017.  doi:10.1145/3072959.3073591.  URL http://dx.doi.org/10.1145/3072959.3073591.
  * Angelidis and Singh [2007] Alexis Angelidis and Karan Singh.  Kinodynamic skinning using volume-preserving deformations.  In _Proceedings of the 2007 ACM SIGGRAPH/Eurographics Symposium on Computer Animation_ , SCA ’07, pages 129–140, Aire-la-Ville, Switzerland, Switzerland, 2007. Eurographics Association.  ISBN 978-1-59593-624-0.  URL http://dl.acm.org/citation.cfm?id=1272690.1272709.
  * von Funck et al. [2006] Wolfram von Funck, Holger Theisel, and Hans-Peter Seidel.  Vector field based shape deformations.  _ACM Trans. Graph._ , 25(3):1118–1125, July 2006\.  ISSN 0730-0301.  doi:10.1145/1141911.1142002.  URL http://doi.acm.org/10.1145/1141911.1142002.
  * Zigelman et al. [2002] G Zigelman, Ron Kimmel, and Nahum Kiryati.  Texture mapping using surface flattening via multidimensional scaling.  8:198–207, 05 2002.
  * Hormann et al. [2008] Kai Hormann, Konrad Polthier, and Alla Sheffer.  Mesh parameterization: Theory and practice.  In _ACM SIGGRAPH ASIA 2008 Courses_ , SIGGRAPH Asia ’08, pages 12:1–12:87, New York, NY, USA, 2008. ACM.  doi:10.1145/1508044.1508091.  URL http://doi.acm.org/10.1145/1508044.1508091.
  * Ebke et al. [2016] Hans-Christian Ebke, Patrick Schmidt, Marcel Campen, and Leif Kobbelt.  Interactively controlled quad remeshing of high resolution 3d models.  _ACM Trans. Graph._ , 35(6):218:1–218:13, November 2016.  ISSN 0730-0301.  doi:10.1145/2980179.2982413.  URL http://doi.acm.org/10.1145/2980179.2982413.
  * Campen and Kobbelt [2014] M. Campen and L. Kobbelt.  Quad Layout Embedding via Aligned Parameterization.  _Computer Graphics Forum_ , 2014.  ISSN 1467-8659.  doi:10.1111/cgf.12401.
  * Erickson and Har-Peled [2002] Jeff Erickson and Sariel Har-Peled.  Optimally cutting a surface into a disk.  In _Proceedings of the Eighteenth Annual Symposium on Computational Geometry_ , SCG ’02, pages 244–253, New York, NY, USA, 2002. ACM.  ISBN 1-58113-504-1.  doi:10.1145/513400.513430.  URL http://doi.acm.org/10.1145/513400.513430.
  * Friederici et al. [2017] A. Friederici, C. Rössl, and H. Theisel.  Finite time steady 2d vector field topology.  In _Topological Methods in Data Analysis and Visualization IV_ , pages 253–266, 2017.
  * Theisel et al. [2004] H. Theisel, T. Weinkauf, H.-C. Hege, and H.-P. Seidel.  Grid-independent detection of closed stream lines in 2d vector fields.  In _Proc. Vision, Modeling and Visualization (VMV) 2004_ , pages 421–428, Stanford, USA, November 15–18 2004.
  * Weinkauf et al. [2004c] T. Weinkauf, H. Theisel, H.-C. Hege, and H.-P. Seidel.  _Boundary Switch Connectors for Topological Visualization of Complex 3D Vector Fields_ , pages 183–192.  2004c.