11institutetext:  University of Sydney, Australia 22institutetext: University
of Konstanz, Germany 33institutetext: Monash University, Australia
44institutetext: Independent Scholar, Germany 55institutetext: Melbourne
University, Australia

#  CelticGraph: Drawing Graphs as Celtic Knots and Links

Peter Eades 11 Niklas Gröne 22 Karsten Klein 22 0000-0002-8345-5806 Patrick
Eades 55 Leo Schreiber 44 Ulf Hailer 22 Falk Schreiber 2233

###### Abstract

Celtic knots are an ancient art form often attributed to Celtic cultures, used
to decorate monuments and manuscripts, and to symbolise eternity and
interconnectedness. This paper describes the framework CelticGraph to draw
graphs as Celtic knots and links. The drawing process raises interesting
combinatorial concepts in the theory of circuits in planar graphs. Further,
CelticGraph uses a novel algorithm to represent edges as Bézier curves, aiming
to show each link as a smooth curve with limited curvature. eltic Art, Knot
Theory, Interactive Interfaces

###### Keywords:

C

Figure 1: _Using the CelticGraph framework, we take the graph $K^{\prime}_{4}$
(a) ($K_{4}$ with some duplicate edges), and create a knot drawing of
$K^{\prime}_{4}$ (b); from this we render the graph as a Celtic Knot with a
sandstone texture (c)._

##  1 Introduction

Celtic knots are an ancient art form often attributed to Celtic cultures.
These elaborate designs (also called “endless knots”) were used to decorate
monuments and manuscripts, and they were often used to symbolise eternity and
interconnectedness. Celtic knots are a well-known visual representation made
up of a variety of interlaced knots, lines, and stylised graphical
representations. The patterns often form continuous loops with no beginning or
end (knot) or a set of such loops (links). In this paper we will use the
Celtic knot visualisation metaphor to represent specific graphs in the form of
“knot diagrams”.

We show how to draw a 4-regular planar graph111Graphs used in this paper can
contain multiple edges and loops (also called pseudographs or multigraphs). as
a knot/link diagram. This involves constructing certain circuits222For the
formal definition of a circuit see Sect. 4 in the 4-regular planar graph.
Further, we show how to route graph edges so that the underlying links are
aesthetically pleasing. This involves some optimisation problems for cubic
Bézier curves. We also provide an implementation of the presented methods as
an add-on for Vanted [24]. This system allows to transform a graph into a knot
(link) representation and to interactively change the layout of both, the
graph as well as the knot. In addition, knots can be exported to the 3D
renderer Blender [4] to allow for artistic 3D renderings of the knot. Figure 1
shows a 4-regular planar graph, its knot representation and a rendering of the
knot.

##  2 Background

This paper has its roots in three disciplines: Mathematical knot theory,
Celtic cultural history, and graph drawing. We briefly review the relevant
parts of these diverse fields in Sect. 2.1, 2.2, and 2.3. Further, in Sect.
2.4 we review relevant properties of Bézier curves, which are a key ingredient
to CelticGraph.

###  2.1 Knot theory

The mathematical theory of knots and links investigates interlacing curves in
three dimensions; this theory has a long and distinguished history in
Mathematics [23]. The motivating problem of Knot Theory is _equivalence_ :
whether two knots can be deformed into each other. A common technique involves
projecting the given curves from three dimensions into the plane; the
resulting “knot diagram” is a 4-regular planar graph, with vertices at the
points where the curve crosses itself (in the projection). For example, a
picture of the _trefoil knot_ and its knot diagram are in Fig. 2. Properties
of a knot or link may be deduced from the knot diagram, and the equivalence
problem can sometimes be solved using knot diagrams.

Figure 2: _(a) The _trefoil knot_ and (b) its resulting “knot diagram”._

###  2.2 Celtic art

Knot patterns (“Celtic knots”) are often described as a characteristic
ornament of so-called “Celtic art”. In fact, since the epoch of the
Waldalgesheim style (4${}^{\text{th}}$/3${}^{\text{rd}}$ century BC), Celtic
art (resp. ornamentation) is characterised by complex, often geometric
patterns of interlinked, opposing or interwoven discs, loops and spirals. The
floral models originate from Mediterranean art; in the Celtic context, they
were deconstructed, abstracted, arranged paratactically or intertwined [33,
36]. It is still unclear whether the import of Mediterranean ornamental models
was accompanied by the adoption of their meaning. However, the selective
reception of only certain motifs suggests rather an adaptation based on
specific Celtic ideas, which we cannot reconstruct exactly due to a lack of
written sources.

In today’s popular understanding, a special role in the transmission of actual
or supposed “Celtic” art is attributed to the early medieval art of Ireland
[28, 38]. However, such a restriction of Irish or insular art to exclusively
Celtic origins would ignore the historical development of the insular-Celtic
context in Ireland and the British Isles. The early medieval art of Ireland is
partially rooted in indigenous Celtic traditions, but was also shaped by Late
Antique Roman, Germanic and Anglo-Saxon, Viking and Mediterranean-Oriental
models [17]. The knot and tendril patterns of the
7${}^{\text{th}}$/8${}^{\text{th}}$ century can also be traced back to
Mediterranean-Oriental manuscripts. Such patterns were subsequently used in
Anglo-Saxon art, transmitted by braided ribbon ornaments and other patterns in
the Germanic “Tierstil” (e. g. on Late Antique soldiers’ belts). For example,
the famous Tara Brooch created in Ireland in the late 7${}^{\text{th}}$ or
early 8${}^{\text{th}}$ century features both native and Germanic a
combination of corresponding motifs [39]. Also the knot patterns and
braided/spiral ornaments described as typical “Celtic” such as in the Book of
Kells [30] and other manuscripts can be linked to Germanic/Anglo-Saxon and
late Roman traditions. The ornamentation today often perceived as “Celtic” is
therefore less exclusive or typical “Celtic”, but rather a result of diverse
influences that reflect an equally complex historical-political development
[29]. So it is not surprising that the so-called Celtic motifs often presented
in tattoo studios of the 21st century, such as braided bands, are not of
Celtic but Germanic origin [34].

Note that while “Celtic knots” are related to the mathematical theory of
knots, the prime motivation of the two topics is different. For example, the
_Bowen knot_ [7], a commonly used decorative knot that appears in Celtic
cultures, is uninteresting in the mathematical sense (it is clearly an
“unknot”).

###  2.3 Graph drawing as art

Note that the purpose of CelticGraph is different from most Graph Drawing
systems. Our aim is to produce decorative and artistically pleasing pictures
of graphs, not to make pictures of graphs that effectively convey information
and insight into data sets. Other examples of such kind of graph drawing
approaches include the system by Devroye and Kruszewski to render images of
botanical trees based on random binary trees [8], a system GDot-i for drawing
graphs as dot paintings inspired by the dot painting style of Central
Australia [21, 11], and research on bobbin lacework [22]. Also related to our
work are Lombardi graph drawings, artistic representations of graphs that
contain edges represented as circular arcs and vertices represented with
perfect angular resolution [10].

###  2.4 Bézier curves

The Gestalt law of continuity [27] implies that humans are more likely to
follow continuous and smooth lines rather than broken or jagged lines. To draw
graphs as Celtic knots, certain circuits in the graph need to be drawn as
smooth curves.

Computer Graphics has developed many models for smooth curves; one of the
simplest is a _Bézier curve_. A _cubic Bézier curve_ with control points
$p_{0},p_{1},p_{2},p_{3}$ is defined parametrically by:

$p(t)=(1-t)^{3}p_{0}+3(1-t)^{2}tp_{1}+3(1-t)t^{2}p_{2}+t^{3}p_{3},$ (1)

for $0\leq t\leq 1$. The following properties of cubic Bézier curves are well-
known [16]:

  * •

The endpoints of the curve are the first and last control points, that is,
$p(0)=p_{0}$ and $p(1)=p_{3}$.

  * •

Every point on the curve lies within the convex hull of its control points.

  * •

The line segments $(p_{0},p_{1})$ and $(p_{3},p_{2})$ are tangent to the curve
at $p_{0}$ and $p_{3}$ respectively. We say $(p_{0},p_{1})$ and
$(p_{3},p_{2})$ are _control tangents_ of the curve.

  * •

The curve is _$C^{k}$ smooth_ for all $k>0$, that is, all the derivatives are
continuous.

Drawing each edge of a graph as a cubic Bézier curve ensures smoothness in the
edges, and can improve readability [41]. However, for CelticGraph we need
certain _circuits_ in the graph to be smooth curves, so we need the curves
representing certain incident edges to be _joined smoothly_. Suppose that
$p(t)$ and $q(t)$ are two cubic Bézier curves that meet at a common endpoint.
Then the curve formed by joining $p(t)$ and $q(t)$ is $C^{1}$ smooth as long
as the control tangents to each curve at the common endpoint form a straight
line; see Fig.3.

Figure 3: _Two cubic Bézier curves with control points
$p_{0},p_{1},p_{2},p_{3}$ and $q_{0},q_{1},q_{2},q_{3}$, meeting at the point
$p_{3}=q_{0}$. The control tangents are shown in black; note that the points
$p_{2},p_{3},q_{1}$ lie on a straight line and the join is $C_{1}$ and
visually smooth._

Mathematically, $C^{1}$ smoothness is adequate. However, the infinitesimality
of Mathematics sometimes does not model human perception well. For example,
the curve in Fig. 4 is mathematically smooth, but given a fixed-resolution
screen and the limits of human perception, it appears to have a non-
differentiable “kink”.

Figure 4: _A cubic Bézier curve with a “kink”, i. e. a point of large
curvature, near the middle. The curve is $C^{1}$ smooth; but the kink,
together with the limits of human perception and screen resolution, mean that
the curve does not look smooth._

For this reason, it is desirable that the _curvature_ [13] of each edge is not
too large. Informally, the curvature $\kappa(t)$ is the “sharpness” of the
curve. More formally, $\kappa(t)$ is the inverse of the radius of the largest
circle that can sit on the curve at $p(t)$ without crossing the curve. For a
cubic Bézier curve $p(t)=(x(t),y(t))$, the curvature at $p(t)$ is given by
[16]:

$\kappa(t)=\frac{\left|\dot{x}\ddot{y}-\ddot{x}\dot{y}\right|}{\left(\dot{x}^{2}+\dot{y}^{2}\right)^{1.5}},$
(2)

where $\dot{f}$ denotes the derivative of $f$ with respect to $t$. Note that
$\kappa(t)$ is continuous except for values of $t$ where both $\dot{x}(t)$ and
$\dot{y}(t)$ are zero. For CelticGraph, we need $C^{1}$ smooth curves with
reasonably small curvature.

###  2.5 Related Work

####  2.5.1 Knot diagrams as Lombardi graph drawings

Closely related are Lombardi graph drawings which are graph drawings with
circular-arc edges and perfect angular resolution [10]. Previous studies have
demonstrated that a significant group of 4-regular planar graphs can be
represented as plane Lombardi graph drawings [25]. However, there are certain
restrictions. Notably, if a planar graph contains a loop, it cannot be
depicted as a Lombardi drawing. In our approach, every 4-regular planar graph
can be transformed in a knot (links).

####  2.5.2 Celtic knots by tiling and algorithmic design methods

Celtic knots can be created using tiling and algorithmic design methods.
George Bain introduced a formal method for creating Celtic knot patterns [2],
which subsequently has been simplified to a three-grid system by Iain Bain [3,
18]. Klempien-Hinrichs and von Totth study the generation of Celtic knots
using collage grammars [26]. And Even-Zohar et al. investigate sets of planar
curves which yield diagrams for all knots [12]. None of those methods use
graphs or are graph drawing approaches.

####  2.5.3 Drawing graphs with Bézier curve edges

A number of network visualisation systems use Bézier curves as edges. These
include yWorks [42], GraphViz [20], Vanted [24], Vizaj [37], and the framework
proposed in [19]. In many cases, such systems allow the user to route the
curves by adjusting control points, but few provide automatic computation of
the curves. However, there are some exceptions. For example, in the GraphViz
system, Bézier curve edges are routed within polygons to avoid edge crossings
[1]. Force-directed methods are also popular for computing control points of
Bézier curve edges [6, 15, 14]. Brandes et al. present a similar method to the
“cross” method in Sect. 5, applied to transport networks [5]. However, only
[14] considers smoothness in more than one edge. None of those systems or
approaches consider Celtic knots.

##  3 Overview of the CelticGraph process

In this Section we outline CelticGraph, our framework for creating
aesthetically pleasing pictures of 4-regular planar graphs as knots. The
CelticGraph procedure is shown in Fig. 5; it has 5 steps:

  1. (a)

Create a topological embedding $G^{\prime}$ of the input 4-regular planar
graph $G$.

  2. (b)

Create a planar straight-line drawing $D$ of the plane graph $G^{\prime}$.

  3. (c)

Create a special circuit partition of $G^{\prime}$, called a “threaded circuit
partition”.

  4. (d)

Using the straight-line drawing $D$ and the threaded circuit partition $C$,
create a drawing $D^{\prime}$ of $G$ with cubic Bézier curves as edges.

  5. (e)

Render the drawing $D^{\prime}$ as a knot, on the screen or with a 3D printer.

Figure 5: _The CelticGraph process_

The first two steps can be done using standard Graph Drawing methods [9].
Steps (c) and (d) are described in the following Sections, step (e) can be
done using standard rendering methods.

##  4 Step (c): Finding the threaded circuit partition

Here we define _threaded circuit partition_ , a special kind of circuit
partition of a plane graph, and show how to find it in linear time.

A _circuit_ in a graph $G$ is a list of distinct edges
$(e_{0},e_{1},\ldots,e_{k-1})$ such that $e_{i}$ and $e_{i+1}$ share a vertex
$i=0,1,\ldots,k-1$ (here, and in the remainder of this paper, indices in a
circuit of length $k$ are taken modulo $k$.) We can write the circuit as a
list of vertices $(u_{0},u_{1},\ldots,u_{k-1})$ where $e_{i}=(u_{i},u_{i+1})$.
Note that a vertex can appear more than once in a circuit, but an edge cannot.
A set $C=\\{c_{0},c_{1},\ldots,c_{h-1}\\}$ of circuits in a graph $G$ such
that every edge of $G$ is in exactly one $c_{j}$ is a _circuit partition_ for
$G$. Given a circuit partition, we can regard $G$ as a directed graph by
directing each edge so that each $c_{i}$ is a directed circuit.

A path $(\alpha,\beta,\gamma)$ of length two (that is, two edges
$(\alpha,\beta)$ and $(\beta,\gamma)$) in a 4-regular plane graph $G$ is a
_thread_ if edges $(\alpha,\beta)$ and $(\beta,\gamma)$ are not contiguous in
the cyclic order of edges around $\beta$. This means that there is an edge
between $(\alpha,\beta)$ and $(\beta,\gamma)$ in both counterclockwise and
clockwise directions in the circular order of edges around $\beta$. We say
that $\beta$ is the _midpoint_ of the thread $(\alpha,\beta,\gamma)$. Note
that each vertex in $G$ is the midpoint of two threads; see Fig. 6(a). For
every edge $(\alpha,\beta)$ in $G$, there is a unique thread
$(\alpha,\beta,\gamma)$; we say that the edge $(\beta,\gamma)$ is the _next
edge after $(\alpha,\beta)$_. For each vertex $u_{j}$ on a circuit
$c=(u_{0},u_{1},\ldots,u_{k-1})$ with $k>1$ there is a path
$p_{j}=(u_{j-1},u_{j},u_{j+1})$ of length two such that $u_{j}$ is the
midpoint of $p_{j}$. In fact we can consider that the circuit $c$ consists of
$k$ paths of length two. We say that the circuit $c$ is _threaded_ if for each
$j$, the path $p_{j}=(u_{j-1},u_{j},u_{j+1})$ is a thread. Note that in such a
circuit, the edge $(u_{j},u_{j+1})$ is the (unique) next edge after
$(u_{j-1},u_{j})$ for each $j$. A circuit partition
$C=\\{c_{0},c_{1},\ldots,c_{h-1}\\}$ is _threaded_ if each circuit $c_{j}$ is
threaded. In the case that $h=1$, a threaded circuit partition defines a
_threaded Euler circuit_ ; see Fig. 6(b).

Figure 6: _(a) Two threads, each with midpoint $\beta$. (b) Plane 4-regular
graph with a threaded Euler circuit $(0,1,2,3,4,0,5,6,3,7,1,5,8,4,7,2,6,8)$._

An assignment $\upsilon(p)\in\\{-1,+1\\}$ of an integer $-1$ or $+1$ to each
thread $p$ of a 4-regular plane graph $G$ is an _under-over assignment_. Note
that for each vertex $\beta$ of $G$, there are two threads $p_{\beta}$ and
$p^{\prime}_{\beta}$ with midpoint $\beta$. We say that an under-over
assignment $\upsilon$ is _consistent_ if
$\upsilon(p_{\beta})=-\upsilon(p^{\prime}_{\beta})$ for each vertex $\beta$.

An under-over assignment $\upsilon$ is _alternating_ on the circuit
$(p_{0},p_{1},\ldots,p_{k-1})$ if $\upsilon(p_{i})=-\upsilon(p_{i+1})$ for
each $i$. An under-over assignment for a graph with a threaded circuit
partition $C$ is _alternating_ if it is alternating on each circuit in $C$.

Intuitively, a consistent under-over assignment designates which thread passes
under or over which thread, and an alternating under-over assignment
corresponds to an alternating knot or link [31].

The following theorem gives the essential properties of threaded circuit
partitions that are essential for CelticGraph.

###### Theorem 4.1

Every 4-regular plane graph has a unique threaded circuit partition, and this
threaded circuit partition has a consistent alternating under-over assignment.
Further, this threaded circuit partition can be found in linear time.

###### Proof

The existence and uniqueness of the threaded circuit partition follows from
the fact that every edge has a unique next edge. A simple linear-time
algorithm to find the threaded circuit partition is to repeatedly choose an
edge $e$ that is not currently in a circuit, then repeatedly choose the next
edge after $e$ until we return to $e$. We can direct every edge of a 4-regular
planar graph $G$ so that each circuit in a given threaded circuit partition
$C$ is a directed circuit. This means that we can sensibly define the “left”
and “right” faces of an edge. Since a 4-regular plane graph is bridgeless
[35], no face is both “left” and “right”.

Figure 7: _(a) Two threads: $(\alpha,\beta,\gamma)$ has under-over assignment
$+1$ (since the face to the left of $(\alpha,\beta)$ is green), and
$(\alpha^{\prime},\beta,\gamma^{\prime})$ has under-over assignment $-1$
(since the face to the left of $(\alpha^{\prime},\beta)$ is blue). (b) The
faces of the graph are coloured according to its bipartition; note that each
vertex has two incoming edges: one has a blue face to the left, the other has
a green face to the left, and that the faces on the left of the threaded Euler
circuit alternate in colour._

Since the planar dual graph of a 4-regular planar graph is bipartite [35], the
faces can be coloured _green_ and _blue_ , such that no two faces of the same
colour share an edge, see Fig. 7. An immediate consequence is that the
sequence of left faces to (directed) edges in a threaded circuit _alternate_
in colour. Now consider a thread $(\alpha,\beta,\gamma)$ in a (directed)
threaded circuit in a threaded circuit partition. If the face to the left of
$(\alpha,\beta)$ is green, then assign $+1$ to the path
$(\alpha,\beta,\gamma)$; otherwise assign $-1$ to $(\alpha,\beta,\gamma)$.
Note that the face to the left of $(\beta,\gamma)$ is the opposite colour of
the face to the left of $(\alpha,\beta)$, and so the under-over assignment is
alternating. Further it is consistent, since at each vertex there is precisely
one incoming arc with a green face on the left, and precisely one incoming arc
with a blue face on the left.

####  4.0.1 Threaded Euler circuits

Celtic knots are sometimes called “endless knots”, and can be used to
symbolise eternity. For this reason, a threaded _Euler_ circuit is desirable;
such a circuit gives a drawing of the graph as a knot rather than a link.
Using the algorithms in the proof of Theorem 4.1, one can test whether a given
plane graph has a threaded Euler circuit in linear time. Note that different
topological embeddings of a given planar graph may have different threaded
circuit partitions; see Fig. 8. It is clear that, in some cases, we can
increase the length of a threaded circuit by changing the embedding. It is
tempting to try to find a method to adjust the embedding to get a threaded
Euler circuit. However, it can be shown that changing the embedding cannot
change the _number_ of threaded circuits in a threaded circuit partition; see
Appendix 0.A.

Figure 8: _Two topological embeddings of a planar graph. In (a), the plane
graph has a threaded circuit partition of 4 circuits, with two circuits of
size 6 (in black) and two circuits of size 12 (in blue and orange). In (b),
the plane graph still has 4 threaded circuits: the two of size 6 are
unchanged, but the lengths of the blue and orange circuits are 14 and 10
respectively._

##  5 Step (d): Smooth knot drawing with Bézier curves

Step (d) takes a straight-line drawing $D$ of the input graph $G$, and
replaces the straight-line edges by cubic Bézier curves in a way that ensures
that each circuit in the threaded circuit partition found in step (c) is
smooth.

A central concept for the smooth drawing method is a “cross” $\chi_{u}$ at
each vertex $u$. For each $u$, $\chi_{u}$ consists of 4 line segments called
“arms”. The four arms are all at right angles to each other, leading to a
perfect angular resolution. Each arm of $\chi_{u}$ has an endpoint at $u$.

Figure 9: _(a) The 3-prism with a cross at each vertex. (b) Edges drawn as
Bézier curves, using the arms of the crosses as control tangents._

This is illustrated in Fig. 9(a). Each edge $(u,v)$ then is drawn as a cubic
Bézier curve with endpoints $u$ and $v$, and the control tangents of the curve
are arms of the crosses $\chi_{u}$ and $\chi_{v}$ (illustrated in Fig. 9(b)).

For this approach, we need to choose three parameters for each cross
$\chi_{u}$:

  1. 1.

The mapping between the four arms of $\chi_{u}$ and the four edges incident to
$u$.

  2. 2.

The angle of orientation of the cross.

  3. 3.

The length of each arm of the cross.

These parameters are discussed in the next subsections. The methods described
in Sect. 5.1 and 5.2 are analogous to the methods in [5]; Sect. 5.3 is not.

###  5.1 The edge-arm mapping

Suppose that $u$ is a vertex in the straight-line drawing $D$ of the input
plane graph. We want to choose the mapping between the arms of the cross
$\chi_{u}$ and the edges incident with $u$ so that the arms are approximately
in line with the edges.

Now suppose that the edges incident with $u$ are $e_{0},e_{1},e_{2},e_{3}$ in
counterclockwise order around $u$. For each $i=0,1,2,3$ we choose an arm
$\alpha_{i}$ of the cross $\chi_{u}$ corresponding to $e_{i}$ so that the
counterclockwise order of arms around $u$ is the same as the order of edges
around $u$; that is, the counterclockwise order of arms is
$\alpha_{0},\alpha_{1},\alpha_{2},\alpha_{3}$. Note that this method separates
multi-edges.

###  5.2 The orientation of the cross

To improve the alignment of the arms of the crosses with the edges, we rotate
each cross. Suppose that the counterclockwise angle that edge $e_{i}$ makes
with the horizontal direction is $\phi_{i}$. We want to rotate the cross by an
angle $\theta$ to align with the edges, as best as possible. This is
illustrated in Fig. 10.

Figure 10: _A cross rotated by an angle of $\theta$. Here the cross is in
blue, the edges of the graph are in orange._

Consider the sum of squares error in rotating by $\theta$; this is:

$f(\theta)=\sum_{i=0}^{i=3}\left(\theta+\frac{i\pi}{2}-\phi_{i}\right)^{2}.$
(3)

To minimise $f(\theta)$, we solve $f^{\prime}(\theta)=0$ and choose the
optimum value:

$\theta^{*}=\frac{1}{4}\left(\sum_{i=0}^{i=3}\phi_{i}\right)-\frac{3\pi}{4}.$
(4)

In Fig. 11, we show a graph with crosses oriented by this method.

Figure 11: _A graph with crosses oriented to align with edges as much as
possible before (a) and after (b) applying the algorithm, and shown in Vanted
(c)._

###  5.3 Arm length

Figure 12: _Three drawings of the 3-prism, differing in edge curvature._

Note that the “apparent smoothness” of an edge depends on its curvature. We
illustrate this with Fig. 12, which shows three Bézier curve drawings of the
3-prism. This graph has 3 threaded circuits, and we want to draw it so that
each one of these threaded circuits appears as a smooth curve with limited
curvature. In Fig. 12(a), the arms of the crosses are all very short,
resulting in a Bézier curve drawing which is very close to a straight-line
drawing. Each edge has low curvature in the middle and high curvature around
the endpoints. The high curvature near their endpoints results in a lack of
apparent smoothness where two Bézier curves join (at the vertices); it is
difficult to discern the three threaded circuits. The arms of the crosses are
longer in Fig. 12(b), resulting in better curvature at the endpoints. However,
here each of the edges $(0,3),(1,4)$, and $(2,5)$ have two points of large
curvature; this is undesirable. In Fig. 12(c), the arms of the crosses are
longer still. Each of the edges $(0,3),(1,4)$, and $(2,5)$ again have two
points of large curvature, but the edges $(3,4),(4,5)$, and $(5,3)$ are worse:
each has a “kink” (a point of very high curvature, despite being
$C^{1}$-smooth).

Next we describe three approaches to choosing the lengths of the arms of the
crosses, aiming to give sufficiently small curvature.

####  5.3.1 Uniform arm lengths

The curvature of the edge varies with lengths of the arms, and we want to
ensure that the maximum curvature in each edge is not too large. The simplest
approach is to use _uniform arm lengths_ , that is, judiciously choose a
global value $\lambda$ and set the length of every arm length to $\lambda$.
The drawings of the 3-prism in Fig. 12 have uniform arm lengths: $\lambda$ in
Fig. 12(a) is quite small, in Fig. 12(c) it is relatively large, and (b) is in
between. In fact, the problem with the uniform arm length approach is typified
in Fig. 12: if $\lambda$ is small, the curvature is high near the endpoints
for all edges, and increasing $\lambda$ increases the curvature away from the
endpoints, especially in the shorter edges. There is no uniform value of
$\lambda$ that gives good curvature in both short and long edges.

####  5.3.2 Uniformly proportional arm lengths

An approach that aims to overcome the problems of uniform arm length is to use
_uniformly proportional arm lengths_ : we judiciously choose a global value
$\alpha$, and then set the lengths of the two arms for edge $(u,v)$ to $\alpha
d(u,v)$, where $d(u,v)$ is the Euclidean distance between $u$ and $v$. Fig. 13
shows typical results for the uniformly proportional approach. For
$\alpha=0.2$ the drawing is similar to Fig. 13(a), and has similar problems.
But for values of $\alpha$ near $0.5$ (Fig. 13(b) and (c)), we have acceptable
results; in particular, the shorter edges have acceptable curvature.

Figure 13: _The uniformly proportional approach: (a) $\alpha=0.2$; (b)
$\alpha=0.4$; (c) $\alpha=0.6$._

####  5.3.3 Optimal arm lengths

Figure 14: _“Ballooning” curves: as $\lambda_{u}$ and $\lambda_{v}$ increase,
curvature falls but the curve becomes very long._

A third approach is to choose the arm lengths at each end of an edge $(u,v)$
to minimise maximum curvature, as follows. Suppose
$\kappa(t,\lambda_{u},\lambda_{v})$ is the curvature of the edge $(u,v)$ at
point $t$ on the curve, when the arm lengths are $\lambda_{u}$ and
$\lambda_{v}$ at $u$ and $v$ respectively. From Equation (2), we note that

Figure 15: _Comparison of proportional arm length (blue) and optimal arm
length (magenta): (a) Trefoil; (b) $K_{4}$ knot; (c) 3-prism; (d) Love knot._

$\frac{\partial}{\partial
t}\kappa(t,\lambda_{u},\lambda_{v})=\left|\frac{\dddot{x}\dot{y}-\dddot{y}\dot{x}}{(\dot{x}^{2}+\dot{y}^{2})^{1.5}}-\frac{\ddot{x}\dot{y}-\ddot{y}\dot{x}}{3(\ddot{x}+\ddot{y})^{2.5}}\right|$
(5)

as long as $(\dot{x}^{2}+\dot{y}^{2})\neq 0$ and
$\ddot{x}\dot{y}\neq\ddot{y}\dot{x}$. Since both $x$ and $y$ are cubic
functions of $t$, equation (5) is not as complex as it seems, and it is
straightforward (but tedious, because of the edge cases) to maximise
$\kappa(t,\lambda_{u},\lambda_{v})$ over $t$; that is, to find the maximum
curvature $\kappa^{*}(\lambda_{u},\lambda_{v})$:

$\kappa^{*}(\lambda_{u},\lambda_{v})=\max_{0\leq t\leq
1}\kappa(t,\lambda_{u},\lambda_{v}).$

Now we want to choose the arm lengths $\lambda_{u}$ and $\lambda_{v}$ to
minimise $\kappa^{*}(\lambda_{u},\lambda_{v})$. Suppose that the unit vectors
in the directions of the appropriate arms of $\chi_{u}$ and $\chi_{v}$ are
$\iota_{u}$ and $\iota_{v}$ respectively. Note that we can express the
internal control points $p_{1}$ and $p_{2}$ of the Bézier curve in terms of
$\lambda_{u}$ and $\lambda_{v}$:

$p_{1}=(1-\lambda_{u})u+\lambda_{u}\iota_{u},~{}~{}p_{2}=(1-\lambda_{v})v+\lambda_{v}\iota_{v}.$

In this way, $\kappa^{*}(\lambda_{u},\lambda_{v})$ is linear in both
$\lambda_{u}$ and $\lambda_{v}$ and finding a minimum point for
$\kappa^{*}(\lambda_{u},\lambda_{v})$ is straightforward. However, in some
cases, an edge with globally minimum maximum curvature may not be desirable.
In Fig. 14, for example, the curvature decreases as $\lambda_{u}$ and
$\lambda_{v}$ increase; for large values of $\lambda_{u}$ and $\lambda_{v}$
the curvature is quite low. The problem is that these large values make the
curve very long (it “balloons” out), which might also cause unintended edge
crossings.

For this reason, we choose an upper bounds $\epsilon_{u}$ and $\epsilon_{v}$
and take a minimum constrained by $\lambda_{u}\leq\epsilon_{u}$ and
$\lambda_{v}\leq\epsilon_{v}$:

$\kappa^{*}_{\min}=\min_{0\leq\lambda_{u}\leq\epsilon_{u},0\leq\lambda_{v}\leq\epsilon_{v}}\kappa^{*}(\lambda_{u},\lambda_{v}).$

We have found that $\epsilon_{u}=\epsilon_{v}=0.75d(u,v)$ gives good results,
where $d(u,v)$ is the distance between $u$ and $v$. Values of $\lambda_{u}$
and $\lambda_{v}$ that achieve the (constrained) minimum $\kappa^{*}_{\min}$
are then used by the Bézier curves. In practice, using such optimal arm
lengths gives better results than using uniformly proportional arm lengths. In
some cases the difference is not significant, but in others the optimal edges
appear to be much smoother. See Fig. 15 for examples.

Figure 16: Examples of Celtic knot renderings in different media including a
3D printed version (mid left).

##  6 CelticGraph implementation as a Vanted add-on and rendering

CelticGraph has been implemented as an add-on of Vanted, a tool for
interactive visualisation and analysis of networks. Figure 1 shows an example
workflow; the first step is implemented as Vanted [24] add-on, the second is
done by Blender [4].

Vanted allows a user to load or create 4-regular graphs, either by importing
from files (e. g. a .gml file), by selecting from examples, or by creating a
new graph by hand. The individual vertices of the graph are then mapped into
the data structure of a cross, containing position and the rotation and
control points of the to-be-generated Bézier curves. The graph is translated
into a knot (link) using the methods for optimal cross rotation and arm length
computation described in the previous sections. Vertex positions can be
interactively changed, either by interacting with the underlying graph, or by
interacting directly with the visualisation of the knot. Once a visualisation
satisfies the expectation of the user, the Bézier curves can be exported for
further use in Blender.

We implemented a Python script and a geometry node tree in Blender which
allows importing the information into Blender and rendering the knot (links),
either using a set of predefined media or interactively; the script can also
run as batch process with selected parameters and media. Figure 16 shows
examples of Celtic knot renderings in different media such as in metal, in
stone, with additional decoration and so on; knots can be also printed in 3D.
More examples can be found in the gallery of our web page
http://celticknots.online which also provides the Vanted add-on, Blender file
and a short manual.

### Acknowledgements

Partly funded by the Deutsche Forschungsgemeinschaft (DFG, German Research
Foundation) – Project-ID 251654672 – TRR 161.

## References

  * [1] Abello, J., Gansner, E.: Short and smooth polygonal paths. In: Lucchesi, C.L., Moura, A.V. (eds.) LATIN’98: Theoretical Informatics. pp. 151–162. Springer (1998)
  * [2] Bain, G.: Celtic art : the methods of construction. Dover Publications (1973)
  * [3] Bain, I.: Celtic knotwork. Sterling Publishing Co. (1986)
  * [4] Blender Online Community: Blender – a 3D modelling and rendering package. Blender Foundation (2018), http://www.blender.org
  * [5] Brandes, U., Shubina, G., Tamassia, R.: Improving angular resolution in visualizations of geographic networks. In: de Leeuw, W.C., van Liere, R. (eds.) Data Visualization 2000. pp. 23–32. Eurographics, Springer (2000)
  * [6] Brandes, U., Wagner, D.: Using graph layout to visualize train interconnection data. Journal of Graph Algorithms and Applications 4, 135–155 (2000)
  * [7] Clark, H.: A short and easy introduction to heraldry. London, Printed for H. Washbourn (1827)
  * [8] Devroye, L., Kruszewski, P.: The botanical beauty of random binary trees. In: Brandenburg, F. (ed.) Graph Drawing 1995. LNCS, vol. 1027, pp. 166–177. Springer (1995)
  * [9] Di Battista, G., Eades, P., Tamassia, R., Tollis, I.G.: Graph Drawing: Algorithms for the Visualization of Graphs. Prentice Hall (1999)
  * [10] Duncan, C.A., Eppstein, D., Goodrich, M.T., Kobourov, S.G., Nöllenburg, M.: Lombardi drawings of graphs. In: Brandes, U., Cornelsen, S. (eds.) Graph Drawing 2010. LNCS, vol. 6502, pp. 195–207. Springer (2010)
  * [11] Eades, P., Hong, S.H., McGrane, M., Meidiana, A.: GDot-i: Interactive system for dot paintings of graphs. In: Krone, M., Lenti, S., Schmidt, J. (eds.) EuroVis 2022 - Posters. The Eurographics Association (2022)
  * [12] Even-Zohar, C., Hass, J., Linial, N., Nowik, T.: Universal knot diagrams. Journal of Knot Theory and Its Ramifications 28(07) (2019)
  * [13] Ferguson, R.: An easier derivation of the curvature formula from first principles. Australian Senior Mathematics Journal 32, 16–22 (2018)
  * [14] Fink, M., Haverkort, H., Nöllenburg, M., Roberts, M., Schuhmann, J., Wolff, A.: Drawing metro maps using bezier curves. In: Graph Drawing 2012. LNCS, vol. 7704, pp. 463–474. Springer (2013)
  * [15] Finkel, B., Tamassia, R.: Curvilinear graph drawing using the force-directed method. In: Graph Drawing 2004. LNCS, vol. 3383, pp. 448–453. Springer (2004)
  * [16] Foley, J.D., van Dam, A., Feiner, S., Hughes, J.F.: Computer graphics - principles and practice, 2nd Edition. Addison-Wesley (1990)
  * [17] Fries-Knoblach, J.: Die Kelten, pp. 138–142. Kohlhammer-Urban (2012)
  * [18] Glassner, A.: Celtic knotwork, part 1. IEEE Computer Graphics and Applications 19(5), 78–84 (1999)
  * [19] Goodrich, M.T., Wagner, C.G.: A framework for drawing planar graphs with curves and polylines. In: Whitesides, S.H. (ed.) Graph Drawing 1998. LNCS, vol. 1547, pp. 153–166. Springer (1998)
  * [20] Graphviz. https://graphviz.org/
  * [21] Hong, S.H., Eades, P., Torkel, M.: Gdot: Drawing graphs with dots and circles. In: 2021 IEEE 14th Pacific Visualization Symposium (PacificVis). pp. 156–165 (2021). https://doi.org/10.1109/PacificVis52677.2021.00029
  * [22] Irvine, V., Biedl, T., Kaplan, C.S.: Quasiperiodic bobbin lace patterns. Journal of Mathematics and the Arts 14(3), 177–198 (2020)
  * [23] James, I.M.: History of topology. North Holland (1999)
  * [24] Junker, B.H., Klukas, C., Schreiber, F.: VANTED: A system for advanced data analysis and visualization in the context of biological networks. BMC Bioinformatics 7, 109.1–13 (2006)
  * [25] Kindermann, P., Kobourov, S., Löffler, M., Nöllenburg, M., Schulz, A., Vogtenhuber, B.: Lombardi drawings of knots and links. In: Frati, F., Ma, K.L. (eds.) Graph Drawing and Network Visualization. pp. 113–126. LNCS, Springer (2018)
  * [26] Klempien-Hinrichs, R., von Totth, C.: Generation of celtic key patterns with tree-based collage grammars. In: Manipulation of graphs, algebras and pictures. Electron. Commun. Eur. Assoc. Softw. Sci. Technol., vol. 26, pp. 205–222 (2010)
  * [27] Koffka, K.: Principles of Gestalt psychology. Harcort Brace and Co. (1935)
  * [28] Maier, B.: Die Geschichte, Kultur, Sprache, pp. 158–159. utb (2015)
  * [29] Maier, B.: Die Geschichte, Kultur, Sprache, p. 159. utb (2015)
  * [30] Monks of St. Columba’s order of Iona: The Book of Kells. at the Old Library in Trinity College Dublin (9th century)
  * [31] Murasugi, K.: Knot theory and its applications (1993)
  * [32] Mutzel, P.: The SPQR-tree data structure in graph drawing. In: Baeten, J.C.M., Lenstra, J.K., Parrow, J., Woeginger, G.J. (eds.) Automata, Languages and Programming. pp. 34–46. Springer (2003)
  * [33] Müller, F.: Die Kunst der Kelten. C.H. Beck Wissen (2012)
  * [34] Müller, F.: Die Kunst der Kelten, p. 119. C.H. Beck Wissen (2012)
  * [35] Nishizeki, T., Rahman, M.S.: Planar graph drawing, Lecture Notes Series on Computing, vol. 12. World Scientific (2004)
  * [36] Rieckhoff, S., Biel, J.: Die Kelten in Deutschland, pp. 197–206. Konrad Theiss Verlag (2001)
  * [37] Rolland, T., De Vico Fallani, F.: Vizaj—a free online interactive software for visualizing spatial networks. PLoS ONE 18(3), e0282181 (2023)
  * [38] Röber, R.: Exhibition catalogue Archäologisches Landesmuseum Stuttgart: Die Welt der Kelten. Zentren der Macht – Kostbarkeiten der Kunst, pp. 460–521. Jan Thorbecke Verlag (2012)
  * [39] Röber, R.: Exhibition catalogue Archäologisches Landesmuseum Stuttgart: Die Welt der Kelten. Zentren der Macht – Kostbarkeiten der Kunst, pp. 512–515. Jan Thorbecke Verlag (2012)
  * [40] Whitney, H.: 2-isomorphic graphs. American Journal of Mathematics 55, 245–54 (1933)
  * [41] Xu, K., Rooney, C., Passmore, P., Ham, D.H., Nguyen, P.H.: A user study on curved edges in graph visualization. IEEE Transactions on Visualization and Computer Graphics 18(12), 2449–2456 (2012)
  * [42] yworks. https://yWorks.org/

##  Appendix 0.A The cardinality of a threaded circuit partition is fixed

In this appendix we provide a proof for the claim made above in Section 4;
namely that the _number_ of threaded circuits in any threaded circuit
partition of a 4-regular plane graph $G$ is fixed by the combinatoric
structure of $G$, and cannot be changed by taking a different plane embedding
of $G$.

Since there is no choice of plane embedding for 3-connected graphs [40] we
will be concerned only with 1- and 2-connected graphs. We will not consider
disconnected graphs; in that case each connected component should be treated
separately. Clearly a threaded circuit cannot span multiple connected
components, so the cardinality of a threaded circuit partition of a
disconnected graph is exactly the sum of the cardinalities of the threaded
circuit partitions of its components.

Suppose that $G$ is a 4-regular planar graph, and $c$ is a cutpoint separating
components $G_{1}$ and $G_{2}$ in $G$. Note that $c$ has degree 2 in both
$G_{1}$ and $G_{2}$, because a 4-regular graph is bridgeless. Now suppose that
the two edges incident with $c$ in $G_{1}$ are $e_{1}$ and $e_{2}$. By the
handshake lemma $e_{1}$ and $e_{2}$ belong to the same threaded circuit in any
threaded circuit of an embedding of $G$. Thus, noting that $c$ is the midpoint
of two threads, all four edges incident with $c$ belong to the same threaded
circuit. Therefore changing the order of 2-connected components around a
cutpoint does not change the number of threaded circuits; in fact we can
deduce the following theorem.

###### Theorem 0.A.1

Suppose that $G$ is a 4-regular planar graph, and $c$ is a cutpoint separating
components $G_{1}$ and $G_{2}$ in $G$; denote by $G^{\prime}_{i}$ the
4-regular planar graph formed by adding a self-loop to $c$ in $G_{i}$, for
$i=1,2$. Suppose that $\hat{G}$ is a planar embedding of $G$, and
$\hat{G^{\prime}_{1}}$ and $\hat{G^{\prime}_{2}}$ are plane subgraphs of $G$
corresponding to $G^{\prime}_{1}$ and $G^{\prime}_{2}$ respectively. Suppose
that $\hat{G},\hat{G_{1}}$ and $\hat{G_{2}}$ have threaded circuit partitions
$C,C_{1}$, and $C_{2}$ respectively. Then $|C|=|C_{1}|+|C_{2}|-1$.

In contrast, “mirroring” about a _separation pair_ can change the threaded
circuits; as demonstrated in Fig. 8. However, we will now show that the
cardinality of a threaded circuit partition is a _graph property_ , not an
embedding property; that is, changing the embedding does not change the
_number_ of threaded circuits in a threaded circuit partition.

###### Theorem 0.A.2

Suppose that $G$ is a 2-connected 4-regular planar graph, and $C$ and
$C^{\prime}$ are threaded circuit partitions of two planar embeddings of $G$.
Then $|C|=|C^{\prime}|$.

###### Proof

For a 2-connected planar graph, all planar embeddings can be found by
“pivoting” (re-ordering and “mirroring”) 3-connected components around
separation pairs. We show that such a pivoting does not change the cardinality
of a threaded circuit partition.

Firstly note that pivoting does not change the internal structure of any
component; it only changes the “interface”, that is, the way in which it
connects to the rest of the graph. Thus the only threaded circuits that are
possibly changed are those that pass through one or both vertices in the
separation pair.

Now suppose that vertices $c$ and $d$ form a separation pair that separates
$G_{1}$ from $G_{2}$. The handshake lemma implies that either both $c$ and $d$
have degree 2 in $G_{1}$, or both have odd degree in $G_{1}$. One can deduce
that, since the graph is 4-regular and planar, there are only four possible
“interfaces”, enumerated in Fig. 17.

To complete the proof, note that pivoting each type of subgraph does not
change the cardinality of the threaded circuit partition.

Figure 17: _Examples of the four types of subgraphs separated by a separation
pair. The type of a subgraph is determined by a perfect matching on the edges
in its cut; there are three ways to match four edges, and one way to match two
edges._

We finally note that this observation provides an extension to the simple
linear-time algorithm in Section 4 that tests whether a graph has a threaded
Euler circuit (in any embedding). Using a SPQR tree [32], one can decompose
the graph into pivotable components and solve the following optimisation
problems:

  * •

Given a 2-connected 4-regular planar graph, find a planar embedding in which
the length of the longest threaded circuit is maximised.

  * •

Given a 2-connected 4-regular planar graph, find a planar embedding in which
the average of the lengths of threaded circuits in the threaded circuit
partition is maximised.