  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(\mathrm{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.
