# Lifting Arc Diagrams Under Branched Covers: An Inverse Problem and its
Solution

Cyrus A. Peterpaul

###### Abstract

A branched covering map of surfaces induces a map in the opposite direction
between their arc complexes. We represent a branched covering map
combinatorially using what we call a lifting picture, and use this
representation to computably solve the membership problem of the set of
weighted arc diagrams on a given surface which can be obtained by lifting a
weighted arc diagram on a bigon. We provide a brute force solution in the
general case, and an efficient solution when the input arc diagram is a
triangulation.

##  1 Introduction

Arc diagrams are simple, combinatorial objects associated to surfaces with
boundary. They consist of homotopy classes of disjoint curves, and can be
thought of as embedded graphs on suitably marked surfaces. Arc diagrams and
the simplicial complexes, known as arc complexes, which can be built from
them, are have been studied by topologists for many years; see, for example,
[3], [5], [2]. This paper examines the behavior of weighted arc diagrams (that
is, diagrams with nonnegative real numbers assigned to each arc) under
topological branched covering maps. A given branched covering map of marked
surfaces induces a map between arcs of the base space and arcs of the total
space by path lifting.

We are interested in the membership problem of the set of weighted arc
diagrams which can be realized by such a process of lifting from a disk with
two marked boundary points, which is referred to as a bigon. That is, given a
weighted arc diagram, decide if it can be realized by lifting the arcs of a
diagram on a bigon under a suitable branched cover. In section 3, we construct
a combinatorial way of representing a topological branched cover which we
refer to as a lifting picture. Because there are finitely many lifting
pictures on a given surface, this problem admits a finite, if computationally
expensive, solution, which we present as algorithm 1.

In the sections which follow, we present a much more efficient solution to
this problem in the case of an arc diagram which is a triangulation of the
surface on which it lives. We tackle this by first presenting solutions to two
special cases in sections 4 and 5, then merging these two special case
solutions to handle a general triangulation in section 6.

##  2 Definitions and Notation

We first need to define a particular kind of marked surface with boundary,
which we will call a _substrate_. The objects and definitions here broadly
track with those in [2].

######  Definition 1.

Let $\Sigma$ be a surface with boundary. Let $V$ be a finite set of distinct
points on the boundary of $\Sigma$ which we call _vertices_. A _2-coloring_ is
a map $V\to\\{\alpha,\beta\\}$ so that no two neighboring vertices are
assigned the same value.

######  Definition 2.

A _substrate_ is a surface $\Sigma$ with boundary equipped with a set
$M_{\Sigma}$ of marked points in the interior of $\Sigma$, a set of vertices
$V_{\Sigma}$, and a 2-coloring $C_{\Sigma}:V_{\sigma}\to\\{\alpha,\beta\\}$.
Each boundary component of $\Sigma$ must contain at least 2 vertices. Call the
componenets of $\partial\Sigma\backslash V_{\Sigma}$ _boundary edges_.

The set $M_{\Sigma}$ will typically be empty except for bigons, which will be
defined shortly. Substrates are the homes of arc diagrams.

######  Definition 3.

Let $\Sigma$ be a substrate and $p:[0,1]\to\Sigma$ be a simple path with
$p(0),p(1)\in V_{\Sigma}$, and $p(t)\not\in M_{\Sigma}$ for all $t$. An _arc_
is the homotopy class relative to $\\{0,1\\}$ of such a path through paths
disjoint from $M_{\Sigma}$.

We will simply say _homotopic_ to mean _homotopic rel endpoints through paths
disjoint from_ $M_{\Sigma}$ in the context of arcs. An arc is called _trivial_
if it is homotopic to a path in the boundary of $\Sigma$ which intersect
$V_{\Sigma}$ only at its endpoints. Otherwise, it is called _nontrivial_. In
particular, an arc which is homotopic to a vertex is trivial. An arc is called
_homonymous_ if $C_{\Sigma}$ takes the same value at both of its endpoints;
that is, if its endpoints are the same color. Otherwise, an arc is called
_heteronymous_.

######  Definition 4.

Two arcs $a$ and $b$ are _noncrossing_ if there are paths representing $a$ and
$b$ that are disjoint except at their endpoints. Otherwise, $a$ and $b$
_cross_.

######  Definition 5.

An _arc diagram_ on a substrate $\Sigma$ is a set of mutually noncrossing arcs
on $\Sigma$.

We will call an arc diagram _clean_ if it contains no trivial arcs. An arc
diagram $D$ is _maximal_ if any nontrivial arc not already in $D$ crosses at
least one arc in $D$. An arc diagram is _fully homonymous_ if it contains only
homonymous arcs. The arcs of a diagram may also be assigned weights.

######  Definition 6.

A _weighted arc diagram_ is an arc diagram $D$ equipped with a map
$w_{D}:D\to{}[0,\infty)$.

######  Definition 7.

A weighted arc diagram $E$ _extends_ a weighted arc diagram $D$ if $D\subset
E$ and $w_{E}=w_{D}$ on the arcs of $D$. $E$ is also called an _extension_ of
$D$.

We will also need to define a branched cover of substrates. Compare to the
definitions of topological branched cover in [6] and [8].

######  Definition 8.

Let $X$ and $Y$ be surfaces. A continuous map $f:X\to Y$ is called a _branched
covering map_ if there is a finite set $\Delta\subset Y$ so that $f$
restricted to $f^{-1}(Y\backslash\Delta)$ is a covering map, and it meets the
following regularity condition. For each $p\in X$ there are open neighborhoods
$U_{p}$ of $p$ and $V_{f(p)}$ of $f(p)$ with charts $\psi:V_{f(p)}\to Z$ and
$\phi:U_{p}\to Z$, where $Z$ is an open neighborhood of 0 in $\mathbb{C}$, so
that the map $\psi\circ f\circ\phi^{-1}:\mathbb{C}\to\mathbb{C}$ is the
complex function $z\to z^{n}$. Note that we are not requiring that $X$ or $Y$
have a complex structure, only that they are topological 2-manifolds.

The smallest such $\Delta$ is called the _singular set_ , and its elements are
_singular values_. $Y\backslash\Delta$ is called the _regular set_ and its
elements likewise called _regular values_. For each $p\in X$, the number $n$
so that $f$ is $z\to z^{n}$ in local coordinates around $p$ and $f(p)$ is
called the _local degree_ of $f$ at $p$, $\deg f(p)$. A point $p$ where $\deg
f(p)>1$ is called a _branch point_.

A branched covering map is called _simple_ if the local degree of $f$ is 2 at
each branch point and the fiber over any singular value contains a unique
branch point.

######  Definition 9.

Let $\Sigma$ and $\Sigma^{\prime}$ be substrates. A _branched cover_ of
$\Sigma^{\prime}$ by $\Sigma$ is a branched covering map
$f:\Sigma\to\Sigma^{\prime}$ which takes $V_{\Sigma}$ to
$V_{\Sigma^{\prime}}$, whose set of singular values is $M_{\Sigma^{\prime}}$
and which commutes with the 2-coloring. That is, for all vertices $v$ of
$\Sigma$, $C_{\Sigma}(v)=C_{\Sigma^{\prime}}(f(v))$. We say that $\Sigma$ is a
branched cover of $\Sigma^{\prime}$ if there exists such a branched covering
map.

We are particularly interested in branched covers of bigons.

######  Definition 10.

A topological disk equipped with the structure of a substrate is a _polygon_.
A polygon with 2 vertices is a _bigon_.

Arcs which share an endpoint are naturally ordered, a property we will use
shortly. Suppose $D$ is an arc diagram on substrate $\Sigma$. Orient each
boundary component of $\Sigma$ so that the interior of $\Sigma$ is on the
left. Choose a set of smooth, disjoint, simple paths realizing $D$. The arcs
incident on a given vertex may now be ordered left to right by the angle of
their inward-pointing tangent vectors at $v$. We call this the _canonical
order_ at each vertex.

######  Proposition 1.

Suppose $f:\Sigma\to\mathcal{B}$ is a simple branched cover. Let $s\in
M_{\mathcal{B}}$ be a singular value, and $\widetilde{s}$ the branch point in
the fiber over $s$. If $p$ is a simple path connecting $s$ to $v$, the union
of the two lifts of $p$ which pass through $\widetilde{s}$ are a path
representing a nontrivial homonymous arc. No other union of lifts of $p$
represents an arc.

###### Proof.

The preimage of $p$ is a collection of paths in $\Sigma$, each of which
connects a point in the fiber over $s$ to a vertex which matches the color of
$v$. Each path has an endpoint on a distinct vertex of $\Sigma$. Two of these
paths, $a$ and $b$, will contain $\widetilde{s}$ as an endpoint; the rest will
have endpoints on distinct points of the fiber over $s$. Therefore, only $a$
and $b$ join together into a path between vertices of $\Sigma$; none of the
rest of the paths fit together into a representative of an arc.

Now it remains to show that $a\cup b$ represents a nontrivial arc. Since $a$
and $b$ will have endpoints on distinct vertices of $\Sigma$, $a\cup b$ is not
a loop. The only trivial, homonymous arcs are loops, so $a\cup b$ represents a
nontrivial arc. ∎

Suppose $f:\Sigma\to\mathcal{B}$ is a branched cover of a bigon by a
substrate. Choose simple, disjoint paths connecting each point of
$M_{\mathcal{B}}$ to a vertex of $\mathcal{B}$. By Proposition 1, each path
$p$ may be asociated with a unique, nontrivial, homonymous arc $\widetilde{p}$
on $\Sigma$, which we call a _branching arc_. We call the set of these arcs a
_branching diagram_ for $f$. If we change these paths by homotopy rel
endpoints and through paths disjoint from $M_{\mathcal{B}}$, the branching
diagram remains constant.

######  Definition 11.

Let $D$ be a branching diagram on $\Sigma$ for the branched cover $f$. A
component of $\Sigma\backslash D$ is called a _sheet_.

######  Proposition 2.

Every sheet $s$ of a simple branched cover $f:\Sigma\to\mathcal{B}$ is simply
connected, and $f$ is a homeomorphism on the interior of $s$.

###### Proof.

The restriction of $f$ to the interior of $s$ is a covering map which sends
interior of $(s)$ to the open set $\mathrm{Int}(\mathcal{B})$ with the images
of the branching arcs in $\partial s$ deleted. This is a simply connected open
set. Since $f$ is injective on the fundamental group of $\mathrm{Int}(s)$, $s$
must be simply connected.

Since $s$ is simply connected, $\chi(s)=1$. This implies that, since
$f|_{\mathrm{Int}(s)}$ is a covering map, $1=\chi(s)=d\chi(f(s))=d$, where $d$
is the degree of $f|_{\mathrm{Int}(s)}$. Hence, $d=1$ and
$f|_{\mathrm{Int}(s)}$ is a homeomorphism. ∎

An important consequence of Proposition 2 is that each sheet of a simple
branched cover contains exactly two boundary edges of $\Sigma$.

Conversely, one can use a branching diagram together with an additional choice
of order to specify a simple branched cover of the bigon. Call an arc diagram
$D$ _ordered_ if there is a total order on the arcs of $D$ which agrees with
the canonical order at each vertex.

######  Proposition 3.

Let $\Sigma$ be a substrate, and $D$ be an ordered arc diagram on $\Sigma$
containing $n=|V_{\Sigma}|/2-\chi(\Sigma)$ homonymous arcs so that each
component of $\Sigma\backslash D$ is simply connected and contains two of
$\Sigma$’s boundary edges. Then there exists a simple branched cover
$f:\Sigma\to\mathcal{B}$ which has $D$ as its branching diagram.

###### Proof.

Let $d_{1},\ldots,d_{n}$ be the arcs of $D$, and number the points of
$M_{\mathcal{B}}$ $m_{1},\ldots,m_{n}$. For $1\leq i\leq n$, connect $m_{i}$
to the vertex which matches the color of the endpoints of $d_{i}$ by a simple
path $p_{i}$ so that the canonical order at each vertex agrees with the order
of the $p_{i}$’s. Let $\phi:\partial\Sigma\cup D\to\mathcal{B}$ which sends
$\partial\Sigma\to\partial\mathcal{B}$, sends vertices to vertices of the same
color, and which sends $d_{i}$ to $p_{i}$.

For each sheet $s$, choose a homeomorphism
$\phi_{s}:\mathrm{Int}(s)\to\mathcal{B}\backslash\phi(\partial s)$ so that the
map $f_{s}:s\to\mathcal{B}$ defined by $f_{s}=\phi_{s}$ on $\mathrm{Int}(s)$
and $\phi$ on $\partial s$ is continuous. Define $f$ to be $f_{s}$ on each
sheet $s$. ∎

An arc on the bigon will have the same lifts under any branched cover with the
same ordered branching diagram, so we will consider branched covers with the
same ordered branching diagram equivalent.

######  Remark 1.

Here is an equivalent definition of substrates and arcs, which is sometimes
convenient. Instead of 2-coloring the vertices of the substrate $\Sigma$, we
can instead 2-color its boundary edges. An arc is now the homotopy class of a
simple path disjoint from $M_{\Sigma}$ with each endpoint on a boundary edge,
through paths disjoint from $V_{\Sigma}$ and $M_{\Sigma}$ which have their
endpoints on $\partial\Sigma$. That is, We allow the ends of the arc to slide
along along a boundary edge, but not into a vertex. All other definitions and
results about arc diagrams may be used with straightforward modifications.

##  3 Lifting and Realizability

Suppose $\Sigma$ and $\mathcal{B}$ are substrates, and $B$ is a weighted arc
diagram on $\mathcal{B}$. Let $f:\Sigma\to\mathcal{B}$ be a branched cover of
substrates. Since $f$ is an ordinary covering map in the complement of
$M_{\mathcal{B}}$, for any arc $a\in B$ we may choose a path $\hat{a}$
representing $a$ and lift $\hat{a}$ to a set of $\deg(f)$-many paths in
$\Sigma$. The homotopy classes of these paths form a set of arcs called the
_lifts_ of $a$. Some of these may be trivial arcs. We denote the set of
nontrivial lifts of $a$ by $\mathcal{L}(a)$.

The branched cover $f:\Sigma\to\mathcal{B}$ together with the weighted arc
diagram $B$ determines a clean, weighted arc diagram $\widetilde{B}$ on
$\Sigma$ in the following way. The set of arcs in $\widetilde{B}$ is the union
of nontrivial lifts

$\bigcup_{b\in B}\mathcal{L}(b)$

of arcs in $B$. For an arc $\widetilde{b}\in\widetilde{B}$, define the weight
by

$w_{\widetilde{B}}(\widetilde{b})=\sum_{\\{b\in
B|\widetilde{b}\in\mathcal{L}(b)\\}}w_{B}(b)$ (1)

That is, the weight of an arc in $\widetilde{B}$ is the sum of the weights of
all arcs which lift to it. It is convenient to treat arcs with weight zero as
essentially trivial. So we impose the following equivalence relation.

######  Definition 12.

Arc diagrams $D$ and $D^{\prime}$ are _equivalent_ if they differ only on
weight zero arcs. That is, if $a\in D\backslash D^{\prime}$, then
$w_{D}(a)=0$, and likewise if $a\in D^{\prime}\backslash D$, then
$w_{D^{\prime}}=0$.

######  Definition 13.

$\widetilde{B}$ is the _lift of_ $B$ _under_ $f$. We also say $B$ _lifts to_
$\widetilde{B}$.

######  Definition 14.

A _lifting picture_ is a quintuple $(\Sigma,C,\prec,\mathcal{B},B)$ consisting
of a substrate $\Sigma$, a branching diagram $C$, an order $\prec$ on $C$, a
bigon $\mathcal{B}$, and an arc diagram $B$ on $\mathcal{B}$.

By Proposition 3, $C,\prec$ determines a branched cover
$\Sigma\to\mathcal{B}$.

######  Definition 15.

Let $L=(\Sigma,C,\prec,\mathcal{B},B)$ be a lifting picture, and $D$ an arc
diagram on $\Sigma$. $L$ _realizes_ $D$ if $B$ lifts under $f$ to $D$. $D$ is
_realizable_ if there exists a lifting picture which realizes $D$.

######  Definition 16.

The _realizability problem_ asks, given a weighted arc diagram $D$ on a
substrate $\Sigma$, to decide whether $D$ is realizable, and to produce a
lifting picture $(\Sigma,C,\prec,\mathcal{B},B)$ which realizes $D$ if one
exists.

Because there are only finitely many lifting pictures on a given substrate,
there is a brute force solution the realizability problem.

######  Algorithm 1.

INPUT: A weighted arc diagram $D$ with weights $w_{D}$ on a substrate
$\Sigma$.
OUTPUT: A lifting picture $(\Sigma,C,\prec,\mathcal{B},B)$ realizing $D$ if
one exists, or the message that no such lifting picture exists.
PROCEDURE: Choose a branching diagram $C$ compatible with $D$ and a valid
order $\prec$ on $C$. Fix a bigon $\mathcal{B}$ with the appropriate number of
interior marked points. Choose an unweighted arc diagram on $\mathcal{B}$. By
propositions 1 and 3, choosing $C$ and $\prec$ specifies a branched covering
map $f:\Sigma\to\mathcal{B}$.

If the arcs of $B$ lift to those of $D$, then we get a linear map $L$ from
vectors of weights $w_{B}$ on $B$ to vectors of weights on $D$. Compute the
Moore-Penrose inverse $L^{+}$ of $L$. The equation $Lw_{B}=w_{D}$ has a
solution if and only if $LL^{+}w_{D}=w_{D}$ [4]. In that case, $L^{+}w_{D}$ is
a solution to $Lw_{B}=w_{D}$, so assign weights $L^{+}w_{D}$ to the arcs of
$w_{B}$, and return the resulting lifting picture
$(\Sigma,C,\prec,\mathcal{B},B)$. Otherwise, try a new combination of $C$,
$\prec$, and unweighted diagram $B$ on $\mathcal{B}$. If all combinations are
exhausted without yielding a solvable equation $Lw_{B}=w_{D}$, then return the
message that $D$ is not realizable.

$\Diamond$

######  Proposition 4.

A clean, maximal arc diagram $D$ on a substrate $\Sigma$ with
$M_{\Sigma}=\emptyset$ defines a triangulation of $\Sigma$, and contains
$N-3\chi(\Sigma)$ arcs, where $N$ is the cardinality of $V_{\Sigma}$ and
$\chi(\Sigma)$ denotes the Euler characteristic.

###### Proof.

$D$ defines a cell decompostition $\mathcal{C}$ of $\Sigma$ as follows: the
set of vertices $V$ of $\mathcal{C}$ is $V_{\Sigma}$, the set of edges $E$
contains the arcs of $D$ and the boundary edges of $\Sigma$, and the set of
2-cells $F$ consists of the closures of the components of $\Sigma\backslash
E$. To see this is a triangulation, suppose there is a 2-cell $C$ that is not
a triangle. If the boundary of $C$ contains at least 4 vertices, then any non-
adjacent pair of vertices in $\partial C$ can be connected by an arc which is
disjoint from $D$ (as it lies in the interior of $C$) and not already in $D$.
This contradicts maximality of $D$. If the boundary of $C$ contains only 1 or
2 vertices, then the interior of $C$ must have genus greater than zero;
otherwise, the boundary of $C$ would collapse under homotopy. In that case,
once again one can add an arc to the diagram, contradictiong maximality. This
is illustrated in Figure 1.

By Euler’s formula, $\chi(\Sigma)=|V|-|E|+|F|$. $N=|V|$. Since $\mathcal{C}$
is a triangulation, $2|D|+\\#\\{\partial\ \mathrm{edges}\\}=3|F|$, where $|D|$
is the number of arcs in $D$. Since there are the same number of vertices as
boundary edges, and $|E|=|D|+\\#\\{\partial\ \mathrm{edges}\\}$, the equation
reduces to $\chi(\Sigma)=N-|D|-N+(2/3)|D|+(1/3)N$, and therefore
$|D|=N-3\chi(\Sigma)$. ∎

Figure 1: A subdiagram consisting of 2 distinct arcs sharing endpoints must
have genus greater than 0. Bold lines represent the boundary of the surface,
fine lines represent arcs. The dashed arc can be added to the diagram, meaning
it is non-maximal.

We now prove some useful facts about lifting arcs from a bigon under a simple
branched cover.

######  Proposition 5.

Let $(\Sigma,C,\prec,\mathcal{B},B)$ be a lifting picture, and $b$ an arc in
$B$. Let $S$ be a sheet of the cover. Then $b$ has a unique lift
$\widetilde{b}$ in $S$. If $b$ is homonymous then $\widetilde{b}$ is
nontrivial if and only if $b$ encloses a singular value $v$ such that the
branch point $\widetilde{v}$ in the fiber over $v$ is contained in the
boundary of $S$. If $b$ is heteronymous, then $\widetilde{b}$ is nontrivial if
and only if $b$ separates two critical values $v$ and $w$.

###### Proof.

Since $f$ restricted to the interior of $S$ is a homeomorphism onto an open
set in $\mathcal{B}$ which contains $b$, $b$ has a unique lift in $S$.

Suppose $b$ is homonymous. First assume $\widetilde{b}$ is nontrivial. Since
$S$ is simply connected, either $\widetilde{b}$ is a branching arc in
$\partial S$ or $\widetilde{b}$ divides $S$ into two nonempty components. If
$\widetilde{b}$ is a branching arc containing branch point $u$, then $b$ is an
arc which encloses $f(b)$. If $\widetilde{b}$ divides $S$ into two components,
then one of those must contain a branch point $u$, and the other contains the
boundary edges of $\Sigma$ present in $\partial S$. Therefore, $b$ must
separate $f(u)$ from $\partial\mathcal{B}$ and hence $b$ encloses a singular
value. Now, assume $b$ encloses a singular value $v$, whose associated branch
point $\widetilde{v}$ is in $\partial S$. Then since $b$ separates $v$ from
$\partial\mathcal{B}$, $\widetilde{b}$ must either separate $\widetilde{v}$
from $\partial\Sigma\cap\partial S$, or be the branching arc containing
$\widetilde{v}$. In either case, $\widetilde{b}$ is nontrivial.

Now, suppose $b$ is heteronymous. First, assume $\widetilde{b}$ is nontrivial.
Then $\widetilde{b}$ separates $S$ into two components. If one of them
contains no branch points, and hence no branching arcs, then it must contain
only $\partial\Sigma\cap\partial S$ and points of $\mathrm{Int}(S)$. But since
$\partial S$ only contains two boundary edges of $\Sigma$, then
$\widetilde{b}$ must be homotopic to one of them, which contradicts
nontriviality. So $\widetilde{b}$ must separate two branch points, and hence
$b$ separates two singular values whose branch points are in $S$. Finally,
assume $b$ separates two singular vaules whose branch points are in $S$. Then
$\widetilde{b}$ must separate those corresponding branch points in $S$, and
hence $\widetilde{b}$ is nontrivial. ∎

######  Corollary 1.

Let $(\Sigma,C,\prec,\mathcal{B},B)$ be a lifting picture, and $b$ a
homonymous arc in $B$ which encloses exactly one singular value $v$. Then $b$
the only nontrivial lift of $b$ is the branching arc $\widetilde{b}$
containing the branch point in the fiber over $b$, and $b$ lifts
$\widetilde{b}$ twice.

###### Proof.

There are exactly two sheets whose boundary contains $\widetilde{b}$, and $b$
lifts to $\widetilde{b}$ on each. By the proposition above, $b$ will lift
trivially on every other sheet. ∎

##  4 Homonymous Recursion

In this chapter, we will show how to decide whether a fully homonymous
weighted arc diagram is realizable, and how to count the ways of realizing it
if so. First, we will define some operations on arc diagrams and substrates
which will be required in the decision algorithm.

######  Definition 17.

A homonymous arc is _outer_ if it forms a triangle, called an _outer triangle_
$\delta(c)$ with two adjacent boundary edges; $c$ is said to _enclose_
$\delta(c)$. If it is also of minimal weight among outer arcs, it is called
_least outer_. If there are also arcs $a$ and $b$ in $D$ which bound a
triangle with $c$ which contains no other arcs of $D$, then that triangle is
unique and called the _inner triangle_ $\Delta(c)$. In particular, every outer
arc in a maximal diagram has an inner triangle. An inner triangle is called
_homonymous_ is it is bounded only by homonymous arcs.

Figure 2: An outer arc $c$. $\Delta(c)$ is bounded by $a$, $b$, and $c$. The
dashed arc $c^{\prime}$ is the dual arc of $c$.

An outer arc $c$ with an inner triangle has a _dual arc_ $c^{\prime}$, which
is the unique nontrivial arc crossing $c$ and connecting a vertex of
$\delta(c)$ to a vertex of $\Delta(c)$. The dual arc is used to define an
operation on a substrate with an arc diagram we call one seam reduction.

######  Definition 18.

_One Seam Reduction:_ Let $\Sigma$ be a substrate with an arc diagram $D$, and
suppose $c$ is an outer arc with homonymous inner triangle $\Delta(c)$. Cut
$\Sigma$ along the homonymous dual arc $c^{\prime}$; that is choose a simple
representative $p^{\prime}$ of $c^{\prime}$, and let $\Sigma^{\prime}$ be the
closure of $\Sigma\backslash c$. The _one seam reduction_ by $c$ is the new
diagram and substrate pair $(\Sigma^{\prime},D\backslash c)$.

Figure 3: Before and after a one seam reduction by $c$.

By performing a one seam reduction, you get a new arc and (possibly
disconnected) substrate with a new, maximal diagram containing one fewer arc.
Two components of the substrate which were separated by a one seam reduction
performed on a triangle $T$ are said to _meet_ at $T$. Since the two legs of
$T$ are both incident on a vertex, one is to the left of the other in the
canonical order. If components $\Sigma^{\prime}$ and $\Sigma^{\prime\prime}$
meet at $T$ and $\Sigma^{\prime}$ contains the left leg of $T$, then
$\Sigma^{\prime}$ meets $\Sigma^{\prime\prime}$ on the left at $T$; otherwise,
it meets $\Sigma^{\prime\prime}$ on the right at $T$.

Call the reverse operation a _one seam join_.

######  Algorithm 2.

_Homonymous Recursion:_
INPUT: A substrate $\Sigma$ with a fully homonymous arc diagram $D$.
OUTPUT: A lifting picture $L$ realizing $D$ if one exists.
PROCEDURE: The base case is when $\Sigma$ is a square. $D$ has only one arc
$d$, with weight $w$ and color $c$. Let $\mathcal{B}$ be a bigon with
$M_{\mathcal{B}}$ containing a single point $p$. Let $B$ be an arc diagram
consisting of a single homonymous arc $b$ with color $c$ enclosing $p$, and
with weight $w/2$. The branching diagram is just $D$. Return the lifting
picture $(\Sigma,D,\mathcal{B},B)$.

Suppose $\Sigma$ is not a square. Let $\mathcal{O}(D)$ be the set of least
outer arcs of $D$, which all have weight $w_{\mathcal{O}}$. Perform a one-seam
reduction along each element of $\mathcal{O}(D)$. If the resulting substrate
is connected, return that $D$ is not realizable. Order the components of the
resulting substrate $\Sigma_{1},\ldots,\Sigma_{k}$ so that if $\Sigma_{i}$
meets $\Sigma_{j}$ on the left anywhere, then $i<j$. If no such order exists,
return that $D$ is not realizable. One may find this order using, for example,
a depth first search. This is a special case of a topological sort, and can be
done in linear time; see section 22.4 of [1]. Perform this procedure
recursively on each $\Sigma_{i}$.

If none of these return that the diagram is not realizable, then they return
lifting pictures $L_{1},\ldots,L_{k}$. Let $B$ be the diagram containing
diagrams $B_{1},\ldots,B_{k}$ as subdiagrams arranged in order, with one extra
arc of weight $w_{\mathcal{O}}$ enclosing all of them. The branching diagram
$C$ is the union $C_{1}\cup\ldots\cup C_{k}$ from $L_{1},\ldots,L_{k}$. The
order $\prec$ on $C$ is defined by requiring it to extend each $\prec_{i}$ on
$C_{i}$; and if $c\in C_{i},c^{\prime}\in C_{j}$, $i<j$, then $c\prec
c^{\prime}$. Return the lifting picture $(\Sigma,C,\prec,\mathcal{B},B)$.
$\Diamond$

######  Lemma 1.

Let $(\Sigma,C,\prec,\mathcal{B},B)$ be a lifting picture, and suppose $b\in
B$ is a homonymous arc of color $c$ which encloses every singular value. If
$\Sigma$ is not a square, then the set of lifts of $b$ is the set of outer
arcs of color $c$ in $\Sigma$. If $\Sigma$ is not a square, then $b$ lifts to
each one once.

###### Proof.

Each sheet $S$ contains a unique outer arc $\omega(S)$ whose outer triangle is
contained in $S$. Equivalently, $\omega(S)$ separates the branching arcs in
$\partial S$ from $\partial\Sigma\cap\partial S$. By Proposition 5, $b$ has a
unique nontrivial lift $\widetilde{b}$ on every sheet $S$. Since $b$ separates
all singular values from $\partial\mathcal{B}$, $\widetilde{b}$ separates the
branching arcs of $\partial S$ from $\partial\Sigma\cap S$, so
$\widetilde{b}=\omega(S)$.

If $\Sigma$ is not a square, then no two sheets $S,S^{\prime}$ can have
$\omega(S)=\omega(S^{\prime})$. ∎

######  Theorem 1.

Let $D$ be a maximal, homonymous diagram on substrate $\Sigma$. Homonymous
recursion returns a lifting picture realizing $D$ if and only if $D$ is
realizable.

###### Proof.

Suppose the lifting picture $L=(\Sigma,C,\prec,\mathcal{B},B)$ is the result
of performing homonymous recursion on $D$. We must show that $L$ realizes $D$.
We proceed by induction on the number of arcs $|D|$ in $D$. Suppose $|D|=1$.
Then $\Sigma$ must be a square. It follows from Proposition 5 and its
corollary that $L$ as returned by the base case of homonymous recursion
realizes $D$. Now, assume that for any maximal, homonymous arc diagram $D$
with $|D|<N$ for some $N$, that if homonymous recursion returns a lifting
picture, then that lifting picture realizes $D$. Suppose $D$ is a maximal,
homonymous diagram with $|D|=N$.

Let $\mathcal{O}$ be the set of least weighted outer arcs of $D$, and let
$w_{\mathcal{O}}$ be the weight of any one of these arcs. Let $D^{\prime}$ be
$D\backslash\mathcal{O}$ with the weights of all outer arcs reduced by
$w_{\mathcal{O}}$, and define $\Sigma_{1},\ldots,\Sigma_{k}$ to be the
components resulting from performing a one seam reduction along each arc in
$\mathcal{O}$. We then have maximal diagrams $D_{1},\ldots,D_{k}$ which are
the restriction of $D^{\prime}$ to each $\Sigma_{i}$. Since homonymous
recursion finishes when applied to $D$, that means that $k\geq 2$ and we have
lifting pictures $L_{i}=(\Sigma_{i},C_{i},\prec_{i},\mathcal{B}_{i},B_{i})$,
$1\leq i\leq k$. By the inductive assumption, $L_{i}$ realizes $D_{i}$, since
$|D_{i}|<N$.

We now must show $C=C_{1}\cup\ldots\cup C_{k}$ is a valid branching diagram.
By construction, and using the assumption that homonymous recursion
successfully terminated, the order of $\Sigma_{1},\ldots,\Sigma_{k}$ is
compatible with the canonical order at each vertex. Therefore, by induction,
the order on $C$ extends the canonical order at each vertex, as it must. It
remains to show that each component of $\Sigma\backslash C$ is simply
connected and contains two edges of $\partial\Sigma$. Let $S$ be a component
of $\Sigma\backslash C$. If $S$ is contained in some $\Sigma_{i}$, then it is
a valid sheet by the inductive hypothesis. Otherwise, $S$ is the result of
performing one seam joins on sheets in various $\Sigma_{i}$’s. But since a
sheet of any $\Sigma_{i}$ contains a unique outer arc along which to perform a
one seam join, $S$ must be the result of performing a one seam join on two
sheets, meaning that $S$ is simply connected and has the correct boundary. So
$C$ is a valid branching diagram.

Now we must show that $L$ realizes $D$. If $b_{i}$ is an arc in $B_{i}\subset
B$, then by prop 5 all nontrivial lifts will be in $\Sigma_{i}$, since the
branch points mapped to the singular values enclosed by $b_{i}$ are all
contained in $\Sigma_{i}$. Therefore, $B_{i}$ lifts to $D_{i}$ in the combined
lifting picture $L$. Then the lift of $B_{1}\cup\ldots\cup
B_{k}=B\backslash\omega$, where $\omega$ is the unique arc in $B$ which
encloses all of $M_{\mathcal{B}}$, is $D_{1}\cup\ldots\cup D_{k}=D^{\prime}$.
Since $\omega$ lifts to every outer arc once by the lemma, $L$ realizes $D$.

Finally, suppose $D$ is a realizable, maximal, homonymous weighted arc diagram
on $\Sigma$. We need to show that homonymous recursion returns a lifting
picture when applied to $D$. Suppose
$R=(\Sigma,C_{R},\prec,\mathcal{B},B_{R})$ is a lifting picture which realizes
$D$. Let $\omega$ be the arc in $B$ which encloses $M_{\mathcal{B}}$, and
consider the set $A$ of nontrivial arcs in $\mathcal{B}$ which cross $\omega$
and which are disjoint from the rest of $B$. The set of nontrivial lifts of
arcs in $A$ is exactly the set of dual arcs of the least outer arcs of $D$.
Since the arcs of $A$ divide $\mathcal{B}$ into multiple components, and these
arcs are disjoint from the singular values, the set of lifts of these arcs
must divide $\Sigma$ into at least 2 components, and these components will
have a consistent left-right orientation as required in the algorithm.
Therefore, one seam reduction will take place, and the algorithm will recurse
onto the components. Finally, we need only observe that each component
$\Sigma_{i}$ will have fewer boundary marked points than $\Sigma$, so
therefore this process must terminate, and homonymous recursion thus returns a
lifting picture. ∎

##  5 Heteronymous Arcs

To address the question of realizability for more general arc diagrams, we
will first treat another special case.

######  Definition 19.

A maximal arc diagram on a substrate $\Sigma$ is _maximally heteronymous_ if
it contains exactly $|V_{\Sigma}|/2-\chi(\Sigma)$ homonymous arcs.

A maximally heteronymous diagram has only one possible choice of branching
diagram. The only freedom is in choosing a total order. As in the homonymous
case, each sheet imposes an ordering on the branching arcs which form its
boundary. A sheet of a maximally heteronymous diagram will be of the form
shown in Figure 4.

Figure 4: A typical sheet of a maximally heteronymous diagram.

For each color $c$, the canonical order at vertices orders the branching arcs
of color $c$ in a sheet $S$. If $D$ is also maximal, then the heteronymous
arcs contained in $S$ impose a canonical order on all branching arcs in
$\partial S$. Globally fix a color $c$. Orient each heteronymous arc so it
points out of its $c$-colored endpoint. Each heteronymous arc separates $S$
into two components, and with the orientation one of these will be on the
left, and the other on the right. Define an order $<_{c}$, on the homonymous
arcs bounding $S$ by requiring $x<_{c}y$ if $x$ comes before $y$ in the
canonical order at a common endpoint; or if there exists a heteronymous arc
$h$ so that $x$ is on the left of $h$ and $y$ is on its right. Since $D$ is
maximal, every pair of homonymous arcs in $S$ is separated by at least one
heteronymous arc, so this is a total order on the branching arcs which bound
$S$. Note that if we choose the opposite color $c^{\prime}$, then $x<_{c}y$ if
and only if $y<_{c^{\prime}}x$.

######  Proposition 6.

Let $D$ be a maximal, maximally heteronymous arc diagram on a substrate
$\Sigma$. If the lifting picture $(\Sigma,C,\prec,\mathcal{B},B)$ realizes
$D$, then the order $\prec$ on $C$ extends $<_{c}$.

###### Proof.

Assume to the contrary that $\prec$ does not extend $<_{c}$. Then on some
sheet $S$ there is a pair of branching arcs, $x$ and $y$, and a heteronymous
arc $h$, such that $x$ is left of $h$ and $y$ is on the right, but $y\prec x$.
If $x$ and $y$ have the same colored endpoints, then this reverses the
canonical order at a vertex, so $(\Sigma,C,\prec,\mathcal{B},B)$ doesn’t
define a branched cover. Otherwise, since $y\prec x$, there is no arc in $B$
which separates the singular values $v_{x}$ from $v_{y}$ associated with $x$
and $y$, respectively, and puts $v_{x}$ to the left of $v_{y}$. Therefore, no
arcs in $B$ can lift to $h$, and therefore $(\Sigma,C,\prec,\mathcal{B},B)$
does not realize $D$. ∎

If a maximal, maximally heteronymous diagram $D$ is realizable, then it must
be realized by a maximal, maximally heteronymous diagram, which on the bigon
has the following form.

Figure 5: A maximal, maximally heteronymous diagram on the bigon. A
heteronymous arc separates each pair of homonymous arcs.

Suppose that $a$ is a heteronymous arc in $D$, and let
$f:\Sigma\to\mathcal{B}$ be a branched cover. $a$ is inside a sheet $S$
bounded by branching arcs, which have canonical order $<_{c}$. $a$ divides the
branching arcs in $\partial S$ into two sets $X$ and $Y$, with $X<_{c}Y$. Let
$x$ be the greatest element of $X$ and $y$ be the least element of $Y$. All
the hetermonymous arcs between $f(x)$ and $f(y)$ will lift to $a$.

Therefore, to realize a maximal, maximally hetermonymous diagram $D$ is to
find a total order on the homonymous arcs of $D$ which agrees with $<_{c}$ on
each sheet and apportions weight to the heteronymous arcs of a diagram on the
bigon of the form shown in Figure 5 so that the total weight in the bigon
between any arc and its successor in a given sheet is exactly the weight of
the heteronymous arc upstairs which separates them on that sheet. We will
build this procedure from several more elementary algorithms.

We can represent a sheet $S$ by a list of the form

$b_{0},w_{1},b_{1},w_{2},b_{3},\ldots,w_{k},b_{k}$ (2)

where the $b_{i}$ are the branching arcs in canonical order, and $w_{i}$ is
the weight of the heteronymous arc between $w_{i-1}$ and $w_{i}$.

######  Algorithm 3.

_Free Merge._
INPUT: Lists $X=w_{1}^{X},x_{1},\ldots,w_{m}^{X},x_{m}$ and
$Y=w_{1}^{Y},y_{1},\ldots,w_{n}^{Y},y_{n}$ of the form in eq. 2 with
$\\{x_{1},\ldots,x_{m}\\}\cap\\{y_{1},\ldots,y_{n}\\}=\emptyset$.
OUTPUT: A list $w_{1}^{Z},z_{1},\ldots,w_{m+n}^{Z},z_{m+n}$.
PROCEDURE: The algorithm is defined recursively. The base case is when $X$ or
$Y$ is empty. In that case, return the nonempty list.

If $X$ and $Y$ are both nonempty, let
$w_{1}^{Z}=\min\\{w_{1}^{X},w_{1}^{Y}\\}$. If $w_{1}^{X}<w_{1}^{Y}$, then let
$X^{\prime}=w_{2}^{X},\ldots,x_{m}$,
$Y^{\prime}=w_{1}^{Y}-w_{1}^{X},y_{1},\ldots,y_{n}$, and $z_{1}=x_{1}$.
Otherwise, let $X^{\prime}=w_{1}^{X}-w_{1}^{Y},x_{2},\ldots,x_{m}$,
$Y^{\prime}=w_{2}^{Y},y_{2},\ldots,y_{n}$, and $z_{1}=y_{1}$. Return
$Z=w_{1}^{Z},z_{1}||FreeMerge(X^{\prime},Y^{\prime})$ where $||$ denotes
concatenation. $\Diamond$

######  Proposition 7.

Algorithm 3, when applied to lists $X=w_{1}^{X},x_{1},\ldots,w_{m}^{X},x_{m}$
and $Y=w_{1}^{Y},y_{1},\ldots,w_{n}^{Y},y_{n}$ returns a list
$Z=w_{1}^{Z},z_{1},\ldots,w_{m+n}^{Z},z_{m+n}$ satisfying the following
properties:

  1. 1.

$\\{z_{1},\ldots,z_{m+n}\\}=\\{x_{1},\ldots,x_{n}\\}\cup\\{y_{1},\ldots,y_{m}\\}$

  2. 2.

If $z_{i}=x_{a}$ and $z_{j}=x_{b}$, then $a<b$ implies $i<j$; likewise if
$z_{i}=y_{a}$ and $z_{j}=y_{b}$, then $a<b$ implies $i<j$.

  3. 3.

$w_{1}^{X}=\sum_{i=1}^{k}w_{i}^{Z}$, where $z_{k}=x_{1}$. Similarly,
$w_{1}^{Y}=\sum_{i=1}^{k}w_{i}^{Z}$, where $z_{k}=y_{1}$.

  4. 4.

For each $1\leq i\leq m$, let $z_{a}=x_{i}$ and $z_{b}=x_{i+1}$. Then
$w_{i+1}^{X}=\sum_{j=a}^{b}w_{j}^{Z}$, and likewise for $z_{a}=y_{i-1}$ and
$z_{b}=y_{i}$.

###### Proof.

First, observe that this algorithm always terminates after no more than $m+n$
steps of the recursion. This is because we remove the first 2 elements of
either $X$ or $Y$ to make $X^{\prime}$ and $Y^{\prime}$, so at most we can
only do this $m$ times to $X$ and $n$ times to $Y$.

$Z$ trivially satisfies properties 1-4 when $X$ or $Y$ is empty. To show this
in general, we will induct on the combined length of the lists, $n+m$. The
base case, $n+m=1$, is a special case of $X$ or $Y$ being empty. Assume $Z$
has properties 1-4 when $n+m\leq N$ for some $N$, and suppose $n+m=N+1$. Let
$X^{\prime}$ and $Y^{\prime}$ be as described in algorithm 3.

We need to check that the list $Z=w_{1}^{Z},z_{1}||Z^{\prime}$, where
$Z^{\prime}=FreeMerge(X^{\prime},Y^{\prime})$, has the properties above.
Properties 1 and 2 follow from the definitions of $z_{1}$, $X^{\prime}$, and
$Y^{\prime}$, and the assumption that these properties hold for
$FreeMerge(X^{\prime},Y^{\prime})$. To show $Z$ has property 3, WLOG assume
that $w_{1}^{Z}=w_{1}^{X}$ and $z_{1}=x_{1}$; otherwise, just switch the roles
of $X$ and $Y$. Let $z_{k}=y_{1}$. Then using the inductive hypothesis it
suffices to show that

$w_{1}^{Y}=\sum_{j=1}^{k}w_{j}^{Z}$

Now, $\sum_{j=1}^{k}w_{j}^{Z}=w_{1}^{X}+\sum_{j=1}^{k}w_{j}^{Z^{\prime}}$. By
definition $w_{1}^{Y^{\prime}}=w_{1}^{Y}-w_{1}^{X}$ and by the inductive
hypothesis, $w_{1}^{Y^{\prime}}=\sum_{j=1}^{k}w_{j}^{Z^{\prime}}$. So
$\sum_{j=1}^{k}w_{j}^{Z}=w_{1}^{X}+w_{1}^{Y^{\prime}}=w_{1}^{Y}$. Property 4
now also follows. ∎

Now we will treat merging lists of the form in eq. 2 with $x_{0}=y_{0}$ and
$x_{m}=y_{n}$ so that the result also satisfies a result like Proposition 7.

######  Algorithm 4.

_Constrained Merge._
INPUT: Lists $X=x_{0},w_{1}^{X},x_{1},\ldots,w_{m}^{X},x_{m}$ and
$Y=y_{0},w_{1}^{Y},y_{1},\ldots,w_{n}^{Y},y_{n}$ of the form in eq. 2 with
$x_{0}=y_{0}$ and $x_{m}=y_{n}$, and such that

$\sum_{i=1}^{m}w_{i}^{X}=\sum_{j=i}^{n}w_{i}^{Y}$

OUTPUT: A list $Z=z_{0},w_{1}^{Z},z_{1},\ldots,w_{m+n}^{Z},z_{m+n}$.
PROCEDURE: Let $z_{0}=x_{0}$. Compute

$Z^{\prime}=FreeMerge(w_{1}^{X},x_{1},\ldots,w_{m}^{X},x_{m},w_{1}^{Y},y_{1},\ldots,w_{n}^{Y},y_{n})$

The last 2 terms of $Z^{\prime}$ will be $0,x_{m}$ or $0,y_{n}$. Let
$Z^{\prime\prime}$ be $Z^{\prime}$ with the last 2 terms deleted. Return
$Z=z_{0}||Z^{\prime\prime}$. $\Diamond$

######  Proposition 8.

Algorithm 4, when applied to lists
$X=x_{0},w_{1}^{X},x_{1},\ldots,w_{m}^{X},x_{m}$ and
$Y=y_{0},w_{1}^{Y},y_{1},\ldots,w_{n}^{Y},y_{n}$ satisfying the assumptions in
algorithm 4 returns a list
$Z=z_{0},w_{1}^{Z},z_{1},\ldots,w_{m+n}^{Z},z_{m+n}$ satisfying the following
properties:

  1. 1.

$\\{z_{1},\ldots,z_{m+n}\\}=\\{x_{1},\ldots,x_{n}\\}\cup\\{y_{1},\ldots,y_{m}\\}$

  2. 2.

If $z_{i}=x_{a}$ and $z_{j}=x_{b}$, then $a<b$ implies $i<j$; likewise if
$z_{i}=y_{a}$ and $z_{j}=y_{b}$, then $a<b$ implies $i<j$.

  3. 3.

For each $1\leq i\leq m+n$, let $z_{a}=x_{i-1}$ and $z_{b}=x_{i}$. Then
$w_{i}^{X}=\sum_{j=a}^{b}w_{j}^{Z}$, and likewise for $z_{a}=y_{i-1}$ and
$z_{b}=y_{i}$

###### Proof.

Property 2 is automatic given prop 7. Property 1 follows from the fact that
the homonymous arcs $z_{1}^{\prime},\ldots,z_{k}^{\prime}$ in

$Z^{\prime}=FreeMerge(w_{1}^{X},x_{1},\ldots,w_{m}^{X},x_{m},w_{1}^{Y},y_{1},\ldots,w_{n}^{Y},y_{n})$

will be the disjoint union of the arcs in the arguments of $FreeMerge$. Since
the total weight in both lists is equal, the last 2 terms of $Z^{\prime}$ will
be either $0,x_{m}$ or $0,y_{m}$. Therefore, after discarding the spurious
last 2 terms of $Z^{\prime}$, property 1 holds, and property 3 also follows
from that fact and prop 7. ∎

We now generalize to all lists of the form in eq. 2. Now, we allow any number
of arcs in the two lists to coincide.

######  Algorithm 5.

_General Merge._
INPUT: Lists $X=x_{0},w_{1}^{X},x_{1},\ldots,x_{m}$ and
$Y=y_{0},w_{1}^{Y},y_{1},\ldots,y_{n}$ of the form in eq. 2.
OUTPUT: A list $Z=z_{0},w_{1}^{Z},z_{1},\ldots,z_{k}$ of the form in eq. 2.
PROCEDURE: Compute the set of arcs $A$ which appear in both $X$ and $Y$.
Define index functions $\sigma,\eta$ by, for each arc $a\in A$,
$x_{\sigma(a)}=a$ and $y_{\eta(a)}=a$. For each pair $a,b$ of arcs in $A$,
with $\sigma(a)<\sigma(b)$, first check that $\eta(a)<\eta(b)$. Otherwise,
raise an exception. Next, check that

$\sum_{i=\sigma(a)+1}^{\sigma(b)}w_{i}^{X}=\sum_{j=\eta(a)+1}^{\eta(b)}w_{j}^{Y}$

If that equation is not satisfied, raise an exception.

Now, let $A=\\{a_{1},\ldots,a_{k}\\}$. Partition $X$ into sublists

$X_{0}=x_{0},w_{1}^{X},\ldots,x_{\sigma(a_{1})-1},w_{\sigma(a_{1})},$
$X_{1}=x_{\sigma(a_{1})},\ldots,x_{\sigma(a_{2})}$ $\ldots$
$X_{k}=w_{\sigma(a_{k})+1}^{X},x_{\sigma(a_{k})+1},\ldots,x_{m}$

Partition $Y$ into sublists $Y_{0},\ldots,Y_{k}$ in the same way. Define
$Z^{\prime}$ to be

$(FreeMerge(X_{0}^{*},Y_{0}^{*}))^{*}||ConstrainedMerge(X_{1},Y_{1})||\ldots||FreeMerge(X_{k},Y_{k})$

where ∗ denotes reindexing in opposite order. Concatenating
$ConstainedMerge(X_{i},Y_{i})$ with $ConstainedMerge(X_{i+1},Y_{i+1})$ results
in duplicate, adjacent $a_{i}$. Remove all these duplicates from $Z^{\prime}$
and call the resulting list $Z$. Return $Z$. $\Diamond$

Now, as an immediate corollary of propositions 7 and 8, we have

######  Proposition 9.

If algorithm 5 does not raise an exception when applied to lists
$X=x_{0},w_{1}^{X},x_{1},\ldots,w_{m}^{X},x_{m}$ and
$Y=y_{0},w_{1}^{Y},y_{1},\ldots,w_{n}^{Y},y_{n}$ satisfying the assumptions in
algorithm 5, then it returns a list
$Z=z_{0},w_{1}^{Z},z_{1},\ldots,w_{m+n}^{Z},z_{m+n}$ satisfying the following
properties:

  1. 1.

$\\{z_{1},\ldots,z_{m+n}\\}=\\{x_{1},\ldots,x_{n}\\}\cup\\{y_{1},\ldots,y_{m}\\}$

  2. 2.

If $z_{i}=x_{a}$ and $z_{j}=x_{b}$, then $a<b$ implies $i<j$; likewise if
$z_{i}=y_{a}$ and $z_{j}=y_{b}$, then $a<b$ implies $i<j$.

  3. 3.

For each $1\leq i\leq m+n$, let $z_{a}=x_{i-1}$ and $z_{b}=x_{i}$. Then
$w_{i}^{X}=\sum_{j=a}^{b}w_{j}^{Z}$, and likewise for $z_{a}=y_{i-1}$ and
$z_{b}=y_{i}$

We can now define the algorithm for realizing a maximal, maximally
heteronymous arc diagram.

######  Algorithm 6.

_Heteronymous Realization._
INPUT: A maximal, maximally heteronymous weighted arc diagram $D$ on a
substrate $\Sigma$.
OUTPUT: A lifting picture $L=(\Sigma,C,\prec,\mathcal{B},B)$.
PROCEDURE: Let $C$ be the set of homonymous arcs in $D$. Check that each
component of the complement of $C$ is simply connected; if not, raise an
exception. Check that $\partial C$ contains 2 edges of $\partial\Sigma$;
otherwise, raise an exception.

For each component $S$ of the complement of $C$, compute the list
$X(S)=x_{0},w_{1},x_{1},\ldots,w_{n},x_{n}$, where $x_{0},\ldots,x_{n}$ are
the arcs of $C$ bounding $S$, and $w_{i}$ is the weight of the heteronymous
arc between $x_{i-1}$ and $x_{i}$. Choose a component $T_{0}$ of
$\Sigma\backslash C$. Let $Z_{0}=X(T_{0})$. Choose a component $U$ adjacent to
$T_{0}$. Let $T_{1}=T_{0}\cup U$. Compute $Z_{1}=GeneralMerge(Z_{0},X(U))$. If
$T_{1}=\Sigma$, then we are done. Otherwise, choose a component $U$ to
$T_{1}$. Let $T_{1}=T_{0}\cup U$, and compute
$Z_{1}=GeneralMerge(Z_{1},X(U))$. Continue in this fashion until, for some
$k$, $T_{k}=\Sigma$.

The order in which each arc of $C$ appears in $Z_{k}$ defines the order
$\prec$ on $C$. Construct $B$ as follows.
$Z_{k}=z_{0},w_{1},z_{1},\ldots,w_{n},z_{n}$. For $0\leq i\leq n$, enclose
$m_{i}\in M_{\mathcal{B}}$ by a homonymous arc with endpoints the same color
as those of $z_{i}$. Assign it half the weight of $z_{i}$. Place a
heteronymous arc between $z_{i}$ and $z_{i+1}$, and assign its weight to be
$w_{i}$. Return $(\Sigma,C,\prec,\mathcal{B},B)$. $\Diamond$

######  Theorem 2.

Let $D$ be a maximal, maximally heteronymous weighted arc diagram on a
substrate $\Sigma$. Then algorithm 6 returns a lifting picture if and only if
$D$ is realizable, and the lifting picture it returns realizes $D$.

###### Proof.

Suppose that Algorithm 6 returns $L=(\Sigma,C,\prec,\mathcal{B},B)$ when
applied to $D$. It follows from Proposition 5 that $L$ realizes $D$ as an
unweighted diagram; it remains to show that each arc of $D$ gets the correct
weight. It follows from Proposition 5 that the homonymous arcs all get the
correct weight. Let $h\in D$ be a heteronymous arc. It is contained in some
sheet $S$. Let $c_{k},c_{\ell}$ be the pair of arcs which flank $h$ in $S$,
where the indices indicate their index in $C$ under $\prec$. Again by
Proposition 5, the heteronymous arcs in $B$ between critical values $m_{k}$
and $m_{\ell}$ will lift to $h$. The weights of those arcs are
$w_{k+1},\ldots,w_{\ell}$. By Proposition 9, $\sum_{i=k+1}^{\ell}w_{i}$ is
equal to the weight of $h$, so $L$ realizes $D$.

Now, suppose $D$ is realizable. We want to show that Algorithm 6 finishes
without throwing an exception. Since $D$ is realizable, there exists a
branched cover $f:\Sigma\to\mathcal{B}$ and a weighted arc diagram $B$ on
$\mathcal{B}$, so that $B$ lifts to $D$ under $f$. There is a unique up to
homotopy set of branch cuts disjoint from and parallel to the homonymous arcs
of $B$ which connect the critical values $M_{\mathcal{B}}$ to the vertices of
$\mathcal{B}$. Therefore, we can assume that the branch cuts lift to the
homonymous arcs $C$ of $D$. That implies that there are no cycles in $C$; that
each component of $D\backslash C$ is simply connected, as these are sheets of
a branched cover of a disk; and that the canonical order of homonymous arcs
bounding each sheet extends to a total order on $C$. Finally, we need to show
that when we merge a sheet with a connected union of sheets, the condition on
sums of weights in Algorithm 5 is satisfied. This follows from Proposition 5
and Lemma 2. ∎

######  Lemma 2.

Let $A,B,C$ be lists of the form required by Algorithm 5. Then
$\mathrm{MERGE}(\mathrm{MERGE}(A,B),C)=\mathrm{MERGE}(\mathrm{MERGE}(A,C),B)$.

###### Proof.

Let $X=\mathrm{MERGE}(\mathrm{MERGE}(A,B),C)$ and
$Y=\mathrm{MERGE}(\mathrm{MERGE}(A,C),B)$, where $\mathrm{MERGE}$ performs
algo 5. Delete the arcs of $C$ not appearing in $A$ or $B$ from $Y$ and add
any weights which are now adjacent; call the result $Z$. On one hand,
$Z=\mathrm{MERGE}(A,B)$. On the other hand, clearly $\mathrm{MERGE}(Z,C)=Y$,
so $X=Y$. ∎

##  6 General Maximal Diagrams

We now put the results of the previous sections together to decide whether any
maximal arc diagram is realizable. A generic maximal diagram is composed of
connected, maximal, fully homonymous subdiagrams separated by heteronymous
arcs. On a bigon, a generic diagram has the form shown in Figure 7.

######  Definition 20.

A _homonymous clump_ is a maximal, connected, homonymous subdiagram.

Let $H_{1},\ldots,H_{n}$ be the set of homonymous clumps in $D$. Each $H_{i}$
has a boundary consisting of homonymous arcs which are side of a triangle with
a heteronymous arc. Call these arcs _outer to_ $H_{i}$. We may cut $\Sigma$
along each of these arcs and paste in triangles as shown in Figure 6. Let
$\Sigma_{i}$ be the component of the resulting surface which contains $H_{i}$.

Figure 6: Cutting along the homonymous arc $a$. Figure 7: Each $B_{i}$ is a
maximal, homonymous subdiagram.

Each component of the complement of $\Sigma_{1}\cup\ldots\cup\Sigma_{n}$ is
either an outer triangle bounded by 2 edges of $\partial\Sigma$ and a
homonymous arc, or a region of the form shown in Figure 4 which we will call a
heteronymous ladder.

######  Definition 21.

Let $D$ be an arc diagram. A _heteronymous ladder_ is a region of $\Sigma$
bounded by homonymous arcs of $D$ which contains only heteronymous arcs in its
interior.

This all suggests that to realize a diagram $D$, one can perform homonymous
recursion to realize each homonymous clump individually, and then use a
version of Algorithm 6 to order these $H_{i}$ and assign weights to the the
heteronymous arcs separating the diagrams which realize each $H_{i}$
downstairs.

######  Definition 22.

Let $(\Sigma,C,\prec,\mathcal{B},B)$ be a lifting picture realizing a diagram
$D$ on $\Sigma$, and $E$ be a maximal, connected homonymous subdiagram of $B$.
We say that $E$ has _connected branching_ if the set of branching arcs whose
critical points are enclosed by arcs of $E$ all are contained in a single
connected, homonymous subdiagram of $D$.

A maximal diagram consists of honomyous clumps and heteronymous ladders. Each
heteronymous ladder can be given a canonical total order, just as in the case
of the sheets of a maximally heteronymous diagram. We now show that, in
essence, clumps lift to clumps. For this we’ll need a procedure we call
_weight rebalancing_.

######  Definition 23.

Let $D$ be an arc diagram, $(\Sigma,C,\prec,\mathcal{B},B)$ be a lifting
picture realizing $D$, and $h\in B$ a homonymous arc. The _branching_ of $h$
is the set of arcs in $C$ whose critical points are mapped into the region
enclosed by $h$. We say $h$ has _connected branching_ if the branching of $h$
is contained in one homonymous clump of $D$. Otherwise, $h$ has _disconnected_
branching.

######  Definition 24.

Let $D$ be an arc diagram, $(\Sigma,C,\prec,\mathcal{B},B)$ be a lifting
picture realizing $D$, and $h\in B$ a homonymous arc. A _new lift_ of $h$ is
an arc in $D$ which is not a lift of any arc in $B$ enclosed by $h$.

If a homonymous arc has no new lifts, then we may perform the following
opertaion on $B$ without changing its lift.

######  Definition 25.

_Pushing down weight._ Let $(\Sigma,C,\prec,\mathcal{B},B)$ be a lifting
picture, $w_{B}$ be the weight function on $B$, and $h\in B$ a homonymous arc.
Let $h_{1},\ldots,h_{k}$ be the outermost arcs enclosed by $h$; that is, each
$h_{i}$ is enclosed by $h$ and not by any other arc enclosed by $h$. Define
$P_{h}(B)$ to be $B$ with $h$ deleted and with
$w_{P_{h}}(h_{i})=w_{B}(h_{i})+w_{B}(h)$. We say that we have _pushed down_
the weight of $h$ to make $(\Sigma,C,\prec,\mathcal{B},P_{h}(B))$.

######  Lemma 3.

Let $D$ be a weighted arc diagram, and suppose that
$(\Sigma,C,\prec,\mathcal{B},B)$ realizes $D$. If $h$ is a homonymous arc in
$B$ with no new lifts, then the diagram
$(\Sigma,C,\prec,\mathcal{B},P_{h}(B))$ also realizes $D$.

###### Proof.

Let $h_{1},\ldots,h_{k}$ be the outermost arcs enclosed by $h$. By assumption
every lift of $h$ is also a lift of some $h_{i}$. Therefore,
$(\Sigma,C,\prec,\mathcal{B},P_{h}(B))$ still realizes $D$ as an unweighted
diagram. Furthermore, since $w_{P_{h}}(h_{i})=w_{B}(h_{i})+w_{B}(h)$, the
weight previously contributed by $h$ to the lifts of $h_{i}$ is not
contributed directly by $h_{i}$, so $(\Sigma,C,\prec,\mathcal{B},P_{h}(B))$
also realizes $D$ as a weighted diagram. ∎

######  Proposition 10.

If $D$ is a maximal, realizable weighted arc diagram, then $D$ is realized by
a lifting picture where every homonymous arc has connected branching.

###### Proof.

Suppose $(\Sigma,C,\prec,\mathcal{B},B)$ realizes $D$. If there is an arc $h$
with no new lifts, push down the weight of $h$. repeat this until every arc
has new lift. Call the resulting lifting picture
$(\Sigma,C,\prec,\mathcal{B},B^{\prime})$. By Lemma 3,
$(\Sigma,C,\prec,\mathcal{B},B^{\prime})$ realizes $D$.

Define $\epsilon(a)$ be the number of critical values enclosed by homonyous
arc $a$. Let $h\in B^{\prime}$ be the arc with the smallest $\epsilon(h)$ such
that $h$ has disconnected branching. We know that $h$ must have a new lift.
Let $h_{1},\ldots,h_{k}$ be the homonymous clumps enclosed by $h$. Each
$h_{i}$ has connected branching. Since $h$ has a new lift, there must be
clumps $h_{a},h_{b}$ so that $h_{a}\cup h_{b}$ has connected branching. On the
other hand, if $h_{i},h_{j}$ are such that $h_{i}\cup h_{j}$ have disconnected
branching, then we may switch their order without affecting the lift.

Using this, we may choose a new order $h_{1}^{\prime},\ldots,h_{k}^{\prime}$
so that if $h_{i}^{\prime}\cup h_{j}^{\prime}$ has connected branching, then
there is no $h_{\ell}$ with $i<\ell<j$ such that $h_{i}\cup h_{\ell}\cup
h_{j}$ has disconnected branching. That is, we can push together all the
clumps under $h$ which lift to the same homonymous clump upstairs. Add a
weight zero homonymous arc enclosing each maximal collection of
$h_{i}^{\prime}$s whose union has connected branching. Call these arcs
$\alpha_{1},\ldots,\alpha_{n}$. Now, $h$ has no new lifts: it always lifts
parallel to the lifts of $\alpha_{1},\ldots,\alpha_{n}$. Call this diagram
$B^{\prime\prime}$. Pass to $P_{h}(B^{\prime\prime})$. The lifting picture
$(\Sigma,C,\prec,\mathcal{B},P_{h}(B^{\prime\prime}))$ still realizes $D$.
Since each of the arcs $\alpha_{i}$ introduced this way have connected
branching, $B^{\prime\prime}$ has fewer arcs with disonnected branching than
$B^{\prime}$. If $B^{\prime\prime}$ still has an arc with disconnected
branching, choose the arc $h$ such that $h$ has the smallest $\epsilon(h)$
among arcs with disconnected branching, and eliminate it in the same way.
Repeat this process until the resulting lifting picture
$(\Sigma,C,\prec,\mathcal{B},B^{\dagger})$ has the property that all
homonymous arcs of $B^{\dagger}$ have connected branching. Since
$B^{\prime\prime}$ has only finitely many arcs, and each step of this process
reduces the number of arcs with disconnected branching, this process
terminates after finitely many steps. By Proposition 3, $B^{\dagger}$ still
realizes $D$.

Finally, add weight zero heteronymous arcs separating each homonymous clump of
$B^{\dagger}$. Call the resulting diagram $B^{max}$. It follows from Lemma 3
and Lemma 5 that these heteronymous arcs have no nontrivial lifts which are
not also lifts of heteronymous arcs already in $B^{\dagger}$, so indeed
$B^{max}$ still realizes $D$. ∎

Lifting pictures where all homonymous arcs have connected branching are
useful, because in such lifting pictures, each homonymous clump lifts
nontrivially to a unique homonymous clump.

######  Lemma 4.

Let $D$ be a maximal arc diagram on a substrate $\Sigma$. Suppose
$(\Sigma,C,\prec,\mathcal{B},B)$ realizes $D$, and all homonymous arcs in $B$
have connected branching. Then each homonymous clump in $B$ lifts nontrivially
to a unique homonymous clump in $D$.

###### Proof.

Let $H$ be a homonymous clump in $B$, and $h\in H$. Since $h$ has connected
branching, all its nontrivial lifts are on sheets bounded by one or more
branching arc in a single homonymous clump $\widetilde{H}$ in $D$. If $S$ is a
sheet completely bounded by arcs in $\widetilde{H}$ then clearly any
nontrivial lifts of $h$ on that sheet are arcs of $\widetilde{H}$. On the
other hand, if $S$ is bounded by some arcs of $\widetilde{H}$ and some arcs
from another homonymous clump, then the lift of at least one heteronymous arc
in $B$ separates the lift of $h$ from the lifts of any arcs in any other
homonymous clump in $B$. So $H$ lifts nontrivially only to $\widetilde{H}$. ∎

######  Lemma 5.

Let $D$ be a realizable, maximal arc diagram, and $S$ a heteronymous ladder in
$D$.

  1. 1.

$S$ is simply connected.

  2. 2.

Each homonymous arc bounding $S$ is contained in a different homonymous clump.

###### Proof.

Every branching arc lies in some homonymous clump. So $S$ is contained in a
single sheet of the cover, and is therefore simply connected. To prove
statement 2, observe that $S$ is contained in a sheet $S^{\prime}$. If
multiple arcs of the same homonymous clump $K$ are in $\partial S$, then at
least 2 branching arcs $a,b$ in $K$ are in $\partial S^{\prime}$. Since the
diagram is maximal and $S^{\prime}$ is simply connected, there is a
heteronymous arc in $S$ which separates $a$ from $b$ in $S^{\prime}$. But this
cannot be the lift of any arc on the bigon, as by Lemma 4 no heteronymous arc
on the bigon can separate two critical points from the same homonymous clump.
∎

This allows us to represent a heteronymous ladder $S$ as a list of the form
needed to input into Algorithm 5. The homonymous arcs of $S$ can be
canonically ordered just as in the maximally heteronymous case. Represent $S$
as a list $s_{0},w_{1},s_{1},\ldots,w_{n},s_{n}$ where $s_{i}$ is the
homonymous clump which contains the $i^{th}$ homonymous arc bounding $S$, and
$w_{i}$ is the weight of the heteronymous arc separating $s_{i-1}$ and $s_{i}$
in $S$.

######  Algorithm 7.

_Maximal Diagram Realization._
INPUT: A maximal, weighted arc diagram $D$ on a substrate $\Sigma$.
OUTPUT: A lifting picture $(\Sigma,C,\prec,\mathcal{B},B)$ realizing $D$.
PROCEDURE: For each homonymous clump $K$, perform homonymous recursion (that
is, Algorithm 2) on $K$, to get a lifting picture
$L_{K}=(\Sigma,C_{K},\prec,\mathcal{B}_{K},B_{K})$.

For each heteronymous ladder $S$, represent $S$ as a list $L(S)$. Choose a
heteronymous ladder $T_{0}$, and let $Z_{0}=L(T_{0})$. If this is the only
heteronymous ladder, we’re done. Otherwise, choose another heteronymous ladder
$U$. Let $T_{1}=T_{0}\cup U$. Compute $Z_{1}=GeneralMerge(Z_{0},L(U))$.
Continue in this fashion until all heteronymous ladders are merged. Let
$Z=z_{0},w_{1}^{Z},z_{1},\ldots,w_{n},z_{n}$ be the resulting list.

Now construct the lifting picture. Let $\mathcal{K}$ be the set of homonymous
clumps in $D$. The set $C$ of branching arcs is $\cup_{K\in\mathcal{K}}C_{K}$.
The order $\prec$ is given by the order on each $C_{K}$ and the ordering on
$\mathcal{K}$ provided by $Z$. The bigon diagram $B$ consists of the
homonymous subdiagrams $B_{z_{1}},\ldots,B_{z_{n}}$ computed in the first part
of the procedure. $B_{z_{i}}$ and $B_{z_{i+1}}$ are separated by a
heteronymous arc with weight $w_{i}^{Z}$. Return
$(\Sigma,C,\prec,\mathcal{B},B)$. $\Diamond$

######  Theorem 3.

Let $D$ be a maximal weighted arc diagram on a substrate $\Sigma$. Then $D$ is
realizable if and only if algorithm 7 finishes without raising an exception,
and if it returns $L=(\Sigma,C,\prec,\mathcal{B},B)$, then $L$ realizes $D$.

###### Proof.

Suppose Algorithm 7 returns $L=(\Sigma,C,\prec,\mathcal{B},B)$. Then by Lemma
4, each maximal homonymous subdiagram $B^{\prime}$ of $B$ lifts to a unique
homonymous clump $D^{\prime}$ in $D$. Since the algorithm finished without
error, it follows from Theorem 1 that $B^{\prime}$ realizes $D^{\prime}$. It
now follows from the proof of Theorem 2 and Lemma 5 that the heteronymous arcs
of $B$ lift to exactly the heteronymous arcs of $D$, and that they get the
correct weight.

Now, suppose that $D$ is realizable. By Proposition 10, we may assume $D$ is
realized by a lifting picture with connected branching. Then by Lemma 4, each
homonymous clump of $D$ is realizable as a homonymous diagram in its own
right, so homonymous recursion will succeed on each clump. Similarly, it
follows from the proof of Theorem 2 that $GeneralMerge$ must succeed in
merging all the heteronymous ladders of $D$. So algorithm 7 finishes without
error when applied to $D$. ∎

##  7 Further Directions

The motivation for the work in this dissertation came from Heegaard Floer
homology. Heegaard Floer homology is a topological invariant of closed,
orientable 3-manifolds, introduced by Ozsvath and Szabo in [7]. It is built on
top of what is known as a Heegaard diagram. Detailed information on Heegaard
diagrams can be found, for example, in [9]. In brief, a Heegaard splitting of
a 3-manifold $M$ is a decomposition of $M$ into two handlebodies $H_{1}$ and
$H_{2}$. One may reconstruct $M$ by gluing together $\partial H_{1}$ and
$\partial H_{2}$ by a homeomorphism. It turns out that enough data to specify
this gluing up to isotopy is encoded in what is called a Heegaard diagram. Let
$\Sigma$ be a surface of genus $g$ homeomorphic to $\partial H_{1}$ and
$\partial H_{2}$. A Heegaard diagram on $\Sigma$ is a choice, up to homotopy,
of $2g$ closed curves on $\Sigma$, $g$ of which are labeled as coming from
$H_{1}$ and the rest of which are labeled as coming from $H_{2}$. Each set of
$g$ curves with the same labels must be linearly independent as 1 dimensional
homology classes.

Heegaard Floer homology uses unordered $g$-tuples of intersection points of
$H_{1}$ curves with $H_{2}$ curves as the generators of the Heegaard Floer
chain complex. Computing the boundary map requires, among other things,
counting structures known as Whitney disks. A Whitney disk, as defined in [7],
can be thought of as a pair of homotopy classes of maps on a surface with
boundary $\Sigma^{\prime}$. One map is an immersion
$\phi:\Sigma^{\prime}\to\Sigma$ which sends $\partial\Sigma^{\prime}$ to the
labeled curves on $\Sigma$. The other is a branched cover $f$ taking
$\Sigma^{\prime}$ to the unit disk with two marked points $p_{1}$ and $p_{2}$
on its boundary. For $i=1,2$, we must have that $\phi(f^{-1}(p_{i}))$ is an
intersection point of an $H_{1}$ and an $H_{2}$ curve for each point in
$f^{-1}(p_{i})$.

To compute the Heegaard Floer boundary map, one must count the number of
holomorphic representatives of these Whitney disks. Holomorphic, in this case,
means that for a choice of complex structure on $\Sigma$, the complex
structure on $\Sigma^{\prime}$ one gets by pulling back the complex structure
on $\Sigma$ under $\phi$ is the same as the complex structure on
$\Sigma^{\prime}$ one gets by pulling back the standard complex structure on
the unit disk under $f$.

We ultimately wish to simplify this computation by using a more combinatorial
version of a Whitney disk, which is based on a so-called degenerate complex
structure. A degenerate complex structure is something like a measured
lamination, which can be pulled back under immersions and branched covers, and
which can be encoded, in the right circumstances, using an arc diagram. We
hope that the algorithm presented here will be useful in a new method for
computing Heegaard Floer homology, and that lifting pictures will be of
independent interest.

## References

  * [1] Thomas H. Cormen Charles E. Leiserson et al.  Introduction to Algorithms.  MIT Press, 3rd edition, 2009.
  * [2] Sergey Fomin, Michael Shapiro, and Dylan Thurston.  Cluster algebras and triangulated surfaces. part i: Cluster complexes.  Acta Mathematica, 201(1):83–146, 2008.
  * [3] Allen Hatcher.  On triangulations of surfaces.  Topology and its Applications, 40(2):189–194, 1991.
  * [4] M. James.  The generalised inverse.  The Mathematical Gazette, 62(420):109–114, 1978.
  * [5] Mustafa Korkmaz and Athanase Papadopoulos.  On the arc and curve complex of a surface.  Mathematical Proceedings of the Cambridge Philosophical Society, 148(3):473–483, 2010.
  * [6] Bojan Mohar.  Branched coverings.  Discrete & Computational Geometry, 3(4):339–348, 1988.
  * [7] Peter Ozsváth and Zoltán Szabó.  Holomorphic disks and topological invariants for closed three-manifolds.  Annals of Mathematics, 159(3):1027–1158, 2004.
  * [8] Artur Piękosz.  Basic definitions and properties of topological branched coverings.  Topological Methods in Nonlinear Analysis, 8(2):359–370, 1996.
  * [9] Dale Rolfsen.  Knots and links.  AMS Chelsea Publishing. American Mathematical Society, ams edition, 2003\.