# From Modular Decomposition Trees to Rooted Median Graphs

Carmen Bruckmann  Helmholtz-Centre for Environmental Research, Permoserstraße
15, D-04318 Leipzig, Germany  Peter F. Stadler  Marc Hellmuth  Department of
Mathematics, Faculty of Science, Stockholm University, SE-10691 Stockholm,
Sweden
<EMAIL_ADDRESS>corresponding author

( )

###### Abstract

The modular decomposition of a symmetric map $\delta\colon X\times
X\to\Upsilon$ (or, equivalently, a set of symmetric binary relations, a
2-structure, or an edge-colored undirected graph) is a natural construction to
capture key features of $\delta$ in labeled trees. A map $\delta$ is explained
by a vertex-labeled rooted tree $(T,t)$ if the label $\delta(x,y)$ coincides
with the label of the last common ancestor of $x$ and $y$ in $T$, i.e., if
$\delta(x,y)=t(\operatorname{lca}(x,y))$. Only maps whose modular
decomposition does not contain prime nodes, i.e., the symbolic ultrametrics,
can be exaplained in this manner. Here we consider rooted median graphs as a
generalization to (modular decomposition) trees to explain symmetric maps. We
first show that every symmetric map can be explained by “extended” hypercubes
and half-grids. We then derive a a linear-time algorithm that stepwisely
resolves prime vertices in the modular decomposition tree to obtain a rooted
and labeled median graph that explains a given symmetric map $\delta$. We
argue that the resulting “tree-like” median graphs may be of use in
phylogenetics as a model of evolutionary relationships.

Keywords:  2-structures; symbolic ultrametrics; modular decomposition; prime
module; prime vertex replacement; median graph; algorithm; half-grid;
hypercube

##  1 Introduction

The decomposition of an object comprising a finite point set $X$ into its
modules has been a topic of intense research for decades, starting with Tibor
Gallai’s seminal work [22]. A module is a subset $M\subseteq X$ such that the
points within $M$ cannot be distinguished from each other in terms of their
relationships with points in $X\setminus M$. Modular decompositions have been
studied for graphs [11, 10, 19, 47, 26, 31], labeling maps or equivalently
sets of binary relations and 2-structures [4, 37, 35, 34, 17, 18, 14, 21, 16,
15, 20, 19] or sets of $n$-ary relations and, equivalently, hypergraphs [6, 5,
7, 25]. They share fundamental properties irrespective of the type of the
objects that determines the nature of the pertinent relationships. In
particular, the strong modules, i.e., the modules that do not with overlap
with other modules, form a hierarchy and thus can be identified with the
vertices of a rooted tree $T$. This _modular decomposition tree_ , whose
leaves correspond to the point set $X$, captures a wealth of information on
the object under consideration.

Models of evolutionary relationships often start from a rooted tree $T$
endowed with labels of vertices or edges that designate evolutionary events. A
broad class of inverse problems thus arises in mathematical phylogenetics that
can be phrased as follows: Given a (rooted) tree $T$ with labels on vertices
and edges and a rule to derive a map $\delta$ on pairs (or $k$-tuples) of
leaves, one asks (i) which maps $\delta$ can be _explained_ by such a labeled
tree, (ii) how an explaining labeled tree $T$ can be constructed, and (iii) to
characterize the set of labeled trees $T$ that explain a given map $\delta$.
Not surprisingly, there is a close connection to the modular decomposition.

An “event labeling” $t$ at the inner vertices of $T$, naturally defines
$\delta(x,y):=t(\operatorname{lca}_{T}(x,y))$ as the label of the last common
ancestor of two leaves $x$ and $y$. An event-labeled tree $(T,t)$ explaining
$\delta$ in this manner exists if and only if $\delta$ is a symbolic
ultrametric [4], which shares the structure of a cograph [10]. The
corresponding co-tree or symbolic discriminating representation, i.e., the
modular decomposition tree of $\delta$, is obtained by contracting edges in
$(T,t)$ whose endpoints share the same label [32]. In phylogenetic
applications, symbolic ultrametrics describe the key concepts of orthology and
paralogy, i.e., the question whether a pair of related genes descends from a
speciation or a gene duplication event [32, 38, 36]. Edge weights may model
distances or specific types of evolutionary events. In a _pairwise
compatibility graph_ (PCG) an edge is drawn whenever the sum of edge weights
between two leaves lies within a specified interval [44, 9]. In phylogenetics,
they model e.g. rare events [33]. Horizontal gene transfer is captured by
Fitch graphs [23, 30, 28, 29], a subclass of directed cographs corresponding
to pairs $(x,y)$ such that an edge with non-zero weight appears along the path
in $T$ connecting $\operatorname{lca}(x,y)$ with the leaf $y$. Interpreting
edge-weights as distances, and thus $\delta(x,y)$ as distance between leaves,
leads to the key theorem of mathematical phylogenetics: There is a unique
edge-weighted tree $T$ if and only if $\delta$ satisfies the so-called 4-point
condition [50, 8].

Phylogenetics also motivates the investigation of generalizations. While trees
are an excellent model of many evolutionary systems, they are approximations
and sometimes networks are a better model of reality [42]. In the case of
distance-based phylogenetics, this naturally connects with theory of split-
decomposable metrics [1] and their natural representations, the Buneman graphs
[13, 39]. The latter form a subclass of Median graphs. Median networks,
furthermore, play an important role as representations of phylogenies within
populations [2, 3]. This suggests to consider median graphs, or subclasses of
median graphs such as the Buneman graphs, as a natural generalization of trees
in the context of phylogenetic questions.

In this contribution, we consider rooted median graphs, i.e., median graphs
with a vertex designated as the root. We note in passing that rooted median
graphs recently have attracted in the context of the Daisy graph construction
[12, 51]. It is natural then to replace the last common ancestor
$\operatorname{lca}(x,y)$ by the median $\operatorname{med}(x,y,\rho)$ of two
vertices $x$ and $y$ and the root $\rho$ and to ask which maps can be
explained as $\delta(x,y)=t(\operatorname{med}(x,y,\rho))$, where $t$ is now a
vertex labeling on the median graph. In Sect. 3 we show that every symmetric
map can be explained by a sufficiently large median graph and provide explicit
constructions for extended hypercubes and extended half-grids. Thm. 3.10 shows
that $O(|X|^{2})$ vertices are sufficient. In the second part of this
contribution, Sect. 4, we show that for every symmetric map $\delta$ a rooted
labeled median graph can be obtained by expanding the map’s modular
decomposition tree by replacing its vertices with explicitly constructed
graphs (Thm. 4.11). This yields a practical algorithm to construct a rooted
median graph that explains $\delta$ with a running time linear in the size of
the input. It reduces to a labeling of the modular decomposition tree exactly
for symbolic ultrametrics (Thm. 4.3).

##  2 Preliminaries

#### Sets and Maps

Let $X$ be a finite set. We write $X^{2}_{\mathrm{irr}}\coloneqq X\times
X\setminus\\{(x,x)\mid x\in X\\}$ for the Cartesian set product without
reflexive elements, $\binom{X}{k}$ for the set of all $k$-element subsets of
$X$, and $2^{X}$ for the powerset of $X$. Denoting by $|X|$ the cardinality of
$X$ we have $|X^{2}_{\mathrm{irr}}|=|X|(|X|-1)$.

A _hierarchy on $X$_ is a subset $\mathcal{H}\subseteq 2^{X}$ such that (i)
$X\in\mathcal{H}$, (ii) $\\{x\\}\in\mathcal{H}$ for all $x\in X$, and (iii)
$p\cap q\in\\{p,q,\emptyset\\}$ for all $p,q\in\mathcal{H}$. Condition (iii)
states that no two members of $\mathcal{H}$ overlap.

Let $X$ and $\Upsilon$ be non-empty sets. We consider _maps_ $\delta\colon
X^{2}_{\mathrm{irr}}\to\Upsilon$ that assign to each pair $(x,y)\in
X^{2}_{\mathrm{irr}}$ the unique label $\delta(x,y)\in\Upsilon$. A map
$\delta$ is _symmetric_ if $\delta(x,y)=\delta(y,x)$ for all distinct $x,y\in
X$. For a subset $L\subseteq X$ we denote with $\delta_{|L}\colon
L^{2}_{\mathrm{irr}}\to\Upsilon$ the map obtained from $\delta$ by putting
$\delta_{|L}(x,y)=\delta(x,y)$ for all distinct $x,y\in L$.

#### Graphs

All graphs $G=(V,E)$ considered here are undirected and simple. For a subset
$W\subseteq V$, we write $G-W$ for the graph obtained from $G$ by deleting all
vertices in $W$ and their incident edges.

All paths in $G$ are considered to be simple, that is, no vertex is traversed
twice. In particular, the graph $P_{n}$ denotes the path on $n$ vertices with
vertex set $V(P_{n})=\\{1,\dots,n\\}$ and edge set
$E(P_{n})=\\{\\{i,i+1\\}\mid 1\leq i<n\\}$. We also write $P_{G}(a,b)$ for a
path connecting two vertices $a$ and $b$ in $G$. A cycle is a graph for which
the removal of any edge results in a path. A cycle of length four is called a
_square_.

The distance $d_{G}(u,v)$ between vertices $u$ and $v$ in a graph $G$ is the
length $|E(P)|$ of a shortest path $P$ connecting $u$ and $v$. The _interval_
between $x$ and $y$ is the set $I_{G}(x,y)$ of vertices that lie on shortest
paths $P_{G}(x,y)$ between $x$ and $y$.

Let $G=(V,E)$ be a graph and $W\subseteq V$. A (partial vertex) labeling is a
map $t\colon W\to\Upsilon$ that assigns to every vertex $v\in W$ one label
$t(v)\in\Upsilon$. We write $(G,t)$ for a given graph $G$ together with
labeling $t$ and call $(G,t)$ _labeled_ graph.

#### Rooted Graphs and Trees

We consider here _rooted_ graphs, that is, graphs for which there is a
particular distinguished vertex $\rho_{G}\in V$, called the _root of $G$_.
Given a rooted graph $G$, we can equip the vertex set $V$ with a partial order
$\preceq_{G}$ by putting $u\preceq_{G}v$ whenever $v$ lies on some path
$P_{G}(\rho_{G},u)$ connecting $\rho_{G}$ and $u$. If $u\preceq_{G}v$ and
$u\neq v$, then we write $u\prec_{G}v$. Furthermore, if we have an edge
$\\{u,v\\}\in E(G)$ such that $u\prec_{T}v$, then $u$ is a _child_ of $v$ and
$\operatorname{child}_{G}(v)$ denotes the set of all children of $v$ in $G$.
If $u\preceq_{G}v$ or $v\preceq_{G}u$, the vertices $u$ and $v$ are
_comparable_ (in $G$) and _incomparable_ , otherwise.

A vertex $v\neq\rho_{G}$ in a graph $G$ is called _leaf_ if its degree
$\deg_{G}(v)=1$. The _inner_ vertices in a graph $G$ are vertices that are not
leaves and $V^{0}(G)$ denotes the set of all inner vertices of $G$. Let
$G=(V,E)$ be a graph and assume that we have added the vertex $x\notin V$ to
$G$ such that $x$ is adjacent to exactly one vertex $v\in V$. Then, we say
that $x$ is _leaf-appended to $v$ (in $G$)_.

A _tree_ is a connected acyclic graph. Given a rooted tree $T$, the last
common ancestor $\operatorname{lca}_{T}(x,y)$ of two vertices $x,y\in V(T)$ is
the unique $\preceq_{T}$-minimal vertex that satisfies
$x,y\preceq_{T}\operatorname{lca}_{T}(x,y)$, that is, there is no further
vertex $v$ with $x,y\preceq_{T}v\prec_{T}\operatorname{lca}_{T}(x,y)$. For
rooted trees $T$ with leaf set $L$ we denote with $L(v)$ the subset of leaves
$x\in L$ with $x\preceq_{T}v$. We also write $L_{T}(v)$ instead of $L(v)$, if
there is a risk of confusion. Two labeled trees $(T,t)$ and
$(T^{\prime},t^{\prime})$ with labeling $t\colon V^{0}(T)\to\Upsilon$ and
$t^{\prime}\colon V^{0}(T^{\prime})\to\Upsilon$ are _isomorphic_ if $T$ and
$T^{\prime}$ are isomorphic via a map $\psi:V(T)\to V(T^{\prime})$ such that
$t^{\prime}(\psi(v))=t(v)$ holds for all $v\in V^{0}(T)$. There is a well-
known bijection between hierarchies and rooted trees [49]:

######  Proposition 2.1.

Let $\mathcal{H}$ be a set of non-empty subsets of $L$. Then, there is a
rooted tree $T=(W,E)$ with leaf set $L$ and with $\mathcal{H}=\\{L(v)\mid v\in
W\\}$ if and only if $\mathcal{H}$ is a hierarchy on $L$. Moreover, if there
is such a rooted tree, then, up to isomorphism, $T$ is unique.

######  Remark 2.2.

Instead of graphs with leaves we could consider a straightforward
generalization of the notion of $\mathscr{X}$-trees frequently employed in
mathematical phylogenetics. There a set of taxa $\mathscr{X}$ is mapped (not
necessarily injectively) to the vertex set $V(T)$ of a rooted or unrooted tree
$T$, see e.g. [49]. We prefer to instead identify the taxa with the leaf set
$L$ and insist that distinct taxa are represented by distinct vertices in the
graphs that describe the phylogenetic relationships. In an $\mathscr{X}$-tree
like setting we could identify the taxa with the corresponding leaf’s
(uniquely defined) “parent”.

#### Cartesian Graph Product

The _Cartesian product_ $G\Box H$ of two graphs $G=(V,E)$ and $H=(W,F)$ has
vertex set $V(G\Box H)\coloneqq V\times W$ and edge set $E(G\Box
H)\coloneqq\\{\\{(g,h),(g^{\prime},h^{\prime})\\}\mid g=g^{\prime}\text{ and
}\\{h,h^{\prime}\\}\in F\text{, or }h=h^{\prime}\text{ and
}\\{g,g^{\prime}\\}\in E\\}$. The Cartesian product is known to be commutative
and associative and thus, $\Box_{i=1}^{n}G_{i}=G_{1}\Box\cdots\Box G_{n}$ is
well-defined [27, 43]. For a vertex $v=(g_{1},\dots,g_{h})\in
V(\Box_{i=1}^{n}G_{i})$ we refer to $(g_{1},\dots,g_{n})$ as the _coordinate
vector_ of $v$ and to $g_{i}$ as the _$i$ -th coordinate_ of $v$. The _Hamming
distance_ between two vertices $v$ and $w$ with coordinate vectors
$(g_{1},\dots,g_{n})$ and $(g^{\prime}_{1},\dots,g^{\prime}_{n})$,
respectively, is the number of coordinates $i$ for which $g_{i}\neq
g^{\prime}_{i}$.

A _complete grid_ is the Cartesian product $P_{n}\Box P_{m}$ of two paths and
a _grid graph_ is a subgraph of a complete grid. A _hypercube $Q_{n}$_ is the
$n$-fold Cartesian product of edges, i.e., $Q_{n}=\Box_{i=1}^{n}K_{2}$.
Equivalently, hypercubes can be defined as graphs having vertex set
$V=\\{0,1\\}^{n}$ and having edges precisely between the vertices that have
Hamming distance $1$.

Based on the _distance formula_ [27, Cor. 5.2], we obtain the following simple
result for complete complete grid graphs and hypercubes that we shall need for
later reference.

######  Lemma 2.3.

Let $P_{n}$ be a path with $V(P_{n})=\\{1,\dots,n\\}$ and edge set
$E(P_{n})=\\{\\{i,j\\}\mid j=i+1,1\leq i<n\\}$ and $G=P_{n}\Box P_{n}$.Then,
for all vertices $(i,j),(i^{\prime},j^{\prime})\in V(G)$ it holds that
$d_{G}((i,j),(i^{\prime},j^{\prime}))=|i-i^{\prime}|+|j-j^{\prime}|$.

For a hypercube $Q_{n}$ the distance $d_{Q_{n}}(x,y)$ of vertices $x,y\in
V(Q_{n})$ is the Hamming distance of $x$ and $y$.

Following [45], we will consider grid graphs as plane graphs, that is, we will
assume that they are embedded in the plane in the natural way – as a subgraph
of a complete grid.

#### Median Graphs

A vertex $x$ is a _median_ of a triple of vertices $u$, $v$ and $w$ if
$d(u,x)+d(x,v)=d(u,v)$, $d(v,x)+d(x,w)=d(v,w)$ and $d(u,x)+d(x,w)=d(u,w)$. A
connected graph $G$ is a _median graph_ if every triple of its vertices has a
unique median. In other words, $G$ is a median graph if, for all distinct
$u,v,w\in V(G)$, there is a unique vertex that belongs to shortest paths
between each pair of $u,v$ and $w$. Equivalently, $G$ is a median graph if
$|I_{G}(u,v)\cap I_{G}(u,w)\cap I_{G}(v,w)|=1$ for every triple $u$, $v$ and
$w$ of its vertices [48, 46]. We denote the unique median of three vertices
$u$, $v$ and $w$ in a median graph $G$ by $\operatorname{med}_{G}(u,v,w)$. A
well-known example of median graphs are trees. In particular, if we consider
rooted trees $T$, then $\operatorname{lca}_{T}(x,y)$ lies on all three paths
between $x$ and $y$, between $\rho_{T}$ and $x$ as well as between $\rho_{T}$
and $y$. Taking the latter two arguments together, we obtain the following

######  Observation 2.4.

If $T$ is a rooted tree, then
$\operatorname{lca}_{T}(x,y)=\operatorname{med}_{T}(x,y,\rho_{T})$ for every
$x,y\in V(T)$.

A further example of median graphs are particular grid graphs for which a
planar drawing is provided. As a direct consequence of Lemma 6 together with
Theorem 7 in [45], we obtain

######  Theorem 2.5 ([45]).

A connected grid graph $G$ is a median graph if and only if all inner faces of
$G$ are squares.

If $e$ is an edge in a connected graph $G$ whose removal makes $G$
disconnected, then $G$ is a median graph if and only if both components of
$G-e$ (the graph obtained from $G$ by removing the edge $e$) are median graphs
[45]. Therefore, we obtain the following simple result that we need for later
reference.

######  Lemma 2.6.

Let $G_{1}=(V_{1},E_{1})$ and $G_{2}=(V_{2},E_{2})$ be two vertex-disjoint
graphs and let $v\in V_{1}$ and $w\in V_{2}$. Then, $G=(V_{1}\cup
V_{2},E_{1}\cup E_{2}\cup\\{\\{v,w\\}\\})$ is a median graph if and only if
$G_{1}$ and $G_{2}$ are median graphs. In particular, if $L$ is the set of
leaves in $G$, then $G$ is median graph if and only if $G-L$ is median graph.

######  Definition 2.7.

Let $G=(V,E)$ be a rooted median graph with root $\rho$ and a specified set
$L\subseteq V$ of vertices. Then,

$V_{\operatorname{med}_{G},L}\coloneqq\\{\operatorname{med}_{G}(\rho,x,y)\mid
x,y\in L\text{ and }x,y,\rho\text{ pairwise distinct}\\}$

denotes the set of all (unique) medians $\operatorname{med}_{G}(\rho,x,y)$ for
all distinct pairs of vertices $x,y\in L$.

######  Definition 2.8.

Let $\delta\colon X^{2}_{\mathrm{irr}}\to\Upsilon$ be a symmetric map. A
rooted median graph $G=(V,E)$ with root $\rho$ and specified set $L=X\subseteq
V$ _explains_ $\delta$ if there is a labeling $t\colon
V_{\operatorname{med}_{G},L}\to\Upsilon$ such that
$\delta(x,y)=t(\operatorname{med}_{G}(\rho,x,y))$ for all distinct $x,y\in X$.

In the following the set $L$ in Def. 2.7 and 2.8 will coincide the leaf set of
the median graphs under consideration.

##  3 Every map $\delta$ can be explained by a labeled median graph

We are interested in rooted median graphs that can explain a given map
$\delta$. As noted in the introduction, only a very restricted subclass of
maps, namely the symbolic ultrametrics [4], can be explained by rooted trees.
This is not surprising since $O(|X|^{2})$ values of $\delta(x,y)$ must be
explained by only $O(|X|)$ labels at the internal vertices of a tree. This
suggests that rooted median graphs with a large enough number of inner
vertices should be able to explain any given map. Here we show that this is
indeed the case.

###  3.1 Extended Hypercubes

One of the best known median graphs is possibly the hypercube. In particular,
every median graph is a distance-preserving subgraph of some hypercube [45].

######  Definition 3.1.

Let $Q_{n}=(V,E)$ be a hypercube. An _extended_ hypercube
$Q^{\mathrm{ext}}_{n}$ with leaf set $L=\\{x_{1},\dots,x_{n}\\}$ is obtained
from $Q_{n}$ as follows: every $x_{i}\in L$ is leaf-appended to the vertex for
which only the $i$-th coordinate is a $1$. The root $\rho$ of
$Q^{\mathrm{ext}}_{n}$ will always be the vertex with coordinate vector
$(1,\dots,1)$.

######  Lemma 3.2.

$Q^{\mathrm{ext}}_{n}$ is a median graph and
$\operatorname{med}_{Q^{\mathrm{ext}}_{n}}(\rho,x_{i},x_{j})\neq\operatorname{med}_{Q^{\mathrm{ext}}_{n}}(\rho,x_{k},x_{l})$
whenever $x_{i}$ and $x_{j}$, resp. $x_{k}$ and $x_{l}$ are distinct vertices
and $|\\{i,j\\}\cap\\{k,l\\}|\leq 1$.

###### Proof.

Since $Q_{n}$ as well as all single vertex graphs
$G_{j}=(\\{x_{j}\\},\emptyset)$, $1\leq j\leq n$ are median graphs, Lemma 2.6
implies that $Q^{\mathrm{ext}}_{n}$ is a median graph.

Now, let $L$ be the set of leaves in $Q^{\mathrm{ext}}_{n}$ and let
$x_{i},x_{j}\in L$ and $x_{k},x_{l}\in L$ be two distinct vertices,
respectively, such that $\\{i,j\\}\neq\\{k,l\\}$. Since $Q^{\mathrm{ext}}_{n}$
is a median graph, the medians in $Q^{\mathrm{ext}}_{n}$ are unique for all
three vertices in $Q^{\mathrm{ext}}_{n}$ and it is easy to verify that
$\operatorname{med}_{Q_{n}}(\rho,v_{i},v_{j})=\operatorname{med}_{Q^{\mathrm{ext}}_{n}}(\rho,v_{i},v_{j})$
for every distinct $v_{i},v_{j}\in V(Q_{n})$ with $v_{i},v_{j}\neq\rho$. By
construction, $x_{\ell}\in L$ is leaf-appended to the unique vertex $v_{\ell}$
with all coordinates being $0$ except the $\ell$-th coordinate which is a $1$
and every shortest path from $x_{\ell}$ to any other vertex must contain
$v_{\ell}$. The latter two arguments imply that it suffices to show that
$\operatorname{med}_{Q_{n}}(\rho,v_{i},v_{j})\neq\operatorname{med}_{Q_{n}}(\rho,v_{k},v_{l})$
in order to show that
$\operatorname{med}_{Q^{\mathrm{ext}}_{n}}(\rho,x_{i},x_{j})\neq\operatorname{med}_{Q^{\mathrm{ext}}_{n}}(\rho,x_{k},x_{l})$.

Assume for contradiction that
$w\coloneqq\operatorname{med}_{Q_{n}}(\rho,v_{i},v_{j})=\operatorname{med}_{Q_{n}}(\rho,v_{k},v_{l})$.
Based on Lemma 2.3 and the respective Hamming distances we easily obtain,

$d_{Q_{n}}(v_{i},w)+d_{Q_{n}}(w,v_{j})=d_{Q_{n}}(v_{i},v_{j})=2=d_{Q_{n}}(v_{k},v_{l})=d_{Q_{n}}(v_{k},w)+d_{Q_{n}}(w,v_{l}).$

There are two possibilities for $w$ to satisfy
$d_{Q_{n}}(v_{i},w)+d_{Q_{n}}(w,v_{j})=d_{Q_{n}}(v_{i},v_{j})=2$, that is, $w$
either the vertex with coordinate vector $(0,\dots,0)$ or the vertex for which
the coordinate vectors have precisely two $1$s, namely the $i$-th and $j$-th
coordinate. Analogously, for
$d_{Q_{n}}(v_{k},v_{l})=d_{Q_{n}}(v_{k},w)+d(w,v_{l})=2$, the median $w$ is
either the vertex $(0,\dots,0)$ or the vertex for which the coordinate vectors
have precisely two $1$s, namely the $k$-th and $l$-th coordinate. This
together with $\\{i,j\\}\neq\\{k,l\\}$ implies that $w$ must be the vertex
$(0,\dots,0)$. Since $w=\operatorname{med}_{Q_{n}}(\rho,v_{i},v_{j})$ it must
also hold that
$d_{Q_{n}}(v_{j},w)+d_{Q_{n}}(w,\rho)=d_{Q_{n}}(v_{j},\rho)=n-1$. However,
since $d_{Q_{n}}(v_{j},w)=1$ and $d_{Q_{n}}(w,\rho)=n$, we obtain
$d_{Q_{n}}(v_{j},w)+d_{Q_{n}}(w,\rho)=d_{Q_{n}}(v_{j},\rho)=n+1$; a
contradiction. ∎

######  Corollary 3.3.

Every symmetric map $\delta\colon X^{2}_{\mathrm{irr}}\to\Upsilon$ can be
explained by a labeled extended hypercube $(Q^{\mathrm{ext}}_{|X|},t)$.

###### Proof.

Let $X$ be the set of leaves in $Q^{\mathrm{ext}}_{|X|}$. Put
$t(\operatorname{med}_{Q^{\mathrm{ext}}_{|X|}}(\rho,x,y))=\delta(x,y)$ for all
distinct $x,y\in X$. By Lemma 3.2, we have
$\operatorname{med}_{Q^{\mathrm{ext}}_{|X|}}(\rho,x_{i},x_{j})\neq\operatorname{med}_{Q^{\mathrm{ext}}_{|X|}}(\rho,x_{k},x_{l})$
given that $\\{i,j\\}\neq\\{k,l\\}$ and $i\neq j$ and $k\neq l$. Hence,
$t(\operatorname{med}_{Q^{\mathrm{ext}}_{|X|}}(\rho,x,y))$ is well-defined and
$(Q^{\mathrm{ext}}_{|X|},t)$ explains $\delta$. ∎

An illustrative example for Cor. 3.3 is provided in Fig. 2. Of course,
$Q^{\mathrm{ext}}_{|X|}$ has $O(2^{|X|})$ vertices and many vertices are not
part of $V_{\operatorname{med}_{Q^{\mathrm{ext}}_{|X|}},X}$ which makes this
construction intractable in practice. Hence, we focus now on graphs that have
significantly less vertices and still explain a symmetric map $\delta$.

###  3.2 Extended Halfgrids

We next consider a class of much smaller median graphs.

######  Definition 3.4.

A _half-grid_ $H_{n}$ with $n\geq 2$ is defined as $H_{2}=P_{2}\Box P_{2}$ or,
if $n\geq 3$, then $H_{n}$ is obtained from the Cartesian product $P_{n}\Box
P_{n}$ by removing all vertices with coordinate vectors $(i,j)$ with $1\leq
j\leq n-2$ and $j+2\leq i\leq n$. and its incident edges, see also Fig. 1.

######  Observation 3.5.

By construction, $H_{n}$ is a subgraph of $P_{n}\Box P_{n}$ that is induced by
the vertices with coordinate vectors $(i,j)$ such that either $i=1$ and $1\leq
j\leq n$ or $2\leq i\leq n$ and $i-1\leq j\leq n$.

Analogously, $H_{n}$ is a subgraph of $P_{n}\Box P_{n}$ that is induced by the
vertices with coordinate vectors $(i,j)$ such that either $j=n$ and $1\leq
i\leq n$ or $1\leq j\leq n-1$ and $1\leq i\leq j+1$.

Figure 1: Sketch of the extended half-grid $H^{\mathrm{ext}}_{n+1}$ on
$X=\\{x_{1},\dots,x_{n+1}\\}$ that is obtained from $P_{n}\Box P_{n}$ by
removal of all gray-colored edges and vertices. For better readability, we
have drawn only a few vertex coordinate vectors that always belong to the
vertex at the lower-right of the respective coordinate vector.  Figure 2:
Left: the graph-representation of a map $\delta\colon
X^{2}_{\mathrm{irr}}\to\Upsilon$ with $X=\\{a,b,c,d\\}$ and
$\delta(a,b)=\delta(a,c)=\delta(b,d)=\mathrm{blue}$ _(solid line)_ ,
$\delta(b,c)=\mathrm{red}$ _(dashed line)_ , $\delta(c,d)=\mathrm{purple}$
_(dashed-dotted line)_ , $\delta(a,d)=\mathrm{green}$ _(dotted line)_. For the
two graphs $(Q^{\mathrm{ext}}_{4},t)$ (middle) and $(H^{\mathrm{ext}}_{4},t)$
(right) all non-black vertices belong to
$V_{\operatorname{med}_{Q^{\mathrm{ext}}_{4}},X}$ and
$V_{\operatorname{med}_{H^{\mathrm{ext}}_{4}},X}$, respectively. Both labeled
graphs $(Q^{\mathrm{ext}}_{4},t)$ and $(H^{\mathrm{ext}}_{4},t)$ explain
$\delta$.

######  Lemma 3.6.

$H_{n}$ is a median graph.

###### Proof.

By construction $H_{n}$ is obtained from $G=P_{n}\Box P_{n}$ be removal of
some vertices and its incident edges. All removed vertices are of the form
$(i,j)$ with $1\leq j\leq n-2$ and $j+2\leq i\leq n$. We continue to show that
each inner face of $H_{n}$ is a square.

Consider a planar embedding of $P_{n}\Box P_{n}$ which can be chosen in a way
such that all inner faces are squares. Let us first remove vertex $v=(n,1)$.
This yields one square deletion and does not produce any new inner face in the
graph $G^{\prime}=G-\\{v\\}$. Now, we remove vertex $w=(n-1,1)$ from
$G^{\prime}$ and again, one square is removed and no new inner face has been
created. This step can repeated until we end in some graph where all vertices
$(n,1),\dots,(3,1)$ have been removed. In this graph, all inner faces are
still squares and thus, by Thm. 2.5, it is a median graph. Now we proceed for
all $j$ from $2$ to $n-2$ and delete stepwisely all vertices
$(n,j),\dots,(j+2,j)$. In each step exactly one square is removed and no new
inner face is created.

Hence, $H_{n}$ is a connected planar grid graph where all inner faces are
squares. By Thm. 2.5, $H_{n}$ is a median graph. ∎

######  Definition 3.7.

Let $H_{n}=(V,E)$ be a half-grid, $n\geq 2$. An _extended_ half-grid
$H^{\mathrm{ext}}_{n+1}$ with leaf set $L=\\{x_{1},\dots,x_{n+1}\\}$ is
obtained from $H_{n}$ as follows: Make $x_{1}$ leaf-appended to vertex
$(1,1)$, $x_{n+1}$ leaf-appended to vertex $(n,n)$ and $x_{j}$ leaf-appended
to vertex $(j,j-1)$, $2\leq j\leq n$ in $H_{n}$.

The root $\rho$ of $H^{\mathrm{ext}}_{n+1}$ will always be the vertex with
coordinate vector $(1,n)$.

######  Proposition 3.8.

Let $H^{\mathrm{ext}}_{n+1}$ be an extended half-grid with leaf set
$L=\\{x_{1},\dots,x_{n+1}\\}$. Then, $H^{\mathrm{ext}}_{n+1}$ is a median
graph and for all leaves $x_{i}$ and $x_{j}$, $i<j$ we have
$\operatorname{med}_{H^{\mathrm{ext}}_{n+1}}(\rho,x_{i},x_{j})=(i,j-1)$.

###### Proof.

For simplicity we put
$\operatorname{med}(\dots)=\operatorname{med}_{H^{\mathrm{ext}}_{n+1}}(\dots)$.
Since $H_{n}$ as well as all single vertex graphs
$G_{j}=(\\{x_{j}\\},\emptyset)$, $1\leq j\leq n+1$ are median graphs, we can
apply Lemma 3.6 together with Lemma 2.6 to conclude that
$H^{\mathrm{ext}}_{n+1}$ is a median graph.

We continue by showing that $\operatorname{med}(\rho,x_{i},x_{j})=(i,j-1)$. We
have leaf-appended each $x_{j}\in X$ to a unique vertex $v_{j}$ in $H_{n}$,
i.e., $v_{1}=(1,1)$ $v_{n+1}=(n,n)$ and $v_{j}=(j,j-1)$, $2\leq j\leq n$. For
simplicity, we put $H\coloneqq H^{\mathrm{ext}}_{n+1}$ and $G=P_{n}\Box
P_{n}$.

In the following, we will make frequent use of the following observation:
Since $H_{n}\subseteq G$, we have $d_{H}(x,y)=d_{H_{n}}(x,y)\geq d_{G}(x,y)$
for all $x,y\in V(H_{n})\subseteq V(H)$. Hence, if there is a path
$P_{H}(x,y)$ of length $d_{G}(x,y)$, then $P_{H}(x,y)$ must be a shortest path
in $H$ between $x$ and $y$. For simplicity we denote with ${P}_{ij}$ the path
$P_{H}(v_{i},v_{j})$ in $H$ connecting $v_{i}$ and $v_{j}$, $i<j$.

######  Claim 3.8.1.

There is a shortest path $P_{i,j}$ in $H$ connecting $v_{i}$ and $v_{j}$,
$i<j$ that contains the vertex $w_{i,j}=(i,j-1)$.

_Proof of Claim._ Let us start with the special case $v_{1}=(1,1)$ and
$v_{n+1}=(n,n)$. By construction of $H_{n}$, all vertices $(1,k)$ with $1\leq
k\leq n$ and all vertices $(k,n)$ with $1\leq k\leq n$ are contained in
$H_{n}$. Thus, there is a path $P_{1,n+1}$ induced by the vertices
$(1,1),\dots,(1,n),\dots,(n,n)$ that has length $2(n-1)=2n-2$. By Lemma 2.3,
$d_{G}(v_{1},v_{n+1})=(n-1)+(n-1)=2n-2$, which implies that $P_{1,n+1}$ is a
shortest path in $H$ that, in particular, includes $w_{1,n+1}=(1,n)$.

Now, consider $v_{1}=(1,1)$ and $v_{j}=(j,j-1)$, $2\leq j\leq n$. Note, by
construction of $H_{n}$, all vertices $(1,k)$ with $1\leq k\leq j-1<n$ and all
vertices $(k,j-1)$ with $1\leq k\leq j$ are contained in $H_{n}$. Thus, there
is a path $P_{1,j}$ induced by vertices $(1,1),\dots,(1,j-1),\dots,(j,j-1)$ of
length $(j-2)+(j-1)$, $2\leq j\leq n$. By Lemma 2.3,
$d_{G}(v_{1},v_{j})=(j-1)+(j-2)$, which implies that $P_{1,j}$ is a shortest
path in $H$ that, in particular, includes $w_{1,j}=(1,j-1)$.

By similar arguments, there is a path $P_{i,n+1}$ from $v_{i}=(i,i-1)$ and
$v_{n+1}=(n,n)$, $2\leq i\leq n$ along the vertices
$(i,i-1),\dots,(i,n),\dots,(n,n)$ of length $(n-i+1)+(n-i)$. By Lemma 2.3,
$d_{G}(v_{i},v_{n+1})=(n-i)+(n-i+1)$, which implies that $P_{i,n+1}$ is a
shortest path in $H$ that, in particular, includes $w_{i,n+1}=(i,n)$.

Now consider $v_{i}=(i,i-1)$ and $v_{j}=(j,j-1)$, $2\leq i<j\leq n$. By Remark
3.5, all vertices $(i,k)$ with $i-1\leq k\leq n$ and all vertices $(k,j-1)$
with $i-1\leq k\leq(j-1)+1=j$ (since $j-1\neq n$) are contained in $H_{n}$.
Thus, there is a path $P_{i,j}$ induced by vertices
$(i,i-1),(i,i),\dots,(i,j-1),(i+1,j-1),\dots,(j,j-1)$ of length
$(j-1-(i-1))+(j-i)=2j-2i$. By Lemma 2.3,
$d_{G}(v_{i},v_{j})=(j-i)+(j-1-(i-1))=2j-2i$, which implies that $P_{i,j}$ is
a shortest path in $H$ that, in particular, includes $w_{i,j}=(i,j-1)$.
$\diamond$

######  Claim 3.8.2.

There are shortest paths ${P}_{H}(\rho,v_{i})$ and ${P}_{H}(\rho,v_{j})$ that
both contain vertex $w_{i,j}=(i,j-1)$ for all $1\leq i<j\leq n+1$.

_Proof of Claim._ For simplicity, we put
${P}_{\rho,i}\coloneqq{P}_{H}(\rho,v_{i})$ and
${P}_{\rho,j}\coloneqq{P}_{H}(\rho,v_{j})$.

Let us start again with $v_{1}=(1,1)$. In this case, there is a path
${P}_{\rho,1}$ from $\rho$ to $v_{1}$ along the vertices
$\rho=(1,n),\dots,(1,1)=v_{1}$ of length $n-1$ which is, by Lemma 2.3, the
same as $d_{G}(\rho,v_{1})$. Hence, ${P}_{\rho,1}$ is a shortest path in $G$.
In particular, $w_{1,j}=(1,j-1)$ is contained in ${P}_{\rho,1}$ for all
$1<j\leq n+1$.

By similar arguments and using the path ${P}_{\rho,n+1}$ along the vertices
$\rho=(1,n),\dots,(n,n)=v_{n+1}$, the path ${P}_{\rho,n+1}$ contains all
vertices $w_{i,n+1}=(i,n)$ with $1\leq i<j\leq n+1$.

Now assume that $v_{i}$ and $v_{j}$ are chosen such that $1<i<j<n+1$. By
similar arguments as in the proof of Claim 3.8.1, there is a path
${P}_{\rho,i}$ along the vertices
$\rho=(1,n),\dots,(i,n),\dots,(i,j-1),\dots,(i,i-1)=v_{i}$. This path
${P}_{\rho,i}$ has length $(i-1)+(n-(i-1))=n$, Moreover, there is a path
${P}_{\rho,j}$ along the vertices
$\rho=(1,n),\dots,(1,j-1),\dots,(i,j-1),\dots,(j,j-1)=v_{j}$. This
${P}_{\rho,j}$ has length $(n-(j-1))+(j-1)=n$, which is, by Lemma 2.3, the
same as $d_{G}(\rho,v_{j})$. For both cases, Lemma 2.3 implies that
${P}_{\rho,i}$ and ${P}_{\rho,j}$ are shortest paths. In particular, both
paths contain $w_{i,j}=(i,j-1)$. $\diamond$

We are now in the position to prove the final statement
$\operatorname{med}(\rho,x_{i},x_{j})=(i,j-1)$ where $x_{i},x_{j}\in X$,
$i<j$. Since each $x_{i}$ is leaf-appended to $v_{i}$ every shortest path from
$x_{i}$ to every other vertex must contain $v_{i}$. In other words, every
shortest path from $x_{i}$ to some vertex $z$ consists of the edge
$\\{x_{i},v_{i}\\}$ and a shortest path from $v_{i}$ to $z$. Thus, Claims
3.8.1 and 3.8.2 imply that $w_{ij}=(i,j-1)$ is contained in a shortest path
from $x_{i}$ to $x_{j}$ as well as in a shortest path from $\rho=(1,n)$ to
$x_{i}$ and $x_{j}$, respectively. Finally, since $H$ is a median graph it
must hold that $\operatorname{med}(\rho,x_{i},x_{j})=(i,j-1)$, $1\leq i<j\leq
n+1$. ∎

######  Corollary 3.9.

Let $H^{\mathrm{ext}}_{n+1}$ be an extended half-grid with leaf set
$L=\\{x_{1},\dots,x_{n+1}\\}$. Then, for each $w\in
V_{\operatorname{med}_{H^{\mathrm{ext}}_{n+1}},L}$ there is a unique pair
$(x_{i},x_{j})$, $i<j$ such that
$w=\operatorname{med}_{H^{\mathrm{ext}}_{n+1}}(\rho,x_{i},x_{j})$.

######  Theorem 3.10.

For every symmetric map $\delta\colon X^{2}_{\mathrm{irr}}\to\Upsilon$, there
is a labeled median graph $(G,t)$ with $O(|X^{2}|)$ vertices and leaf-set $X$
that explains $\delta$ and such that its root $\rho_{G}$ is in
$V_{\operatorname{med}_{G},X}$.

###### Proof.

If $|X|=2$, then one can easily verify that this can explained by a rooted
tree with one inner vertex and two leaves. Consider $H^{\mathrm{ext}}_{|X|}$
with leaf set $X=\\{x_{1},\dots,x_{n+1}\\}$, $|X|\geq 3$ and root $\rho$. By
construction, $H^{\mathrm{ext}}_{|X|}$ has $O(|X^{2}|)$ vertices. Put
$t(\operatorname{med}_{H^{\mathrm{ext}}_{|X|}}(\rho,x,y))=\delta(x,y)$ for all
distinct $x,y\in X$. By Cor. 3.9,
$\operatorname{med}_{H^{\mathrm{ext}}_{|X|}}(\rho,x,y))$ is uniquely
determined for all distinct $x,y\in X$. Hence,
$t(\operatorname{med}_{H^{\mathrm{ext}}_{|X|}}(\rho,x,y))$ is well-defined and
$(G=H^{\mathrm{ext}}_{|X|},t)$ explains $\delta$. Moreover, by Prop. 3.8,
$\operatorname{med}_{H^{\mathrm{ext}}_{|X|}}(\rho,x_{1},x_{n+1})=(1,n)=\rho$.
Therefore, $\rho\in V_{\operatorname{med}_{G},X}$. ∎

An example for the construction as in the proof of Thm. 3.10 is provided in
Fig. 2.

While $Q^{\mathrm{ext}}_{|X|}$ has $2^{|X|}+|X|$ vertices, the graph
$H^{\mathrm{ext}}_{|X|}$ has only $\Theta(|X|^{2})$ vertices, and thus, is
more space-efficient. There are maps for which we cannot avoid that the graph
that explains it has $\Theta(|X|^{2})$ vertices. In particular, if
$\delta\colon X^{2}_{\mathrm{irr}}\to\Upsilon$ is a surjective map with
$|\Upsilon|=|\binom{X}{2}|$, then
$\delta(x,y)\neq\delta(x^{\prime},y^{\prime})$ for all pairs
$(x,y),(x^{\prime},y^{\prime})\in X^{2}_{\mathrm{irr}}$ with
$\\{x,y\\}\neq\\{x^{\prime},y^{\prime}\\}$. In this case, all the labels of
the respective medians must be distinct and thus, $\Theta(|X|^{2})$ medians
must exist. In other words, halfgrids are in some sense optimal if all
$\delta(x,y)$ are distinct. In general, however, we want to explain maps
$\delta$ by median graphs that are closer to trees. This leads us directly to
the concept of the modular decomposition of a map which is explained in the
next section.

##  4 Median graphs from Modular Decomposition Trees

This section makes extensive use of results established in [34] for so-called
2-structures (cf. [17, 18, 15, 20, 21, 47, 19, 20, 16, 14] and (not
necessarily symmetric) maps $\delta$. A (labeled) _2-structure_ is a triple
$g=(X,\Upsilon,\delta)$ where $X$ and $\Upsilon$ are nonempty sets and
$\delta\colon X^{2}_{\mathrm{irr}}\to\Upsilon$ is a map. Since 2-structures
are essentially determined by $\delta\colon X^{2}_{\mathrm{irr}}\to\Upsilon$
we use such maps, instead of 2-structures, which is more suitable for our
purposes. The idea underlying this section is to start from the modular
decomposition tree of a symmetric map $\delta$ and to “expand” this tree in a
principled manner into a rooted median graph that explains $\delta$. We thus
start with the notion of modules for symmetric maps.

######  Definition 4.1.

A _module_ of a symmetric map $\delta\colon X^{2}_{\mathrm{irr}}\to\Upsilon$
is a subset $M\subseteq X$ such that $\delta(x,z)=\delta(y,z)$ holds for all
$x,y\in M$ and $z\in X\setminus M$. A module $M$ of $\delta$ is _strong_ if
$M$ does not overlap with any other module of $\delta$, that is, $M\cap
M^{\prime}\in\\{M,M^{\prime},\emptyset\\}$ for all modules $M^{\prime}$ of
$\delta$.

We write $\mathbb{M}(\delta)$ for the set of all modules of a symmetric map
$\delta$ and $\mathbb{M}_{\mathrm{str}}(\delta)\subseteq\mathbb{M}(\delta)$
for the set of all strong modules of $\delta$. The empty set $\emptyset$, the
complete vertex set $X$, and the singletons $\\{v\\}$ are always modules. They
are called the _trivial_ modules of $\delta$. We will assume from here on,
that a module is non-empty unless otherwise indicated.

The set $\mathbb{M}_{\mathrm{str}}(\delta)$ of strong modules is uniquely
determined [34, 19]. While there may be exponentially many modules, the size
of the set of strong modules is in $O(|X|)$ [19]. In particular, $X$ and the
singletons $\\{v\\}$, $v\in X$ are strong modules. Since strong modules do not
overlap this implies that $\mathbb{M}_{\mathrm{str}}(\delta)$ forms a
hierarchy and, by Prop. 2.1, gives rise to a unique tree representation
$T_{\delta}$ of $\delta$, known as the _modular decomposition tree_ (_MDT_) of
$\delta$. The vertices of $T_{\delta}$ are (identified with) the elements of
$\mathbb{M}_{\mathrm{str}}(\delta)$. Adjacency in $T_{\delta}$ is defined by
the maximal proper inclusion relation, that is, there is an edge
$\\{M,M^{\prime}\\}$ between
$M,M^{\prime}\in\mathbb{M}_{\mathrm{str}}(\delta)$ iff $M\subsetneq
M^{\prime}$ and there is no
$M^{\prime\prime}\in\mathbb{M}_{\mathrm{str}}(\delta)$ such that $M\subsetneq
M^{\prime\prime}\subsetneq M^{\prime}$. The root of $T_{\delta}$ is
(identified with) $X$ and every leaf $v$ corresponds to the singleton
$\\{v\\}$, $v\in X$.

Uniqueness and the hierarchical structure of
$\mathbb{M}_{\mathrm{str}}(\delta)$ implies that there is a unique partition
$\mathbb{M}_{\max}(\delta)=\\{M_{1},\dots,M_{k}\\}$ of $X$ into maximal
(w.r.t. inclusion) strong modules $M_{j}\neq X$ of $\delta$ [17, 18]. Since
$X\notin\mathbb{M}_{\max}(\delta)$ the set $\mathbb{M}_{\max}(\delta)$
consists of $k\geq 2$ strong modules, whenever $|X|>1$.

For later reference, we recall

######  Lemma 4.2 ([17], Lemma 4.11).

Let $M_{1},M_{2}\in\mathbb{M}(\delta)$ be two disjoint modules of a symmetric
map $\delta$. Then there is a unique label $i\in\Upsilon$ such that
$\delta(x,y)=\delta(y,x)=i$ for all $x\in M_{1}$ and $y\in M_{2}$.

In order to infer $\delta$ from $T_{\delta}$ we need to determine the label
$\delta(x,y)$ of all pairs of distinct leaves $x,y$ from $T_{\delta}$. Hence,
we need to define a labeling function $t_{\delta}$ that assigns this “missing
information” to the inner vertices of $T_{\delta}$.

The simplest case for the construction of $t_{\delta}$ is given by symmetric
maps $\delta\colon X^{2}_{\mathrm{irr}}\to\Upsilon$ that satisfy the following
two axioms:

  * (U1)

there exists no subset $\\{x,y,u,v\\}\in\binom{X}{4}$ such that
$\delta(x,y)=\delta(y,u)=\delta(u,v)\neq\delta(y,v)=\delta(x,v)=\delta(x,u)$.

  * (U2)

$|\\{\delta(x,y),\delta(x,z),\delta(y,z)\\}|\leq 2$ for all $x,y,z\in X$.

A symmetric map that satisfies (U1) and (U2) is called a _symbolic
ultrametric_ [4]. In this case, there is a unique vertex labeled tree
$(T^{*},t^{*})$, called _discriminating symbolic representation_ of $\delta$,
that satisfies $t^{*}(v)\neq t^{*}(u)$ for all edges $\\{u,v\\}\in E(T^{*})$
with $u,v\in V^{0}(T^{*})$ being inner vertices and for which
$t(\operatorname{lca}_{T}(x,y))=\delta(x,y)$ for all distinct $x,y\in X$ (cf.
[4] and [32, Prop. 1]). Hence, given the discriminating symbolic
representation $(T^{*},t^{*})$ of a symbolic ultrametric $\delta$ we can
uniquely recover $\delta$ from $(T^{*},t^{*})$.

Now consider the MDT $T_{\delta}$ of $\delta$. In case $\delta$ is a symbolic
ultrametric we can also equip $T_{\delta}$ with a labeling $t_{\delta}$, by
setting $t_{\delta}(\operatorname{lca}_{T_{\delta}}(x,y))=\delta(x,y)$ for all
distinct $x,y\in X$. If $\delta$ is a symbolic ultrametric then Lemma 7 and
Theorem 6 and 7 in [34] imply that $t_{\delta}$ is well-defined and satisfies
$t_{\delta}(v)\neq t_{\delta}(u)$ for all edges $\\{u,v\\}\in E(T_{\delta})$
with $u,v\in V^{0}(T_{\delta})$. In particular, we have $\delta(x,y)=i$ if and
only if $t_{\delta}(\operatorname{lca}_{T_{\delta}}(x,y))=i$. Since the
discriminating symbolic representation $(T^{*},t^{*})$ and modular
decomposition trees $(T_{\delta},t_{\delta})$ are unique (up to isomorphism),
we can conclude that the two trees $(T^{*},t^{*})$ and
$(T_{\delta},t_{\delta})$ must be isomorphic. We summarize this discussion in
the following

######  Theorem 4.3.

Suppose $\delta\colon X^{2}_{\mathrm{irr}}\to\Upsilon$ is a symmetric map.
Then there is a discriminating symbolic representation $(T^{*},t^{*})$ of
$\delta$ if and only if $\delta$ is a symbolic ultrametric. In this case,
$(T^{*},t^{*})$ and the labeled MDT $(T_{\delta},t_{\delta})$ are isomorphic.

Note, for symbolic ultrametrics $\delta$, we thus obtain a vertex labeled
median graph $(T_{\delta},t_{\delta})$ that explains $\delta$, since
$\operatorname{lca}_{T_{\delta}}(x,y)=\operatorname{med}_{T_{\delta}}(\rho,x,y)$.

Figure 3: Left: The graph-representation of a map $\delta\colon
X^{2}_{\mathrm{irr}}\to\Upsilon$ with $X=\\{a,b,c,d,e\\}$ and
$\delta(a,b)=\mathrm{blue}$ _(dashed-dotted-line)_ ,
$\delta(b,c)=\delta(b,d)=\delta(b,e)=\mathrm{red}$ _(solid-line)_ ,
$\delta(a,c)=\delta(a,d)=\delta(a,e)=\delta(c,e)=\mathrm{purple}$ _(dashed-
line)_ , $\delta(c,d)=\delta(d,e)=\mathrm{green}$ _(dotted-line)_. Right: The
graph-representation of the map
$\delta/\mathbb{M}_{\max}(\delta)\colon\mathbb{M}_{\max}(\delta)^{2}_{\mathrm{irr}}\to\Upsilon$.
Note, $\delta$ is not a symbolic ultrametric, since it does not satisfy (U2)
as e.g. $|\\{\delta(a,b),\delta(a,c),\delta(b,c)\\}|=3$. The strong modules of
$\delta$ are the trivial modules $X$ and $\\{x\\}$ for all $x\in X$ as well as
$\\{c,e\\}$ and $M\coloneqq\\{c,d,e\\}$. Therefore,
$\mathbb{M}_{\max}(\delta)=\\{\\{a\\},\\{b\\},M\\}$ and for the quotient map
$\delta/\mathbb{M}_{\max}(\delta)$ we have
$\delta/\mathbb{M}_{\max}(\delta)(\\{a\\},\\{b\\})=\mathrm{blue}$,
$\delta/\mathbb{M}_{\max}(\delta)(\\{a\\},M)=\mathrm{purple}$ and
$\delta/\mathbb{M}_{\max}(\delta)(\\{b\\},M)=\mathrm{red}$. Note, in this
example, $\delta/\mathbb{M}_{\max}(\delta)$ is prime since
$\mathbb{M}(\delta/\mathbb{M}_{\max}(\delta))$ consists of the trivial modules
$\\{\\{a\\}\\}$, $\\{\\{b\\}\\}$ and $\\{M\\}$ only.

Not all maps $\delta$ are symbolic ultrametrics. The modular decomposition
tree $T_{\delta}$ still exists, but in general there will be no labeling
$t_{\delta}$ such that
$t_{\delta}(\operatorname{lca}_{T_{\delta}}(x,y))=\delta(x,y)$ holds for all
$x\neq y$, see Fig. 4. As a remedy, let us consider the following

######  Definition 4.4.

Let $\delta\colon X^{2}_{\mathrm{irr}}\to\Upsilon$ be a symmetric map. A
_quotient map_ is the map
$\delta/\mathbb{M}_{\max}(\delta)\colon\mathbb{M}_{\max}(\delta)^{2}_{\mathrm{irr}}\to\Upsilon$
obtained from $\delta$ by putting, for all
$M,M^{\prime}\in\mathbb{M}_{\max}(\delta)$,
$\delta/\mathbb{M}_{\max}(\delta)(M,M^{\prime})=\delta(x,y)$ for some $x\in
M$, $y\in M^{\prime}$.

We first note that $\delta/\mathbb{M}_{\max}(\delta)$ is well-defined because
$\mathbb{M}_{\max}(\delta)$ is well-defined and for every two distinct and,
therefore, disjoint modules $M,M^{\prime}\in\mathbb{M}_{\max}(\delta)$ there
is a label $i\in\Upsilon$ with $\delta(x,y)=i$ for all $x\in M$ and $y\in
M^{\prime}$ (cf. Lemma 4.2).

In addition to symbolic ultrametrics, there are two other important subclasses
of symmetric maps $\delta\colon X^{2}_{\mathrm{irr}}\to\Upsilon$:

  * A map $\delta$ is _prime_ if $\mathbb{M}(\delta)$ consists of trivial modules only.

  * $\delta$ is _complete_ if for all $(x,y),(x^{\prime},y^{\prime})\in X^{2}_{\mathrm{irr}}$, $\delta(x,y)=\delta(x^{\prime},y^{\prime})$.

Although maps $\delta$ are not necessarily prime or complete, their quotients
$\delta/\mathbb{M}_{\max}(\delta)$ are always either of one or the other type.

######  Lemma 4.5 ([18, 21, 34]).

Let $\delta$ be a symmetric map. Then the quotient
$\delta/\mathbb{M}_{\max}(\delta)$ is either complete or prime. If $\delta$ is
a symbolic ultrametric, then $\delta/\mathbb{M}_{\max}(\delta)$ is complete.

An illustrative example of the notation established above is provided in Fig.
3 and 4. We shall say that an _inner_ vertex $v$ of $T_{\delta}$ (or,
equivalently, the module $L(v)$ where $L=L_{T_{\delta}}$) is complete or prime
if the quotient $\delta_{|L(v)}/\mathbb{M}_{\max}(\delta_{|L(v)})$ is complete
or prime, respectively. We can now adjust the labeling function by setting

$t_{\delta}(v)=\begin{cases}\mbox{prime, }&\mbox{if }v\mbox{ is prime}\\\
i&\mbox{else, in which case }v=\operatorname{lca}_{T_{\delta}}(x,y)\text{ and
}\delta(x,y)=i\mbox{ for some leaves }x,y\in L(v)\end{cases}$

for all inner vertices $v\in V^{0}(T_{\delta})$.

######  Theorem 4.6.

[34, Thm. 3 and Prop. 1] For a symmetric map $\delta\colon
X^{2}_{\mathrm{irr}}\to\Upsilon$ the following statements are equivalent:

  1. 1.

$\delta$ is a symbolic ultrametric.

  2. 2.

The labeled MDT $(T_{\delta},t_{\delta})$ of $\delta$ has no inner vertex $v$
labeled prime, that is, the quotient
$\delta_{|L(v)}/\mathbb{M}_{\max}(\delta_{|(L(v)})$ is always complete where
$L=X$ denotes the leaf set of $T_{\delta}$.

In order to infer $\delta$ from $T_{\delta}$ we need to determine the label
$\delta(x,y)$ of all pairs of distinct leaves $x,y$ of $T_{\delta}$. In the
case of prime nodes, however, we must therefore drag the entire information of
the quotient maps. An alternative idea is to replace prime vertices by
suitable median graphs and extend the labeling function $t_{\delta}$ that
assigns the “missing information” to the inner vertex of the new graph.

######  Definition 4.7 (prime-vertex replacement (pvr) graphs).

Let $\delta\colon X^{2}_{\mathrm{irr}}\to\Upsilon$ be a symmetric map with MDT
$(T_{\delta},t_{\delta})$ that has leaf set $L=X$. Denote by $\mathcal{P}$ be
the set of all prime vertices in $T_{\delta}$. A _prime-vertex replacement_
(_pvr_) graph $(G^{*},t^{*})$ of $(T_{\delta},t_{\delta})$ is obtained by the
following procedure:

  1. 1.

For all $v\in\mathcal{P}$, remove all edges $\\{v,u\\}$ with
$u\in\operatorname{child}_{T_{\delta}}(v)$ from $T_{\delta}$ to obtain the
forest $(T^{\prime},t_{\delta})$. We note that each child
$u\in\operatorname{child}_{T_{\delta}}(v)$ corresponds to a unique module
$L(u)\in\mathbb{M}_{\max}(\delta_{|(L(v)})$.

  2. 2.

For all $v\in\mathcal{P}$ choose a median graph $G_{v}$ with root $v$ and
leaf-set $L(G_{v})=\\{u\mid L(u)\in\mathbb{M}_{\max}(\delta_{|(L(v)})\\}$ and
labeling $t_{v}\colon V_{\operatorname{med}_{G_{v}},L(G_{v})}\to\Upsilon$ such
that $(G_{v},t_{v})$ explains
$\delta_{|L(v)}/\mathbb{M}_{\max}(\delta_{|(L(v)})$ and such that $v\in
V_{\operatorname{med}_{G_{v}},L(G_{v})}$.

  3. 3.

For all $v\in\mathcal{P}$, add $G_{v}$ to $T^{\prime}$ by identifying the root
of $G_{v}$ with $v$ in $T^{\prime}$ and each leaf $u$ of $G_{v}$ with the
corresponding child $u\in\operatorname{child}_{T_{\delta}}(v)$, for all $v\in
P$. This results in a pvr graph $G^{*}$.

  4. 4.

Let
$W(G^{*})=V^{0}(T_{\delta})\cup\bigcup_{v\in\mathcal{P}}V_{\operatorname{med}_{G_{v}},L(G_{v})}$
be the set of vertices that either obtained a label in $T_{\delta}$ or in one
of the chosen median graphs $(G_{v},t_{v})$. We define a new labeling
$t^{*}\colon W(G^{*})\to\Upsilon$ by putting, for all $v\in W(G^{*})$,

$t^{*}(v)=\begin{cases}t_{\delta}(v)&\mbox{if }v\in
V^{0}(T_{\delta})\setminus\mathcal{P}\\\ t_{v}(v)&\mbox{if }v\in\mathcal{P}\\\
t_{w}(v)&\mbox{else, i.e., }v\in W(G^{*})\setminus V^{0}(T_{\delta})\text{ and
thus, }v\text{ is a vertex of }G_{w}\text{ for some }w\in P\end{cases}$

We next derive some basic properties for pvr graphs that we need later in
order to show that pvr graphs can explain a given map $\delta$.

Figure 4: Left: The graph-representation of the map $\delta\colon
X^{2}_{\mathrm{irr}}\to\Upsilon$ as in Fig. 3. Middle: The MDT
$(T_{\delta},t_{\delta})$. Right: A pvr graph $(G^{*},t^{*})$ of
$(T_{\delta},t_{\delta})$. The root $\rho$ of $(T_{\delta},t_{\delta})$ is
labeled “prime”, since $L_{T_{\delta}}(\rho)=X$ and
$\delta_{|X}/\mathbb{M}_{\max}(\delta_{|X})=\delta/\mathbb{M}_{\max}(\delta)$
is prime, as outlined in the caption of Fig. 3. The pvr graph $(G^{*},t^{*})$
is obtained from $(T_{\delta},t_{\delta})$ by replacing the root $\rho$ by the
median graph $H^{\mathrm{ext}}_{3}$ that explains
$\delta_{|X}/\mathbb{M}_{\max}(\delta_{|X})$ (represented in Fig. 3, right).
The labeling of the white vertex in $(G^{*},t^{*})$ can be chosen arbitrarily.

######  Lemma 4.8.

Let $\delta\colon X^{2}_{\mathrm{irr}}\to\Upsilon$. Then, the pvr graph
$(G^{*},t^{*})$ of the MDT $(T_{\delta},t_{\delta})$ constructed according to
Def. 4.7 is well-defined and unique up to the choice of the median graphs
$(G_{v},t_{v})$ in Def. 4.7(2). Furthermore, we have $V(T_{\delta})\subseteq
V(G^{*})$.

###### Proof.

Let $(T_{\delta},t_{\delta})$ be the MDT of $\delta$ and let $L=X$ denote the
leaf set of $T_{\delta}$. Let $\mathcal{P}$ be the set of all prime vertices
in $T_{\delta}$. We show first that $(G^{*},t^{*})$ is well-defined. By
construction, $L\subseteq V(G^{*})$. Moreover, if $v\in V^{0}(T_{\delta})$ is
a non-prime vertex, then it still exists in $G^{*}$ and $v\in W(G^{*})$. Thus,
we can put $t^{*}(v)=t_{\delta}(v)$. This part is clearly well-defined.

Now let $v\in V(T_{\delta})$ be a prime vertex. By definition,
$\delta_{v}\coloneqq\delta_{|L(v)}/\mathbb{M}_{\max}(\delta_{|L(v)})$ consists
of trivial modules only. Since $\mathbb{M}_{\max}(\delta_{|L(v)})$ is a subset
of strong modules of $\delta$ and $\delta$ is a symmetric map, any two
distinct modules $M,M^{\prime}\in\mathbb{M}_{\max}(\delta_{|L(v)})$ must be
disjoint. Hence, Lemma 4.2 implies that there is a unique label $i\in\Upsilon$
such that $\delta(x,y)=\delta(y,x)=i$ for all $x\in M$ and $y\in M^{\prime}$.
By definition, we thus have
$\delta_{v}(M,M^{\prime})=\delta_{v}(M^{\prime},M)=i$ for some unique label
$i\in\Upsilon$. Consequently, $\delta_{v}$ is a symmetric map and well-
defined. By Theorem 3.10 there is a labeled median graph $(G_{v},t_{v})$ that
explains $\delta_{v}$ and such that $v\in
V_{\operatorname{med}_{G_{v}},L(G_{v})}$. Hence, $(G_{v},t_{v})$ is well
defined. Note that each $M\in\mathbb{M}_{\max}(\delta_{|L(v)})$ corresponds to
some module $L(u)$, $u\in\operatorname{child}_{T_{\delta}}(v)$ and that
$G_{v}$ has leaf set $L(G_{v})=\operatorname{child}_{T_{\delta}}(v)$ where
each child $u\in\operatorname{child}_{T_{\delta}}(v)$ is uniquely identified
with the module $L(u)$. Since $v$ is prime, the edges between the children of
$v$ and vertex $v$ are removed and we add the median graph $G_{v}$ with leaf-
set $L(G_{v})=\operatorname{child}_{T_{\delta}}(v)$ by identifying its root
with $v$ and every $u\in L(G_{v})$ with the unique child
$u\in\operatorname{child}_{T_{\delta}}(v)$ in $T^{\prime}$. As this step is
uniquely determined (up to the choice of $G_{v}$) and applied precisely once
to prime vertices $v$, we can conclude that $G^{*}$ is well-defined.

These arguments in particular imply $V(T_{\delta})\subseteq V(G^{*})$.

We continue to show that the labeling $t^{*}$ is well-defined. As argued
above, $t^{*}(v)=t_{\delta}(v)$ is well-defined for non-prime vertices $v$ of
$T_{\delta}$. Moreover, since $t_{v}$ is a map from
$V_{\operatorname{med}_{G_{v}},L(G_{v})}$ to $\Upsilon$ and since $v\in
V_{\operatorname{med}_{G_{v}},L(G_{v})}$, the assignment $t^{*}(v)=t_{v}(v)$
is well defined for all $v\in\mathcal{P}$. Note, none of the leaves $u\in
L(G_{v})$ are contained in $V_{\operatorname{med}_{G_{v}},L(G_{v})}$ and thus,
do not obtain a label $t_{v}(u)$. By construction, $u\in L(G_{v})$ implies
that $u\in V(T_{\delta})$. Hence, $u\in L(G_{v})$ obtains either the unique
label $t^{*}(u)=t_{\delta}(u)$ if $u\notin\mathcal{P}$ or $t^{*}(u)=t_{u}(u)$
if $u\in\mathcal{P}$. In summary, for all vertices $V(T_{\delta})$ the
labeling $t^{*}$ is well-defined. Now let $v\in W(G^{*})\setminus
V^{0}(T_{\delta})$. In this case, there is a vertex $w$ distinct from $v$ such
that $v\in V(G_{w})$ and $G_{w}$ is the median graph chosen in Step 2. Now,
$G_{w}$ has root $w$. Since $v\in W(G^{*})\setminus V^{0}(T_{\delta})$ we have
$w\in V_{\operatorname{med}_{G_{w}},L(G_{w})}$ by construction, and therefore
$v$ is labeled by $t_{w}(v)$. By construction of $t^{*}$, we have
$t^{*}(v)=t_{w}(v)$, which is well-defined. In summary, therefore, $t^{*}$ is
well-defined. ∎

######  Lemma 4.9.

Let $\delta\colon X^{2}_{\mathrm{irr}}\to\Upsilon$ be a map and let
$(G^{*},t^{*})$ be a pvr graph of the MDT $(T_{\delta},t_{\delta})$. If
$u,v\in V(T_{\delta})$ such that $u\preceq_{T_{\delta}}v$, then
$u\preceq_{G^{*}}v$ and the vertices on the (unique) shortest path
$P_{T_{\delta}}(u,v)$ in $T_{\delta}$ are contained in the vertex set of every
path $P_{G^{*}}(u,v)$ in $G^{*}$.

###### Proof.

If $u=v$ in $T_{\delta}$, then we can apply Lemma 4.9 to conclude that
$V(T_{\delta})\subseteq V(G^{*})$ and thus, $u=v$ in $G^{*}$. In this case,
the path $P_{T_{\delta}}(u,v)$ in $T_{\delta}$ consists of $u$ only and so,
$P_{G^{*}}(u,v)$ does. Hence, we assume in the following that $u,v\in
V(T_{\delta})$ are chosen such that $u\prec_{T_{\delta}}v$.

Assume that $\\{u,v\\}\in E(T_{\delta})$. If $v$ is not a prime vertex, then
this edge $\\{u,v\\}$ also exists in $G^{*}$, by construction. Thus
$u\prec_{G^{*}}v$. Otherwise, if $v$ is a prime vertex it is replaced by a
median graph $G_{v}$ with root $v$ and $u\in L(G_{v})$. That is,
$u\prec_{G_{v}}v$ and, by construction, $u\prec_{G^{*}}v$.

Assume now that $\\{u,v\\}\notin E(T_{\delta})$ and consider the unique path
$P_{T_{\delta}}(u,v)$. By analogous arguments, $b\prec_{G^{*}}a$ for every
edge $\\{a,b\\}$ in the path $P_{T_{\delta}}(a,b)$ with
$b\prec_{T_{\delta}}a$. By induction on the number of edges, we thus conclude
that $u\prec_{G^{*}}v$.

It remains to show that the vertices in the unique shortest
$P_{T_{\delta}}(u,v)$ in $T_{\delta}$ are contained in the vertex set of every
path $P_{G^{*}}(u,v)$ in $G^{*}$. By Lemma 4.8, the vertices in
$P_{T_{\delta}}(u,v)$ are contained in $V(G^{*})$. Let $\\{a,b\\}$ be an edge
in $P_{T_{\delta}}(u,v)$ with $b\prec_{T_{\delta}}a$. As argued above, if $a$
is not prime, then $\\{a,b\\}$ is an edge in $G^{*}$ and, otherwise, we still
have $b\prec_{G^{*}}a$. Hence, if $a$ is not prime, then $P_{G^{*}}(u,v)$ must
contain the edge $\\{a,b\\}$ (since $a$ is the unique last ancestor of $b$)
and, if $a$ is prime, then $P_{G^{*}}(u,v)$ must contain a subpath from $a$ to
$b$ in ${G^{*}}$ that starts at the root $a$ of $G_{a}$ and ends in the leaf
$b$ of $G_{a}$. In summary, $P_{G^{*}}(u,v)$ either still contains the edge
$\\{a,b\\}$ or a path from $a$ to $b$ in $G^{*}$. Hence, the vertices $a$ and
$b$ are contained $P_{G^{*}}(u,v)$. Since the choice of the edge in
$P_{T_{\delta}}(u,v)$ was arbitrary, all vertices of $P_{T_{\delta}}(u,v)$ are
contained in the vertex set of $P_{G^{*}}(u,v)$. Since these arguments apply
to all paths $P_{G^{*}}(u,v)$, the statement follows. ∎

######  Lemma 4.10.

Let $\delta\colon X^{2}_{\mathrm{irr}}\to\Upsilon$ be a map and let
$(G^{*},t^{*})$ be a pvr graph of the MDT $(T_{\delta},t_{\delta})$. Let
$x,y\in X$ be distinct and denote by $v_{x}$ and $v_{y}$ the two children of
$v\coloneqq\operatorname{lca}_{T_{\delta}}(x,y)$ with
$x\preceq_{T_{\delta}}v_{x}$ and $y\preceq_{T_{\delta}}v_{y}$, respectively.
Then, the following two statement are true:

  * (i)

$v_{x},v_{y}\in P_{G^{*}}(x,y)$.

  * (ii)

$\operatorname{med}_{G^{*}}(\rho,x,y)=\operatorname{med}_{G^{*}}(v,v_{x},v_{y})$.
Moreover,
$\operatorname{med}_{G^{*}}(v,v_{x},v_{y})=\operatorname{med}_{G_{v}}(v,v_{x},v_{y})$
in case $v$ is prime and $G_{v}$ is chosen in Step (2) in Def. 4.7.

###### Proof.

(i) If $v=\operatorname{lca}_{T_{\delta}}(x,y)$ is not a prime vertex, then
every path between $v$ and $x$ in $G^{*}$ contains $v_{x}$ while every path
between $v$ and $y$ in $G^{*}$ contains $v_{y}$. Moreover, every path between
$x$ and $y$ in $G^{*}$ must contain vertex $v$. Since every path between $v$
and $x$ in $G^{*}$ as well as between $v$ and $y$ in $G^{*}$ is a subpath of
some path between $x$ and $y$, the vertices $v_{x}$ and $v_{y}$ are contained
in $P_{G^{*}}(x,y)$. If $v$ is a prime vertex, then it is replaced by a median
graph $G_{v}$ and, by construction $v_{x}$ and $v_{y}$ are leaves in $G_{v}$.
Hence, by construction, $v_{x}$ and $v_{y}$ are incomparable. Moreover, by
Lemma 4.9 we have $x\preceq_{G^{*}}v_{x}$ and $y\preceq_{G^{*}}v_{y}$. Note,
by construction, there is no vertex that is incomparable to $v_{x}$ (resp.,
$v_{y}$) that is also an ancestor of $x$ (resp., $y$). Consequently, $v_{x}$
and $v_{y}$ are contained in $P_{G^{*}}(x,y)$.

(ii) Application of Lemma 4.9 implies that $v,v_{x}\in
P_{T_{\delta}}(\rho,x)\subseteq P_{G*}(\rho,x)$ and $v,v_{y}\in
P_{T_{\delta}}(\rho,y)\subseteq P_{G^{*}}(\rho,y)$. Moreover, (i) implies
$v_{x},v_{y}\in P_{T_{\delta}}(x,y)\subseteq P_{G^{*}}(x,y)$. Hence,
$I_{G^{*}}(v,v_{x})\subseteq I_{G^{*}}(\rho,x)$, $I_{G^{*}}(v,v_{y})\subseteq
I_{G^{*}}(\rho,y)$ and $I_{G^{*}}(v_{x},v_{y})\subseteq I_{G^{*}}(x,y)$.
Therefore, $I_{G^{*}}(v,v_{x})\cap I_{G^{*}}(v,v_{y})\cap
I_{G^{*}}(v_{x},v_{y})\subseteq I_{G^{*}}(\rho,x)\cap I_{G^{*}}(\rho,y)\cap
I_{G^{*}}(x,y)$. Since $G^{*}$ is a median graph, both intersections have
precisely one element namely $\operatorname{med}_{G^{*}}(v,v_{x},v_{y})$ and
$\operatorname{med}_{G^{*}}(\rho,x,y)$, which therefore are identical. By
construction, furthermore, we also have
$\operatorname{med}_{G^{*}}(v,v_{x},v_{y})=\operatorname{med}_{G_{v}}(v,v_{x},v_{y})$
in case $v$ is prime. ∎

######  Theorem 4.11.

Let $\delta$ be a symmetric map with MDT $(T_{\delta},t_{\delta})$ and let
$(G^{*},t^{*})$ be a pvr graph for $(T_{\delta},t_{\delta})$. Then,
$(G^{*},t^{*})$ is a median graph that explains $\delta$.

###### Proof.

Let $\mathcal{P}$ be the set of all prime vertices in $T_{\delta}$. We show
first that $G^{*}$ is a median graph. To this end, consider the graph
$G_{v}-L(G_{v})$ obtained from the labeled median graph $(G_{v},t_{v})$
constructed in Step (2) in Def. 4.7. By Lemma 2.6, $G_{v}-L(G_{v})$ remains a
median graph. We denote with $H$ the graph that is the disjoint union of the
graphs $G_{v}-L(G_{v})$ (for all prime vertices $v$) and the connected
components of the forest $T^{\prime}$ obtained in Step (1) in Def. 4.7. Note,
all connected components of $H$ are median graphs and, in particular, $H$ is a
spanning subgraph of $G^{*}$. It is an easy task to verify that every edge
$e\in E(G^{*})\setminus E(H)$ connects precisely two connected components of
$H$. Moreover, all edges $e\in E(G^{*})\setminus E(H)$ that are added to
obtain $G^{*}$ are only edges that are already contained in $T_{\delta}$. In
other words, stepwise addition of edges $e\in E(G^{*})\setminus E(H)$ cannot
create new cycles in $G^{*}$. Hence, whenever we have added a proper subset
$F\subset E(G^{*})\setminus E(H)$ of edges to $H$ and take a further edge
$f\in E(G^{*})\setminus(E(H)\cup F)$ then it must connect again two connected
components of the graph $(V(G^{*}),E(H)\cup F)$. By induction and Lemma 2.6,
the connected components that are joined by a new edge $f$ are again median
graphs. As a consequence, $G^{*}$ is a median graph.

Let $\rho$ be the root of $G^{*}$. It remains to show that $(G^{*},t^{*})$
explains $\delta$. Recall that we have $L(G^{*})=X$ by construction. In order
to verify that $\delta(x,y)=t^{*}(\operatorname{med}_{G^{*}}(\rho,x,y))$ for
all distinct $x,y\in X$ we consider the following cases: Either
$t_{\delta}(\operatorname{lca}_{T_{\delta}}(x,y))=i$ for some $i\in\Upsilon$
or $t_{\delta}(\operatorname{lca}_{T_{\delta}}(x,y))=\text{prime}$. Set
$v\coloneqq\operatorname{lca}_{T_{\delta}}(x,y)$ and denote by $v_{x}$ and
$v_{y}$ the two children of $v$ with $x\preceq_{T_{\delta}}v_{x}$ and
$y\preceq_{T_{\delta}}v_{y}$. Note, $v_{x}$ and $v_{y}$ are incomparable in
${T_{\delta}}$ since $v=\operatorname{lca}_{T_{\delta}}(x,y)$. By Lemma 4.9,
the vertices $v_{x}$ and $v_{y}$ still exist in $G^{*}$ and are, by
construction still incomparable in $G^{*}$.

Suppose first $t_{\delta}(v)=i$ for some $i\in\Upsilon$ in which case
$\delta(x,y)=i$. In this case, $v$ is not a prime vertex and, by construction,
its two children in $G^{*}$ are still $v_{x}$ and $v_{y}$. By Lemma 4.9, $v$
is contained in the shortest paths $P_{G^{*}}(\rho,x)$ as well as
$P_{G^{*}}(\rho,y)$. Moreover, by Lemma 4.10(i), $P_{G^{*}}(x,y)$ contains
$v_{x}$ and $v_{y}$. Since $v_{x}$ and $v_{y}$ have only vertex $v$ as common
adjacent vertex and since any path connecting $v_{x}$ and $v_{y}$ contains
$v$, we can conclude that $P_{G^{*}}(x,y)$ must contain $v$. Since $G^{*}$ is
a median graph this implies that $\operatorname{med}_{G^{*}}(\rho,x,y)=v$.
Since $v$ is not a prime vertex, we have, by construction,
$t^{*}(\operatorname{med}_{G^{*}}(\rho,x,y))=t_{\delta}(v)=\delta(x,y)$.

Now assume that $v$ is prime. In this case, $v$ has been replaced by the
median graph $G_{v}$ according to Def. 4.7(2). In particular, $(G_{v},t_{v})$
explains
$\delta_{v}\coloneqq\delta_{|L(v)}/\mathbb{M}_{\max}(\delta_{|(L(v)})$. Note,
for each child $u\in\operatorname{child}_{T_{\delta}}(v)$, the set $L(u)$ is a
module in $\mathbb{M}_{\max}(\delta_{|L(v)})$. Since $v$ is prime,
$\delta_{v}$ consists of trivial modules only, that is, every
$L(u)\in\mathbb{M}_{\max}(\delta_{|(L(v)})$ forms a trivial module
$M=\\{L(u)\\}$ in $\mathbb{M}(\delta_{v})$. This and definition of
$\delta_{v}$ implies that $\delta_{v}$ maps pairs $(M,M^{\prime})$ of distinct
trivial modules to some label in $\Upsilon$. By definition of $L(G_{v})$, the
leaves $v_{x}$ and $v_{y}$ are contained in $L(G_{v})$ and represent the
trivial modules $\\{L(v_{x})\\}$ and $\\{L(v_{y})\\}$ of $\delta_{v}$. Since
$L(v_{x}),L(v_{y})\in\mathbb{M}_{\max}(\delta_{|(L(v)})$, they are disjoint
and hence, Lemma 4.2 implies that there is a unique label $i\in\Upsilon$ such
that such that $\delta(a,b)=i$ for all $a\in L(v_{x})$ and all $b\in
L(v_{y})$. Therefore we have, by definition,
$\delta_{v}(\\{L(v_{x})\\},\\{L(v_{y}\\}))=i=\delta(x,y)$. Since $v_{x}$ and
$v_{y}$ are contained in $L(G_{v})$ and represent the trivial modules
$\\{L(v_{x})\\}$ and $\\{L(v_{y})\\}$ of $\delta_{v}$, and since
$(G_{v},t_{v})$ explains $\delta_{v}$, we have
$t_{v}(\operatorname{med}_{G_{v}}(\rho,v_{x},v_{y}))=\delta(x,y)$. By Lemma
4.10(ii),
$\operatorname{med}_{G^{*}}(\rho,x,y)=\operatorname{med}_{G_{v}}(v,v_{x},v_{y})=\operatorname{med}_{G^{*}}(v,v_{x},v_{y})$.
This and Def. 4.7(4) implies
$t^{*}(\operatorname{med}_{G^{*}}(\rho,x,y))=t_{v}(\operatorname{med}_{G_{v}}(\rho,v_{x},v_{y}))=\delta(x,y)$.
∎

As a direct consequence of Thm. 4.11 we obtain a practical algorithm to
compute a pvr graph for a given map $\delta$ that is linear in the size of the
input.

Algorithm 1 Construction of a labeled median graph that explains a given
symmetric map.

1:symmetric map $\delta\colon X^{2}_{\mathrm{irr}}\to\Upsilon$

2:pvr graph $(G^{*},t^{*})$ that explains $\delta$

3:Compute MDT $(T_{\delta},t_{\delta})$

4:$(G^{*},t^{*})\leftarrow(T_{\delta},t_{\delta})$

5:$\mathcal{P}\leftarrow$ set of prime vertices in $(T_{\delta},t_{\delta})$

6:for all $v\in\mathcal{P}$ do

7: $n_{v}\leftarrow|\operatorname{child}_{T_{\delta}}(v)|$

8: $(G^{*},t^{*})\leftarrow$ graph obtained from $(G^{*},t^{*})$ by replacing
$v$ by $(G_{v},t_{v})$ where $G_{v}\simeq H^{\mathrm{ext}}_{n_{v}}$ (cf. Def.
4.7)

9:return $(G^{*},t^{*})$

######  Theorem 4.12.

Algorithm 1 correctly computes a labeled median graph $(G,t)$ that explains a
given symmetric map $\delta\colon X^{2}_{\mathrm{irr}}\to\Upsilon$ in $O(m)$
time, where the input size is $m=|X^{2}|$.

###### Proof.

By Theorem 4.11, every pvr graph as constructed in Def. 4.7 explains $\delta$.
Hence, it remains to show that replacing each prime vertex $v$ by
$(G_{v},t_{v})=(H^{\mathrm{ext}}_{n},t_{v})$ with
$n_{v}=|\operatorname{child}_{T_{\delta}}(v)|$ yields a valid pvr graph.
Observe first that every prime vertex $v$ must have at least three children
since otherwise, $\delta_{|L(v)}/\mathbb{M}_{\max}(\delta_{|L(v)})$ is
complete. Hence, $H^{\mathrm{ext}}_{n_{v}}$ is well-defined since $n_{v}\geq
3$ for all $v\in\mathcal{P}$. This and Prop. 3.8 implies that
$H^{\mathrm{ext}}_{n_{v}}$ is a well-defined median graph for all
$v\in\mathcal{P}$. As outlined in the proof of Thm. 3.10, there is a labeling
$t_{v}$ such that $(H^{\mathrm{ext}}_{n_{v}},t_{v})$ explains any map
$\delta_{|L(v)}/\mathbb{M}_{\max}(\delta_{|L(v)})$. Hence, Algorithm 1 is
correct.

To compute the running time, we first note that by [34, Thm. 7] the MDT
$(T_{\delta},t_{\delta})$ can be computed in $O(|X|^{2})$ time. Computing the
initial graph $(G^{*},t^{*})$ and the set of prime vertices $\mathcal{P}$ can
be done in $O(|X|)$ because $T_{\delta}$ is a tree and thus has $O(|X|)$ edges
and vertices. Set $V\coloneqq V(T_{\delta})$. By construction,
$H^{\mathrm{ext}}_{n_{v}}$ has $O(n_{v}^{2})$ edges and vertices. Each prime
vertex $v\in\mathcal{P}$ therefore can be replaced by $(G_{v},t_{v})$ with
$G_{v}\simeq H^{\mathrm{ext}}_{n_{v}}$ in $O(n_{v}^{2})$ time. Repeating the
latter for all prime vertices works thus in
$O(\sum_{v\in\mathcal{P}}n_{v}^{2})\subseteq O(\sum_{v\in
V}n_{v}^{2})\subseteq O(|V|\sum_{v\in V}n_{v})\subseteq O(|V|\sum_{v\in
V}\deg(v))\subseteq O(|V||E(T_{\delta})|)=O(|V|^{2})=O(|X|^{2})$ time. The
total effort is therefore in $O(|X|^{2})$. ∎

##  5 Future Directions

In summary, we have shown that labeled extended hypercubes, extended half-
grids, and pvr graphs can be used to explain a given symmetric map $\delta$.
Clearly, pvr graphs with leaf set $X$ have usually fewer vertices than
extended half-grids $H^{\mathrm{ext}}_{|X|}$, which in turn are much smaller
than extended hypercubes $Q^{\mathrm{ext}}_{|X|}$. This begs the question
under which conditions it is possible to further simplify a rooted median
graph $(G,t)$ that explains a map $\delta$. More precisely, a given labeled
rooted median graph $(G,t)$ with leaf set $X$ is _least-resolved_ w.r.t. a
given map $\delta\colon X^{2}_{\mathrm{irr}}\to\Upsilon$ if it explains
$\delta$ and there is no labeled rooted median graph $(G^{*},t^{*})$
explaining $\delta$ that can be obtained from $G$ by edge contraction (and the
removal of any multi-edge that may result in the process). Furthermore, let us
say that $(G,t)$ is _minimally-resolved_ w.r.t. $\delta$, if it explains
$\delta$ and has among all labeled rooted median graphs with leaf set $X$ that
explain $\delta$ the fewest number of vertices.

Figure 5: The map $\delta$ as in Fig. 2(left) explained by a labeled halfgrid
$(H^{\mathrm{ext}}_{4},t)$ that explains $\delta$ (middle). After contraction
of the two edges incident to the root and removing one of the resulting
“multi”-edges one obtains the graph $(G,t^{\prime})$ on the right. It is easy
to verify that $G$ is a grid-graph and, since all inner faces are squares, $G$
is a median graph (c.f. Thm. 2.5). In particular, $(G,t^{\prime})$ is a least-
resolved median graph that explains $\delta$. Figure 6: Both graphs explain
the same symmetric map $\delta$. However, the rooted median graph $(G,t)$
(left) has only 10 vertices and 10 edges while the labeled MDT
$(T_{\delta},t_{\delta})$ has 11 vertices and 10 edges. Thus, although
$(T_{\delta},t_{\delta})$ is least-resolved w.r.t. $\delta$ it is not
minimally-resolved w.r.t. $\delta$.

The graph in Fig. 5(right), for example, is obtained from the halfgrid in Fig.
5(middle) by contraction of two edges and removal of one of the resulting
multi-edges connecting the root $\rho$ and the purple-colored vertex. The
resulting graph is still a median graph that explains $\delta$. Hence, the
halfgrid is not least-resolved w.r.t. the given map $\delta$. The tree
$(T_{\delta},t_{\delta})$ in Fig. 6 is least-resolved w.r.t. $\delta$. It is
not minimally resolved, however, since the median graph $(G,t)$ in Fig. 6
explains the same map $\delta$ with fewer vertices. These example suggest to
characterize least resolved and minimally resolved rooted median graphs that
explain a given map $\delta$. The example in Fig. 6 begs the question which
symbolic ultrametrics can be explained by median graph with fewer vertices
than the MDT or cotree?

The definition of minimal resolution suggested above above uses $|V(G)|$ to
measure the size of $(G,t)$. It may no be the most natural choice, however. As
an alternative, one might want to consider median graphs with a minimal number
of edges. Are the discriminating cotrees minimal explanations for symbolic
ultrametrics if $|E(G)|$ is used to quantify size?

A related topic for future work is the use of unrooted instead of rooted
graphs as models of evolutionary relationships. Median networks again appear
as a natural generalization of trees. In fact they are used to describe
population-level variations e.g. in [3]. It seems, however, that in the
unrooted setting ternary rather than binary relations become the natural
mathematical objects to encode events and properties. This line of reasoning
has led to investigations into symbolic ternary metrics and the
characterization of a generalization of symbolic ultrametrics [24, 40]. In
[41] such relations are considered in the context of orthology in the setting
of level-1 networks as a generalization of trees.

#### Acknowledgements.

Stimulating discussions with Carsten R. Seemann are gratefully acknowledged.
This work was funded in part by the _Deutsche Forschungsgemeinschaft_.

## References

  * [1] Hans-Jürgen Bandelt and Andreas W M Dress.  A canonical decomposition theory for metrics on a finite set.  Adv. Math., 92:47–105, 1992.
  * [2] Hans-Jürgen Bandelt, P Forster, B C Sykes, and M B Richards.  Mitochondrial portraits of human population using median networks.  Genetics, 141:743–753, 1995.
  * [3] Hans-Jürgen Bandelt, Vincent Macaulay, and Martin Richards.  Median networks: Speedy construction and greedy reduction, one simulation, and two case studies from human mtDNA.  Mol Phylog Evol, 16:8–28, 2000.
  * [4] Sebastian Böcker and Andreas W. M. Dress.  Recovering symbolically dated, rooted trees from symbolic ultrametrics.  Adv. Math., 138:105–125, 1998.
  * [5] Paola Bonizzoni and Gianluca Della Vedova.  Modular decomposition of hypergraphs.  In M. Nagl, editor, International Workshop on Graph-Theoretic Concepts in Computer Science, volume 1017 of Lect. Notes Comp. Sci., pages 303–317, Berlin, Heidelberg, 1995. Springer.
  * [6] Paola Bonizzoni and Gianluca Della Vedova.  An algorithm for the modular decomposition of hypergraphs.  J. Algorithms, 32:65–86, 1999.
  * [7] Abderrahim Boussaïri, Brahim Chergui, Pierre Ille, and Mohamed Zaidi.  3-uniform hypergraphs: modular decomposition and realization by tournaments.  Contrib. Discr. Math., 15:121–158, 2020.
  * [8] Peter Buneman.  The recovery of trees from measures of dissimilarity.  In Frank Roy Hodson, David George Kendall, and Petre Tautu, editors, Mathematics in the Archaeological and Historical Sciences, pages 387–385. Edinburgh University Press, Edinburgh, 1971.
  * [9] Tiziana Calamoneri and Blerina Sinaimeri.  Pairwise compatibility graphs: A survey.  SIAM Review, 58:445–460, 2016.
  * [10] D. G. Corneil, H. Lerchs, and L. Steward Burlingham.  Complement reducible graphs.  Discr. Appl. Math., 3:163–174, 1981.
  * [11] C. Crespelle and C. Paul.  Fully dynamic recognition algorithm and certificate for directed cographs.  Discr. Appl. Math., 154:1722–1741, 2006.
  * [12] Tanja Dravec and Andrej Taranenko.  Daisy Hamming graphs.  Discussiones Math. Graph Theory, 2020.
  * [13] Andreas W. M. Dress, Micheal D. Hendy, Katharina T. Huber, and Vincent Moulton.  On the number of vertices and edges of the Buneman graph.  Ann. Comb., 1:329–337, 1997.
  * [14] A Ehrenfeucht, T. Harju, and G. Rozenberg.  Incremental construction of 2-structures.  Discr. Math, 128:113–141, 1994.
  * [15] A. Ehrenfeucht, T. Harju, and G. Rozenberg.  Theory of 2-structures.  In Zoltán Fülöp and Ferenc Gécseg, editors, Automata, Languages and Programming: Proceedings of the 22nd International Colloquium, ICALP 95 Szeged, Hungary, July 10–14, 1995, pages 1–14. Springer, Berlin, Heidelberg, 1995.
  * [16] A. Ehrenfeucht and G. Rozenberg.  Primitivity is hereditary for 2-structures.  Theor. Comp. Sci., 70:343–358, 1990.
  * [17] A Ehrenfeucht and G Rozenberg.  Theory of 2-structures, part I: Clans, basic subclasses, and morphisms.  Theor. Comp. Sci., 70:277–303, 1990.
  * [18] A Ehrenfeucht and G Rozenberg.  Theory of 2-structures, part II: Representation through labeled tree families.  Theor. Comp. Sci., 70:305–342, 1990.
  * [19] Andrzej Ehrenfeucht, Harold N. Gabow, Ross M. Mcconnell, and Stephen J. Sullivan.  An $O(n^{2})$ divide-and-conquer algorithm for the prime tree decomposition of two-structures and modular decomposition of graphs.  J. Algorithms, 16:283–294, 1994.
  * [20] Andrzej Ehrenfeucht, Tero Harju, and Grzegorz Rozenberg.  The theory of 2-structures: A framework for decomposition and transformation of graphs.  World Scientific, Singapore, 1999.
  * [21] J. Engelfriet, T. Harju, A. Proskurowski, and G Rozenberg.  Characterization and complexity of uniformly nonprimitive labeled 2-structures.  Theor. Comp. Sci., 154:247–282, 1996.
  * [22] Tibor Gallai.  Transitiv orientierbare graphen.  Acta Math. Acad. Sci. Hung., 18:25–66, 1967.
  * [23] Manuela Geiß, John Anders, Peter F. Stadler, Nicolas Wieseke, and Marc Hellmuth.  Reconstructing gene trees from Fitch’s xenology relation.  J. Math. Biol., 77:1459–1491, 2017.
  * [24] Stefan Grünewald, Yangjing Long, and Yaokun Wu.  Reconstructing unrooted phylogenetic trees from symbolic ternary metrics.  Bull. Math. Biol., 80:1563–1577, 2018.
  * [25] Michel Habib, Fabien de Montgolfier, Lalla Mouatadid, and Mengchuan Zou.  A general algorithmic scheme for modular decompositions of hypergraphs and applications.  In C. Colbourn, R. Grossi, and N. Pisanti, editors, International Workshop on Combinatorial Algorithms, volume 11638 of Lect. Notes Comp. Sci., pages 251–264, Cham, 2019. Springer.
  * [26] Michel Habib and Christophe Paul.  A survey of the algorithmic aspects of modular decomposition.  Comp. Sci. Rev., 4:41–59, 2010.
  * [27] R. Hammack, W. Imrich, and S. Klavžar.  Handbook of Product Graphs.  Discrete Mathematics and its Applications. CRC Press, 2nd edition, 2011\.
  * [28] M. Hellmuth.  Generalized Fitch graphs: Edge-labeled graphs that are explained by edge-labeled trees.  Discr. Appl. Math., 267:1–11, 2019.
  * [29] M. Hellmuth and C. R. Seemann.  Alternative characterizations of Fitch’s xenology relation.  J. Math. Biology, 79:969–986, 2019.
  * [30] M. Hellmuth, C. R. Seemann, and P. F. Stadler.  Generalized fitch graphs II: Sets of binary relations that are explained by edge-labeled trees.  Discrete Appl. Math., 283:495–511, 2020.
  * [31] Marc Hellmuth, Adrian Fritz, Nicolas Wieseke, and Peter F. Stadler.  Cograph editing: Merging modules is equivalent to editing $P_{4}$s.  Art Discrete Appl. Math., 3:P2.01, 2020.
  * [32] Marc Hellmuth, Maribel Hernandez-Rosales, Katharina T. Huber, Vincent Moulton, Peter F. Stadler, and Nicolas Wieseke.  Orthology relations, symbolic ultrametrics, and cographs.  J Math Biol, 66:399–420, 2013.
  * [33] Marc Hellmuth, Maribel Hernandez-Rosales, Yangjing Long, and Peter F. Stadler.  Inferring phylogenetic trees from the knowledge of rare evolutionary events.  J. Math. Biol., 76:1623–1653, 2018.
  * [34] Marc Hellmuth, Peter F. Stadler, and Nicolas Wieseke.  The mathematics of xenology: Di-cographs, symbolic ultrametrics, 2-structures and tree-representable systems of binary relations.  J. Math. Biology, 75:199–237, 2017.
  * [35] Marc Hellmuth and Nicolas Wieseke.  On symbolic ultrametrics, cotree representations, and cograph edge decompositions and partitions.  In Dachuan Xu, Donglei Du, and Dingzhu Du, editors, Computing and Combinatorics, volume 9198 of Lect. Notes Comp. Sci., pages 609–623. Springer, Cham, 2015.
  * [36] Marc Hellmuth and Nicolas Wieseke.  From sequence data incl. orthologs, paralogs, and xenologs to gene and species trees.  In P. Pontarotti, editor, Evolutionary Biology, chapter 21, pages 373–392. Springer, Cham, 2016.
  * [37] Marc Hellmuth and Nicolas Wieseke.  On tree representations of relations and graphs: Symbolic ultrametrics and cograph edge decompositions.  J. Comb. Opt., 36:591–616, 2018.
  * [38] Marc Hellmuth, Nicolas Wieseke, Marcus Lechner, Hans-Peter Lenhof, Martin Middendorf, and Peter F. Stadler.  Phylogenomics with paralogs.  Proc. Natl. Acad. Sci. USA, 112:2058–2063, 2015.
  * [39] Katharina T. Huber and Vincent Moulton.  The relation graph.  Discr. Math., 244:153–166, 2002.
  * [40] Katharina T. Huber, Vincent Moulton, and Guillaume E. Scholz.  Three-way symbolic tree-maps and ultrametrics.  J Classif., 36:513–540, 2019.
  * [41] Katharina T. Huber and Guillaume E. Scholz.  Beyond representing orthology relations by trees.  Algorithmica, 80:73–103, 2018.
  * [42] D H Huson and C Scornavacca.  A survey of combinatorial methods for phylogenetic networks.  Genome Biol Evol, 3:23–35, 2011.
  * [43] W. Imrich, S. Klavžar, and D.F. Rall.  Graphs and their Cartesian Product.  Topics in Graph Theory. A K Peters, Ltd., Wellesley, MA, 1st edition, 2008\.
  * [44] P. E. Kearney, J. I. Munro, and D. Phillips.  Efficient generation of uniform samples from phylogenetic trees.  In Algorithms in Bioinformatics (WABI 2003 Budapest), volume 2812 of Lect. Notes Comp. Sci., pages 177–189, Berlin, 2003. Springer.
  * [45] Sandi Klavžar and Riste Škrekovski.  On median graphs and median grid graphs.  Discr. Math., 219:287–293, 2000.
  * [46] Sandi Klavžar and Henry Martyn Mulder.  Median graphs: characterizations, location theory and related structures.  J. Comb. Math. Comb. Computing, 30:103–128, 1999.
  * [47] Ross M. McConnell.  An $O(n^{2})$ incremental algorithm for modular decomposition of graphs and 2-structures.  Algorithmica, 14:229–248, 1995.
  * [48] Martyn Mulder.  The structure of median graphs.  Discr. Math., 24:197–204, 1978.
  * [49] Charles Semple and Mike Steel.  Phylogenetics, volume 24 of Oxford Lecture Series in Mathematics and its Applications.  Oxford University Press, Oxford, 2003.
  * [50] J. M. S. Simões-Pereira.  A note on the tree realizability of a distance matrix.  J. Combin. Theory, 6:303–310, 1969.
  * [51] Andrej Taranenko.  Daisy cubes: a characterization and a generalization.  Eur. J. Comb., 85:103058, 2020.