Victor Chepoi
email: victor.chepoi@lis-lab.fr

Arnaud Labourel
email: arnaud.labourel@lis-lab.fr

Sébastien Ratel
email: sebastien.ratel@lis-lab.fr

Distance and routing labeling schemes for cube-free median graphs 1

Distance labeling schemes are schemes that label the vertices of a graph with short labels in such a way that the distance between any two vertices u and v can be determined efficiently by merely inspecting the labels of u and v, without using any other information. Similarly, routing labeling schemes label the vertices of a graph in a such a way that given the labels of a source node and a destination node, it is possible to compute efficiently the port number of the edge from the source that heads in the direction of the destination. One of important problems is finding natural classes of graphs admitting distance and/or routing labeling schemes with labels of polylogarithmic size. In this paper, we show that the class of cube-free median graphs on n nodes enjoys distance and routing labeling schemes with labels of O(log 3 n) bits.

Introduction

Classical network representations are usually global in nature. In order to derive a useful piece of information, one must access to a global data structure representing the entire network even if the needed information only concerns few nodes. Nowadays, with networks getting bigger and bigger, the need for locality is more important than ever. Indeed, in several cases, global representations are impractical and network representation must be distributed. The notion of (distributed) labeling scheme has been introduced [START_REF] Breuer | An unexpected result in coding the vertices of a graph[END_REF][START_REF] Gavoille | Distance labeling in graphs[END_REF][START_REF] Kannan | Implicit representation of graphs[END_REF][START_REF] Peleg | Proximity-preserving labeling schemes[END_REF][START_REF] Peleg | Informative labeling schemes for graphs[END_REF] in order to meet this need. A (distributed) labeling scheme is a scheme maintaining global information on a network using local data structures (or labels) assigned to nodes of the network. Their goal is to locally store some useful information about the network in order to answer a specific query concerning a pair of nodes by only inspecting the labels of the two nodes. Motivation for such localized data structure in distributed computing is surveyed and widely discussed in [START_REF] Peleg | Proximity-preserving labeling schemes[END_REF]. The predefined queries can be of various types such as distance, adjacency, or routing. The quality of a labeling scheme is measured by the size of the labels of nodes and the time required to answer queries. Trees with n vertices admit adjacency and routing labeling schemes with size of labels and query time O(log n) and distance labeling schemes with size of labels and query time O(log 2 n), and this is asymptotically optimal. Finding natural classes of graphs admitting distance labeling schemes with labels of polylogarithmic size is an important and challenging problem.

A connected graph G is median if any triplet of vertices x, y, z contains a unique vertex simultaneously lying on shortest (x, y)-, (y, z)-, and (z, x)-paths. Median graphs constitute the most important class in metric graph theory [START_REF] Bandelt | Metric graph theory and geometry: a survey[END_REF]. This importance is explained by the bijections between median graphs and discrete structures arising and playing important roles in completely different areas of research in mathematics and theoretical computer science: in fact, median graphs, 1-skeletons of CAT(0) cube complexes from geometric group theory [START_REF] Gromov | Hyperbolic groups[END_REF][START_REF] Sageev | CAT(0) cube complexes and groups[END_REF], domains of event structures from concurrency [START_REF] Winskel | Models for concurrency[END_REF], median algebras from universal algebra [START_REF] Bandelt | Median algebras[END_REF], and solution sets of 2-SAT formulae from complexity theory [START_REF] Mulder | Median graphs and Helly hypergraphs[END_REF][START_REF] Schaefer | The complexity of satisfiability problems[END_REF] are all the same. In this paper, we design a distance labeling scheme for median graphs containing no cubes. In our scheme, the labels have O(log 3 n) bits and O(1) query time. Our constant query time assumes the standard word-RAM model with word size Ω(log n).

We continue with the idea of the labeling scheme. It generalizes the distance labeling scheme for trees proposed by Peleg in [START_REF] Peleg | Proximity-preserving labeling schemes[END_REF] and our work can be viewed in a sense as an answer to the question

1
The short version of this paper appeared at MFCS 2019 2 Corresponding author, E-mail: arnaud.labourel@lis-lab.fr "How far can we take the scheme of Peleg?". Let G = (V, E) be a cube-free median graph with n vertices. First, the algorithm computes a centroid (median) vertex c of G and the star St(c) of c (the union of all edges and squares of G incident to c). The star St(c) is gated, i.e., each vertex of G has a unique projection (nearest vertex) in St(c). Therefore, with respect to the projection function, the vertex-set of G is partitioned into fibers: the fiber F (x) of x ∈ St(c) consists of all vertices v ∈ V having x as the projection in St(c). Since c is a centroid of G, each fiber contains at most n 2 vertices. The fibers are also gated and are classified into panels and cones depending on the distance between their projections and c (one for panels and two for cones). Each cone has at most two neighboring panels however a panel may have an unbounded number of neighboring cones. Given two arbitrary vertices u and v of G, we show that d G (u, v) = d G (u, c) + d G (c, v) for all locations of u and v in the fibers of St(c) except the cases when u and v belong to neighboring cones and panels, or u and v belong to two cones neighboring the same panel, or u and v belong to the same fiber. If d G (u, v) = d G (u, c)+d G (c, v), then d G (u, v) can be retrieved by keeping d G (u, c) in the label of u and d G (v, c) in the label of v. If u and v belong to the same fiber F (x), the computation of d G (u, v) is done by recursively partitioning the cube-free median graph F (x) at a later stage of the recursion. In the two other cases, we show that d G (u, v) can be retrieved by keeping in the labels of vertices in all cones the distances to their projections on the two neighboring panels. It turns out (and this is the main technical contribution of the paper), that for each panel F (x), the union of all projections of vertices from neighboring cones on F (x) is included in an isometric tree of G and that the vertices of the panel F (x) contain one or two projections in this tree. All such outward and inward projections are kept in the labels of respective vertices. Therefore, one can use distance labeling schemes for trees to deal with vertices u and v lying in neighboring fibers or in cones having a common neighboring panel. Consequently, the size of the label of a vertex u on each recursion level is O(log 2 n). Since the recursion depth is O(log n), the vertices of G have labels of size O(log 3 n). The distance d G (u, v) can be retrieved by finding the first time in the recursion when vertices u and v belong to different fibers of the partition. Consequently, the main result of the paper is the following theorem: Theorem 1.1. There exists a distance labeling scheme that constructs in O(n log n) time labels of size O(log 3 n) of the vertices of a cube-free median graph G = (V, E). Given the labels of two vertices u and v of G, it computes in constant time the distance d G (u, v) between u and v.

With the same ideas, it is possible to adapt our technique to design a routing labeling scheme. Theorem 1.2. There exists a routing labeling scheme that constructs in O(n log n) time labels of size O(log 3 n) of the vertices of a cube-free median graph G = (V, E). Given the labels of two vertices u and v, it computes in constant time a port of u to a neighbor of u on a shortest path to v.

Preliminaries

2.1. Basic notions. In this subsection, we recall some basic notions from graph theory. All graphs G = (V, E) occurring in this note are undirected, simple, and connected. In our algorithmic results we will also suppose that they are finite. The closed neighborhood of a vertex v is denoted by N [v] and consists of v and the vertices adjacent to v. The (open) neighborhood N (v) of v is the set N [v] \ {v}. The degree deg(v) of v is the number of vertices in its open neighborhood. We will write u ∼ v if two vertices u and v are adjacent and u v if u and v are not adjacent. We will denote by G[S] the subgraph of G induced by a subset of vertices S of V . If it is clear from the context, we will use the same notation S for the set S and the subgraph G[S] induced by S.

The distance d G (u, v) between two vertices u and v is the length of a shortest (u, v)-path, and the interval I(u, v) between u and v consists of all the vertices on shortest (u, v)-paths, that is, of all vertices (metrically) between u and v: I(u, v)

:= {x ∈ V : d G (u, x) + d G (x, v) = d G (u, v)}. A subgraph H of a graph G = (V, E) is called an isometric subgraph of G if d H (u, v) = d G (u, v)
for any two vertices u, v of H, i.e., any pair of vertices of H can be connected inside H by a shortest path of G. A subgraph H = (S, E ) of G (or the corresponding vertex set S) is called convex if it includes the interval of G between any pair of H's vertices, i.e., if for any pair u, v of vertices of H all shortest (u, v)-paths of G are included in H. A halfspace of G is a convex subset S with convex complement V \ S. The distance from a vertex v to a subgraph

H of G is d G (v, H) = min{d G (v, x) : x ∈ V (H)}.
A subgraph H of G is said to be gated if for every vertex v / ∈ V (H), there exists a vertex v ∈ V (H) such that for all u ∈ V (H),

d G (v, u) = d G (v, v ) + d G (v , u) (v is called the gate of v in H).
Therefore, v is the gate of v in H if for any vertex u of H, there exists a shortest (u, v)-path passing via v . For a vertex x of a gated subgraph H of G, the set (or the subgraph induced by this set) F (x) = {v ∈ V : x is the gate of v in H} is called the fiber of x with respect to H. From the definition it follows that the fibers {F (x) : x ∈ H} define a partition of the vertex set of G. Notice also that gated sets of a graph enjoy the finite Helly property, that is, every finite family of gated sets that pairwise intersect has a nonempty intersection.

The m-dimensional hypercube Q m is the graph whose vertex-set consists of all subsets of an m-set X := {1, . . . , m} and in which two vertices A and B are linked by an edge if and only if |A B| = 1.

A graph G is called median if the intersection I(x, y) ∩ I(y, z) ∩ I(z, x) is a singleton for each triplet x, y, z of vertices. The unique vertex m(x, y, z) ∈ I(x, y)∩I(y, z)∩I(z, x) is called the median of x, y, z. Median graphs are bipartite. Basic examples of median graphs are trees, hypercubes, rectangular grids, and Hasse diagrams of distributive lattices and of median semilattices [START_REF] Bandelt | Metric graph theory and geometry: a survey[END_REF]. The star St(z) of a vertex z of a median graph G is the union of all hypercubes of G containing z. If G is a tree and z has degree r, then St(z) is the closed neighborhood of z and is isomorphic to K 1,r . The dimension dim(G) of a median graph G is the largest dimension of a hypercube of G.

A cube-free median graph is a median graph G of dimension 2, i.e., a median graph not containing 3-cubes as isometric subgraphs. Two illustrations of cube-free median graphs are given in Figure 1. The left figure will be used as a running example to illustrate the main definitions. Even if cubefree median graphs are the skeletons of 2-dimensional CAT(0) cube complexes, their combinatorial structure is rather intricate. For example, cube-free median graphs are not necessarily planar: for this, take the Cartesian product K 1,n × K 1,m of the stars K 1,n and K 1,m for n, m ≥ 5. Moreover, they may contain any complete graph K n as a minor. Cube-free median graphs and their square complexes have been previously studied in [START_REF] Bandelt | Ramified rectilinear polygons: coordinatization by dendrons[END_REF][START_REF] Brešar | On cube-free median graphs[END_REF][START_REF] Chepoi | On embeddings of CAT(0) cube complexes into products of trees via colouring their hyperplanes[END_REF][START_REF] Chepoi | Shortest path problem in rectangular complexes of global nonpositive curvature[END_REF].

a vertex u ∈ V of a graph G = (V, E), let M (u) := v∈V d G (u, v). A vertex z ∈ V minimizing the function M is called a median of G.
It is well known that any tree T has either a single median or two adjacent medians. Moreover, a vertex v is a median of T if and only if any subtree of T \ {v} contains at most a half of vertices of T . For this reason, a median vertex of a tree is often called a centroid. Further, in order to distinguish medians of triplets and the median vertices of a graph G, we will use the name centroid also for median vertices of G.

In order to make the proofs easier to follow, most of the main definitions and notations are recalled in Section 9.

2.2.

Distance and routing labeling schemes. Let G = (V, E) be a finite graph. The ports of a vertex u ∈ V are the distinct (with respect to u) integers, ranging from one to the degree of u, given to the oriented edges around u, i.e., the edges -→ uv. If uv ∈ E, then the port from u to v, denoted port(u, v), is the integer given to -→ uv. More generally, for arbitrary vertices u, v of G, port(u, v) denotes any value port(u, v ) such that uv ∈ E and v ∈ I(u, v). A graph with ports is a graph to which edges are given ports. All the graphs in this paper are supposed to be graphs with ports.

A labeling scheme on a graph family G consists of an encoding function and a decoding function. The encoding function is given a total knowledge of a graph G ∈ G and gives labels to its vertices in order to allow the decoding function to answer a predefined question (query) with knowledge of a restricted number of labels only. The encoding and decoding functions highly depend on the family G and on the type of queries: adjacency, distance, or routing queries. More formally, a distance labeling scheme on a graph family G consists of an encoding function C G : V (G) → {0, 1} * that gives to every vertex of a graph G of G a label, and of a decoding function D G : {0, 1} * ×{0, 1} * → N that, given the labels of two vertices u and v of G, can compute efficiently the distance d G (u, v) between them. In a routing labeling scheme, the encoding function C G : V (G) → {0, 1} * gives labels such that the decoding function D G : {0, 1} * × {0, 1} * → N is able, given the labels of a source u and a target v, to decide which port of u to take to get closer to v.

We continue by recalling the distance labeling scheme for trees proposed by Peleg in [START_REF] Peleg | Proximity-preserving labeling schemes[END_REF]. First, as we noticed above, if T is a tree with n vertices and c is a centroid of T , then the removal of c splits T in subtrees with at most n 2 vertices each. The distance between any two vertices u and v from different subtrees of T \ {c} is d T (u, c) + d T (c, v). Therefore, each vertex of T can keep in its label the distance to the centroid c. Hence, it remains to recover the information necessary to compute the distance between two vertices in the same subtree of T \ {c}. This can be done by recursively applying to each subtree T of T \ {c} the same procedure as for T . Consequently, the label of each vertex v of T consists of the distances from v to the roots of all subtrees occurring in the recursive calls and containing v. Since from step to step the size of such subtrees is divided by at least 2, v belongs to log 2 n subtrees, thus the label of each vertex v of T has size log 2 2 n bits.

Related work

In this section we review some known results on distance/routing schemes and median graphs.

3.1. Distance and routing labeling schemes. Distance Labeling Schemes (DLS) have been introduced in a series of papers by Peleg et al. [START_REF] Gavoille | Distance labeling in graphs[END_REF][START_REF] Peleg | Proximity-preserving labeling schemes[END_REF][START_REF] Peleg | Informative labeling schemes for graphs[END_REF]. Before these works, some closely related notions already existed such as embeddings in a squashed cube [START_REF] Winkler | Proof of the squashed cube conjecture[END_REF] (equivalent to distance labeling schemes with labels of size log 2 n times the dimension of the cube) or labeling schemes for adjacency requests [START_REF] Kannan | Implicit representation of graphs[END_REF]. One of the main results for DLS is that general graphs support distance labeling schemes with labels of size O(n) bits [START_REF] Alstrup | Simpler, faster and shorter labels for distances in graphs[END_REF][START_REF] Gavoille | Distance labeling in graphs[END_REF][START_REF] Winkler | Proof of the squashed cube conjecture[END_REF]. This scheme is asymptotically optimal since Ω(n) bits labels are needed for general graphs. Another important result is that there exists a distance labeling scheme for trees with O(log 2 n) bits labels [START_REF] Alstrup | Distance labeling schemes for trees[END_REF][START_REF] Freedman | Optimal distance labeling schemes for trees[END_REF][START_REF] Peleg | Proximity-preserving labeling schemes[END_REF]. Several classes of graphs containing trees also enjoy a distance labeling scheme with O(log 2 n) bit labels such as bounded tree-width graphs [START_REF] Gavoille | Distance labeling in graphs[END_REF], distance-hereditary graphs [START_REF] Gavoille | Distance labeling scheme and split decomposition[END_REF], bounded clique-width graphs [START_REF] Courcelle | Query efficient implementation of graphs of bounded clique-width[END_REF], and non-positively curved plane graphs [START_REF] Chepoi | Distance and routing labeling schemes for non-positively curved plane graphs[END_REF]. A lower bound of Ω(log 2 n) bits on the label length is known for trees [START_REF] Alstrup | Distance labeling schemes for trees[END_REF][START_REF] Gavoille | Distance labeling in graphs[END_REF], implying that all the results mentioned above are optimal as well. Other families of graphs have been considered such as interval graphs, permutation graphs, and their generalizations [START_REF] Bazzaro | Localized and compact data-structure for comparability graphs[END_REF][START_REF] Gavoille | Optimal distance labeling for interval graphs and related graph families[END_REF] for which an optimal bound of Θ(log n) bits was given, and planar graphs for which there is a lower bound of Ω(n

3 ) bits [START_REF] Gavoille | Distance labeling in graphs[END_REF] and an upper bound of O( √ n) bits [START_REF] Gawrychowski | A note on distance labeling in planar graphs[END_REF]. (1 + )-Approximate distance labeling schemes with optimal (polylogarithmic) label length are known for networks of bounded doubling dimension [START_REF] Abraham | Forbidden-set distance labels for graphs of bounded doubling dimension[END_REF][START_REF] Talwar | Bypassing the embedding: algorithms for low dimensional metrics[END_REF].

Routing is a basic task that a distributed network must be able to perform. The design of efficient Routing Labeling Scheme (RLS) is a well studied subject; for an overview, we refer to the book [START_REF] Peleg | Distributed Computing: A Locality-Sensitive Approach[END_REF]. One trivial way to produce a RLS, i.e., a routing via shortest paths, is to store a complete routing table at each node of the network. This table specifies, for any destination, the port leading to a shortest path to that destination. This gives an exact RLS with labels of size O(n log d) bits for graphs of maximum degree d that is optimal for general graphs [START_REF] Gavoille | Memory requirement for routing in distributed networks[END_REF]. For trees, there exists exact RLS with labels of size (1 + o(1)) log 2 n [START_REF] Fraigniaud | Routing in trees[END_REF][START_REF] Thorup | Compact routing schemes[END_REF]. Exact RLS with labels of polylogarithmic size also exist for graphs of bounded tree-width, clique-width or chordality [START_REF] Dragan | Collective tree spanners in graphs with bounded parameters[END_REF] and for non-positively curved plane graphs [START_REF] Chepoi | Distance and routing labeling schemes for non-positively curved plane graphs[END_REF]. For the families of graph excluding a fixed minor (including planar and bounded genus graphs), there is an exact RLS with labels of size O( √ n log 2 n/ log log n) [START_REF] Dragan | Collective tree spanners in graphs with bounded parameters[END_REF]. For compact (1 + )-approximate routing schemes for networks of bounded doubling dimension, see [START_REF] Abraham | Routing in networks with low doubling dimension[END_REF][START_REF] Konjevod | Optimal scale-free compact routing schemes in networks of low doubling dimension[END_REF].

3.2. Median graphs. Median graphs and related structures have an extensive literature; for surveys listing their numerous characterizations and properties, see [START_REF] Bandelt | Metric graph theory and geometry: a survey[END_REF][START_REF] Klavžar | Median graphs: characterizations, location theory and related structures[END_REF][START_REF] Knuth | The Art of Computer Programming : Vol. 4. Fascicle 0, Introduction to combinatorial algorithms and Boolean functions[END_REF]. These structures have been investigated in different contexts by quite a number of authors for more than half a century. In this subsection we briefly review the links between median graphs and CAT(0) cube complexes. We also recall some results, related to the subject of this paper, about the distance and shortest path problems in median graphs and CAT(0) cube complexes. For a survey of results on median graphs and their bijections with median algebras, median semilattices, CAT(0) cube complexes, and solution spaces of 2-SAT formulae, see [START_REF] Bandelt | Metric graph theory and geometry: a survey[END_REF]. For a comprehensive presentation of median graphs and CAT(0) cube complexes as domains of event structures, see [START_REF] Chalopin | A counterexample to Thiagarajan's conjecture on regular event structures[END_REF].

Median graphs are intimately related to hypercubes: median graphs can be obtained from hypercubes by amalgams and median graphs are themselves isometric subgraphs of hypercubes [START_REF] Bandelt | Embedding topological median algebras in products of dendrons[END_REF][START_REF] Mulder | The Interval Function of a Graph[END_REF]. Moreover, median graphs are exactly the retracts of hypercubes [START_REF] Bandelt | Retracts of hypercubes[END_REF]. Due to the abundance of hypercubes, to each median graph G one can associate a cube complex X(G) obtained by replacing every hypercube of G by a solid unit cube. Then G can be recovered as the 1-skeleton of X(G). The cube complex X(G) can be endowed with several intrinsic metrics, in particular with the 2 -metric. An important class of cube complexes studied in geometric group theory is the class of CAT(0) cube complexes. CAT(0) geodesic metric spaces are usually defined via the nonpositive curvature comparison axiom of Cartan-Alexandrov-Toponogov [START_REF] Bridson | Metric Spaces of Non-Positive Curvature[END_REF]. For cube complexes (and more generally for cell complexes) the CAT(0) property can be defined in a very simple and intuitive way by the property that 2 -geodesics between any two points are unique. Gromov [START_REF] Gromov | Hyperbolic groups[END_REF] gave a nice combinatorial characterization of CAT(0) cube complexes as simply connected cube complexes with flag links. It was also shown in [START_REF] Chepoi | Graphs of some CAT(0) complexes[END_REF][START_REF] Roller | Poc sets, median algebras and group actions[END_REF] that median graphs are exactly the 1-skeletons of CAT(0) cube complexes.

Previous characterizations can be used to show that several cube complexes arising in applications are CAT(0). Billera et al. [START_REF] Billera | Geometry of the space of phylogenetic trees[END_REF] proved that the space of trees (encoding all tree topologies with a given set of leaves) is a CAT(0) cube complex. Abrams et al. [START_REF] Abrams | State complexes for metamorphic robots[END_REF][START_REF] Ghirst | The geometry and topology of reconfiguration[END_REF] considered the space of all possible positions of a reconfigurable system and showed that in many cases this state complex is CAT(0). Billera et al. [START_REF] Billera | Geometry of the space of phylogenetic trees[END_REF] formulated the problem of computing the geodesic between two points in the space of trees. In the robotics literature, geodesics in state complexes correspond to the motion planning to get the robot from one position to another one with minimal power consumption. A polynomial-time algorithm for geodesic problem in the space of trees was provided in [START_REF] Owen | A fast algorithm for computing geodesic distances in tree space[END_REF]. A lineartime algorithm for computing distances in CAT(0) square complexes (cube complexes of cube-free median graphs) was proposed in [START_REF] Chepoi | Shortest path problem in rectangular complexes of global nonpositive curvature[END_REF]. Recently, Hayashi [START_REF] Hayashi | A polynomial time algorithm to compute geodesics in CAT(0) cubical complexes[END_REF] designed the first polynomial-time algorithm for geodesic problem in all CAT(0) cube complexes.

Returning to median graphs, the following is known about the labeling schemes for them and about some related combinatorial problems. First, the arboricity of any median graph G on n vertices is at most log n, leading to adjacency schemes of O(log 2 n) bits per vertex. As noted in [START_REF] Chepoi | On density of subgraphs of Cartesian products[END_REF], one log 2 n factor can be replaced by the dimension of G. Compact distance labeling schemes can be obtained for some subclasses of cube-free median graphs. One particular class is that of squaregraphs, i.e., plane graphs in which all inner vertices have degree ≥ 4. For squaregraphs, distance schemes with labels of size O(log 2 n) follow from a more general result of [START_REF] Chepoi | Distance and routing labeling schemes for non-positively curved plane graphs[END_REF] for plane graphs of nonpositive curvature. Another such class of graphs is that of partial double trees [START_REF] Bandelt | Ramified rectilinear polygons: coordinatization by dendrons[END_REF]. Those are the median graphs which isometrically embed into a Cartesian product of two trees and can be characterized as the cube-free median graphs in which all links are bipartite graphs [START_REF] Bandelt | Ramified rectilinear polygons: coordinatization by dendrons[END_REF]. The isometric embedding of partial double trees into a product of two trees immediately leads to distance schemes with labels of O(log 2 n) bits. Finally, with a technically involved proof, it was shown in [START_REF] Chepoi | On embeddings of CAT(0) cube complexes into products of trees via colouring their hyperplanes[END_REF] that there exists a constant M such that any cube-free median graph G with maximum degree ∆ can be isometrically embedded into a Cartesian product of at most (∆) := M ∆ 26 trees. This immediately shows that cube-free median graph admit distance labeling schemes with labels of length O( (∆) log 2 n). Compared with the O(log 3 n)-labeling scheme obtained in the current paper, the disadvantage of the resulting O( (∆) log 2 n)-labeling scheme is its dependence of the maximum degree ∆ of G. The situation is even worse for high dimensional median graphs: [START_REF] Chepoi | On embeddings of CAT(0) cube complexes into products of trees via colouring their hyperplanes[END_REF] presents an example of a 5-dimensional median graph/CAT(0) cube complex with constant degree which cannot be embedded into a Cartesian product of a finite number of trees. Therefore, for general finite median graphs the function (∆) does not exist.

Analogously, it was shown in [START_REF] Chepoi | Nice labeling problem for event structures: a counterexample[END_REF] that the nice labeling conjecture for event structures (a conjecture formulated in concurrency theory) is false for event domains which are median graphs of dimension at least 4 but it was proven in [START_REF] Chepoi | On embeddings of CAT(0) cube complexes into products of trees via colouring their hyperplanes[END_REF] that this conjecture is true for event structures with 2-dimensional (cube-free) domains. On the other hand, it was shown in [START_REF] Chalopin | A counterexample to Thiagarajan's conjecture on regular event structures[END_REF] that the Thiagarajan conjecture (an important conjecture in concurrency relating 1-safe Petri nets and regular event structures) is false already for regular event structures with 2-dimensional domains but is true for event structures with hyperbolic domains (the second result heavily relies on the very deep result of Agol [START_REF] Agol | The virtual Haken conjecture[END_REF] from geometric group theory). All this in a sense explains the difficulty of designing polylogarithmic distance labeling schemes for general median graphs and motivates the investigation of such schemes for cube-free median graphs. Nevertheless, we do not have a proof that such schemes do not exist for all median graphs.

Fibers in median graphs

In this section, we recall the properties of median graphs and of the fibers of their gated subgraphs. They will be used in our labeling schemes and some of them could be potentially useful for designing distance labeling schemes for general median graphs. Since all those results are dispersed in the literature and time, we present them with (usually, short and unified) proofs in the appendix.

Lemma 1. (Quadrangle Condition) For any vertices u, v, w, z of a median graph G such that d G (u, z) = k + 1, v, w ∼ z, and d G (u, v) = d G (u, w) = k, there is a unique vertex x ∼ v, w such that d G (u, x) = k -1.
The Quadrangle Condition is simultaneously a local and global metric condition on graphs, which has topological consequences. In bipartite graphs, this condition implies that any cycle C can be "paved" in a special way (from top-to-bottom with respect to any basepoint of C) with quadrangles (4-cycles or squares). This implies that all cycles are null-homotopic, i.e., that the square complexes of such graphs are simply connected. The Quadrangle and Triangle Conditions define the class of weakly modular graphs [START_REF] Bandelt | Metric graph theory and geometry: a survey[END_REF][START_REF] Chepoi | Classification of graphs by means of metric triangles[END_REF], which comprises most of te classes of graphs investigated in Metric Graph Theory; for a full account, see the survey [START_REF] Bandelt | Metric graph theory and geometry: a survey[END_REF] and the recent paper [START_REF] Chalopin | Weakly modular graphs and nonpositive curvature[END_REF].

The following result is a particular case of the local-to-global characterization of convexity and gatedness in weakly modular graphs established in [START_REF] Chepoi | Classification of graphs by means of metric triangles[END_REF]: Lemma 2. A subset of vertices A of a median graph G gated iff A is convex and iff H := G[A] is connected and A is locally convex, i.e., if x, y ∈ A and d G (x, y) = 2, then I(x, y) ⊆ A. Suppose that the median graph G is rooted at an arbitrary vertex v 0 . For a vertex v, all neighbors u of v such that u ∈ I(v, v 0 ) are called predecessors of v. A median graph G satisfies the downward cube property [START_REF] Bénéteau | Medians in median graphs and their cube complexes in linear time[END_REF] if any vertex v and all its predecessors belong to a single cube of G. We continue with properties of stars and fibers of stars. Combinatorially, the stars of median graphs may have quite an arbitrary structure: by a result of [START_REF] Bandelt | Embedding topological median algebras in products of dendrons[END_REF], there is a bijection between the stars of median graphs and arbitrary graphs. Given an arbitrary graph H, the simplex graph [START_REF] Bandelt | Embedding topological median algebras in products of dendrons[END_REF] σ(H) of H has a vertex v σ for each clique of G (i.e., empty set, vertices, edges, triangles, etc.) and two vertices v σ and v σ are adjacent in σ(H) if and only if the cliques σ and σ differ only in a vertex. It was shown in [START_REF] Bandelt | Embedding topological median algebras in products of dendrons[END_REF] that the simplex graph σ(H) of any graph H is a median graph. Moreover, one can easily show that the star in σ(H) of the vertex v ∅ (corresponding to the empty set) coincides with the whole graph σ(H). Vice-versa, any star St(z) of a median graph can be realized as the simplex graph σ(H) of the graph H having the neighbors of z as the set of vertices and two such neighbors u , u of z are adjacent in H if and only if z, u , u belong to a common square of G.

Next, we consider stars St(z) of median graphs from the metric point of view.

Lemma 5. For any vertex z of a median graph G, the star St(z) is a gated subgraph of G.

The following property of median graphs is also well-known in more general contexts. The graphs satisfying this property are called fiber-complemented [START_REF] Chastand | Fiber-complemented graphs. I. Structure and invariant subgraphs[END_REF]. Lemma 6. For any gated subgraph H of a median graph G, the fibers F (x), x ∈ V (H), are gated. Lemma 6 has two corollaries. First, from this lemma and Lemma 5 we obtain: Corollary 3. For any vertex z of a median graph G, the fibers of the star St(z) are gated.

For an edge uv of a median graph G, let andW (v, u) constitute a partition of the vertex set of G. In view of the following result, we will refer to the sets of the form W (u, v), W (v, u) as to the halfspaces of G (recall that a halfspace is a convex set with convex complement): Corollary 4. For any edge uv of a median graph G, the sets W (u, v) and W (v, u) are gated and, thus, are complementary halfspaces of G. Conversely, any pair of complementary halfspaces of G has the form {W (u, v), W (v, u)} for an edge uv of G.

W (u, v) = {z ∈ V : d G (z, u) < d G (z, v)} and W (v, u) = {z ∈ V : d G (z, v) < d G (z, u)}. Since G is bipartite, W (u, v)
Proof. Since edges of a median graph G are gated, the first assertion of the corollary follows by applying Lemma 6 to the edge uv. Conversely, if {H , H } is a pair of complementary halfspaces of G, let uv be an edge of G with u ∈ H and v ∈ H . Since both H and H are convex, we conclude that

H ⊆ W (u, v) and H ⊆ W (v, u). Since both pairs {H , H } and {W (u, v), W (v, u)} define partitions, we have H = W (u, v) and H = W (v, u).
That the halfspaces of a median graph are convex was established first by Mulder [START_REF] Mulder | The Interval Function of a Graph[END_REF]. He also proved that the boundaries of halfspaces are convex (the boundary of the halfspace

W (u, v) is the set ∂W (u, v) = {z ∈ W (u, v) : ∃z ∈ W (v, u), z ∼ z }).
We will prove this property for boundaries of fibers of arbitrary gated subgraphs of a median graph.

Let H be a gated subgraph of a median graph G = (V, E) and let F(H) = {F (x) : x ∈ V (H)} be the partition of V into the fibers of H. We will call two fibers F (x) and F (y) neighboring (notation F (x) ∼ F (y)) if there exists an edge x y of G with one end x in F (x) and another end y in F (y). If F (x) and F (y) are neighboring fibers of H, then denote by ∂ y F (x) the set of all vertices x ∈ F (x) having a neighbor y in F (y) and call ∂ y F (x) the boundary of F (x) relative to F (y).

Lemma 7. Let H be a gated subgraph of a median graph G = (V, E). Two fibers F (x) and F (y) of H are neighboring if and only if

x ∼ y. If F (x) ∼ F (y), then the boundary ∂ y F (x) of F (x) relative to F (y) induces a gated subgraph of G of dimension ≤ dim(G) -1.
For a vertex x of a gated subgraph H of G and its fiber F (x), the union of all boundaries ∂ y F (x) over all F (y) ∼ F (x), y ∈ V (H), is called the total boundary of F (x) and is denoted by ∂ * F (x). More precisely, the vertices and the edges of ∂ * F (x) are the unions of vertices and edges of all boundaries ∂ y F (x) over all fibers F (y) ∼ F (x), y ∈ V (H). Lemma 8. Let H be a gated subgraph of a median graph G of dimension d. Then the total boundary

∂ * F (x) of any fiber F (x) of H does not contain d-dimensional cubes.
Proof. Suppose by way of contradiction that ∂ * F (x) contains a d-dimensional cube Q. Since Q is a gated subgraph of G, we can consider the gate x of x in Q and the vertex furthest from x in Q (this is the vertex of Q opposite to x ). Denote this furthest from x vertex of Q by x . From the choice of x as the gate of x in Q and x as the opposite to

x vertex of Q, we conclude that Q ⊆ I(x, x ). Suppose that x ∈ ∂ y F (x) ⊂ ∂ * F (x). Since ∂ y F (x) is gated (Lemma 7) and Q ⊆ I(x , x), Q is included in the boundary ∂ y F (x). This contradicts Lemma 7 that ∂ y F (x) has dimension ≤ d-1.
Lemma 9. Let H be a gated subgraph of a median graph G. Then the total boundary ∂ * F (x) of any fiber F (x) of H induces an isometric subgraph of G.

Proof. Pick u, v ∈ ∂ * F (x), say u ∈ ∂ y F (x) and v ∈ ∂ z F (x). Let w be the median of the triplet x, u, v. Since w ∈ I(u, x) ⊆ ∂ y F (x) ⊂ ∂ * F (x) we deduce that I(u, w) ⊆ ∂ * F (x). Analogously, we can show that I(v, w) ⊆ ∂ * F (x). Since w ∈ I(u, v) and I(u, w) ∪ I(w, v) ⊆ ∂ * F (x)
, the vertices u and v can be connected in ∂ * F (x) by a shortest path passing via w.

We conclude this section with an additional property of fibers of stars of centroids of

G. Recall, that c is a centroid of G if c minimizes the function M (x) = v∈V d G (x, v).
Lemma 10. Let c be a centroid of a median graph G with n vertices. Then any fiber F (x) of the star St(c) of c has at most n/2 vertices. ,c) and u ∈ I(x, c), and we conclude that

Proof. Suppose by way of contradiction that |F

(x)| > n/2 for some vertex x ∈ St(c). Let u be a neighbor of c in I(x, c). If v ∈ F (x), then x ∈ I(v
u ∈ I(v, c). Consequently, F (x) ⊆ W (u, c), whence |W (u, c)| > n/2. Therefore |W (c, u)| = n -|W (u, c)| < n/2. But this contradicts the fact that c is a centroid of G. Indeed, since u ∼ c, one can easily show that M (u) -M (c) = |W (c, u)| -|W (u, c)| < 0.
Unfortunately, the total boundary ∂ * F (x) of a fiber does not always induce a median subgraph. Therefore, even if ∂ * F (x) is an isometric subgraph of G of dimension ≤ dim(G) -1, one cannot recursively apply the algorithm to the subgraphs induced by the total boundaries ∂ * F (x). However, if G is 2-dimensional (i.e., G is cube-free), then the total boundaries of fibers are isometric subtrees of G and one can use for them distance and routing schemes for trees. Even in this case, we still need an additional property of total boundaries, which we will establish in the next section.

Fibers in cube-free median graphs

In this section, we establish additional properties of fibers of stars and of their total boundaries in cube-free median graphs G = (V, E). Using them we can show that for any pair u, v of vertices of G, the following trichotomy holds: the distance d G (u, v) either can be computed as

d G (u, c) + d G (c, v),
or as the sum of distances from u, v to appropriate vertices u , v of ∂ * F (x) plus the distance between u , v in ∂ * F (x), or via a recursive call to the fiber containing u and v.

Classification of fibers.

From now on, let G = (V, E) be a cube-free median graph. Then the star St(z) of any vertex z of G is the union of all squares and edges containing z. Specifying the bijection between stars of median graphs and simplex graphs of arbitrary graphs mentioned above, the stars of cube-free median graphs correspond to simplex graphs of triangle-free graphs.

Let z be an arbitrary vertex of G and let F z = {F (x) : x ∈ St(z)} denote the partition of V into the fibers of St(z). We distinguish two types of fibers: the fiber

F (x) is called a panel if x is adjacent to z and F (x) is called a cone if x has distance two to z. The interval I(x, z) is the edge xz if F (x) is a panel and is a square Q x := (x, y , z, y ) if F (x)
is a cone. In the second case, since y and y are the only neighbors of x in St(z), by Lemma 7 we deduce that the cone F (x) is adjacent to the panels F (y ) and F (y ) and that F (x) is not adjacent to any other panel or cone. By the same lemma, any panel F (y) is not adjacent to any other panel, but F (y) is adjacent to all cones F (x) such that the square Q x contains the edge yz. For an illustration, see Figure 2. 5.2. Total boundaries of fibers are quasigated. For a set A, an imprint of a vertex u / ∈ A on A is a vertex a ∈ A such that I(u, a) ∩ A = {a}. Denote by Υ(u, A) the set of all imprints of u on A. The most important property of imprints is that for any vertex z ∈ A, there exists a shortest (u, z)-path passing via an imprint, i.e., that I(u, z) ∩ Υ(u, A) = ∅. Therefore, if the set Υ(u, A) has constant size, one can store in the label of u the distances to the vertices of Υ(u, A). Using this, for any

z ∈ A, one can compute d G (u, z) as min{d G (u, a) + d G (a, z) : a ∈ Υ(u, A)}. Note that a set A is gated if

and only if any vertex u /

∈ A has a unique imprint on A. Following this, we will say that a set A is k-gated if for any vertex u / ∈ A, |Υ(u, A)| ≤ k. In particular, we will say that a set A is

quasigated if |Υ(u, A)| ≤ 2 for any vertex u / ∈ A.
The main goal of this subsection is to show that the total boundaries of fibers are quasigated.

Let T be a tree with a distinguished vertex r in G. The vertex r is called the root of T and T is called a rooted tree. We will say that a rooted tree T has gated branches if for any vertex x of T the unique path P (x, r) of T connecting x to the root r is a gated subgraph of G.

By adapting Lemmas 7, 8, and 9 to cube-free median graphs, we obtain the following result:

Lemma 11. For each fiber F (x) of a star St(z) of a cube-free median graph G, the total boundary ∂ * F (x) is an isometric tree with gated branches.

Proof. By Lemma 9, ∂ * F (x) is an isometric subgraph of G. Now we show that ∂ * F (x) is a tree. By Lemma 7, each boundary ∂ y F (x) is a gated tree rooted at x, thus ∂ * F (x) is the union of the gated trees. Suppose by way of contradiction that ∂ * F (x) contains a cycle C. Let u be a furthest from x vertex of C and suppose that u ∈ ∂ y F (x). Let v , v be the neighbors of u in C. Since G is bipartite, from the choice of u we conclude that v , v are closer to x than u. Since ∂ y F (x) is gated, and thus convex, this implies that v , v ∈ I(u, x) ⊆ ∂ y F (x), contrary to the fact that ∂ y F (x) is a gated tree rooted at x. This shows that ∂ * F (x) is an isometric tree of G.

For any vertex v ∈ ∂ * F (x) there exists a fiber

F (y) ∼ F (x) of St(z) such that v belongs to the boundary ∂ y F (x) of F (x) relative to F (y). Since ∂ y F (x) is a gated subtree of G and v, x ∈ ∂ y F (x), the unique path P (v, x) connecting v and x in ∂ y F (x) is a convex subpath of ∂ y F (x)
, and therefore a convex subpath of the whole graph G. Since convex subgraphs are gated, P (x, v) is a gated path of G belonging to ∂ * F (x). This proves that ∂ * F (x) is a tree with gated branches. By Lemma 11, each ∂ * F (x) induces a tree of G. This tree is an isometric subgraph of G, which means that any two vertices of ∂ * F (x) can be connected in ∂ * F (x) by a shortest path of G. Moreover, since ∂ * F (x) has gated branches, the respective shortest path connecting any vertex v of ∂ * F (x) to the root x coincides with the entire interval I(v, x). However the tree ∂ * F (x) is not necessarily gated itself. Since a panel F (x) may be adjacent to an arbitrary number of cones, one can think that the imprint-set Υ(u, ∂ * F (x)) of a vertex u of F (x) may have an arbitrarily large size. The following lemma shows that this is not the case, namely that |Υ(u, ∂ * F (x))| ≤ 2. This is one of the key ingredients in the design of the distance and routing labeling schemes presented in Sections 6 and 7.

Lemma 12. Any rooted tree T with gated branches of G = (V, E) is quasigated.

Proof. Let r be the root of T . Pick any u ∈ V \ V (T ) and suppose by way of contradiction that Υ(u, T ) contains three distinct imprints x 1 , x 2 , and x 3 . Since T has gated branches, none of the vertices x 1 , x 2 , x 3 belong to the path of T between the root r and another vertex from this triplet. In particular, r is different from x 1 , x 2 , x 3 . Suppose additionally that among all rooted trees T with gated branches of G and such that |Υ(u, T )| ≥ 3, the tree T has the minimal number of vertices. This minimality choice (and the fact that any subtree of T containing r is also a rooted tree with gated branches) implies that T is exactly the union of the three gated paths P (r, x 1 ), P (r, x 2 ), and P (r, x 3 ) connecting the root r with the leaves x 1 , x 2 , and x 3 of T . Notice that P (r, x 1 ), P (r, x 2 ), and P (r, x 3 ) not necessarily pairwise intersect only in r.

First, notice that x 1 , x 2 , x 3 ∈ I(u, r). Indeed, let z i denote the median of the triplet x i , u, r. If z i = x i , since z i ∈ I(x i , r) = P (x i , r) ⊂ T and z i ∈ I(u, x i ), we obtain a contradiction with the inclusion of x i in Υ(u, T ). Thus z i = x i , yielding x i ∈ I(u, z i ).

Let y i be the neighbor of x i in the path P (r, x i ), i = 1, 2, 3. Since G is bipartite, either x i ∈ I(y i , u) or y i ∈ I(x i , u). Since x i ∈ Υ(u, T ), necessarily x i ∈ I(y i , u). Let T i be the subtree of T obtained by removing the leaf x i . From the minimality choice of T , we cannot replace T by the subtree

T i . This means that |Υ(u, T i )| ≤ 2. Since x j , x k ∈ Υ(u, T i ) for {i, j, k} = {1, 2, 3}, necessarily I(y i , u) ∩ {x j , x k } = ∅ holds.
Suppose without loss of generality that d G (r, x 3 ) = max{d G (r, x i ) : i = 1, 2, 3} := k. Since I(y 3 , u)∩{x 1 , x 2 } = ∅ holds, we can suppose without loss of generality that x 2 ∈ I(y 3 , u). Since x 3 ∈ I(y 3 , u), from these two inclusions we obtain that d G (x 3 , u)

+ 1 = d G (y 3 , x 2 ) + d G (x 2 , u). Therefore, d G (x 3 , u) ≥ d G (x 2 , u). Since x 2 , x 3 ∈ I(u, r), we have d G (u, x 2 ) + d G (x 2 , r) = d G (u, x 3 ) + d G (x 3 , r). Since d G (r, x 3 ) ≥ d G (r, x 2 ), all this is possible only if d G (x 3 , u) = d G (x 2 , u) and d G (x 3 , r) = d G (x 2 ,
r). Moreover, d G (y 3 , x 2 ) = 1 holds, i.e., y 3 and x 2 are adjacent in T . Since x 2 is a leaf of T , this is possible only if y 2 and y 3 coincide. Let y := y 2 = y 3 . We distinguish two cases:

Case 1. d G (x 1 , r) = k.
Since all three vertices x 1 , x 2 , x 3 have the same distance k to r, we can apply to x 1 the same analysis as to x 3 and deduce that the neighbor y 1 of x 1 in T coincides with one of the vertices y 2 , y 3 . Since y 2 = y 3 = y, we conclude that the vertices x 1 , x 2 , x 3 have the same neighbor y in T . Since y is closer to r than each of the vertices x 1 , x 2 , x 3 and since x 1 , x 2 , x 3 ∈ I(r, u), we conclude that x 1 , x 2 , x 3 ∈ I(y, u). By the minimality of T , we conclude that k = 1 and y = r, i.e., T consists only of x 1 , x 2 , x 3 , and y = r. Applying the quadrangle condition three times, we can find three vertices x i,j , i, j ∈ {1, 2, 3}, i = j, such that x i,j ∼ x i , x j and d G (x i,j , u) = k -1 (see Figure 3, left). If two of the vertices x 1,2 , x 2,3 , and x 3,1 coincide, then we will get a forbidden K 2,3 : if, say x 1,2 = x 2,3 , then this copy of K 2,3 contains the vertices y, x 1 , x 2 , x 3 , and x 1,2 = x 2,3 . Thus x 1,2 , x 2,3 , and x 3,1 are pairwise distinct. Since G is bipartite, this implies that d G (x i , x j,k ) = 3 for {i, j, k} = {1, 2, 3}. Since x 1,2 , x 2,3 ∈ I(x 2 , u), by quadrangle condition there exists a vertex

w such that w ∼ x 1,2 , x 2,3 and d G (w, u) = k -2. Since G is bipartite, d G (w, x 3,1 ) equals to 3 or to 1. If d G (w, x 3,1 ) = 3 = d G (y, w)
, then the triplet y, w, x 3,1 has two medians x 1 and x 3 , which is impossible, because G is median. Thus d G (w, x 3,1 ) = 1, i.e., w ∼ x 3,1 . Then one can easily see that the vertices y, x 1 , x 2 , x 3 , x 1,2 , x 2,3 , x 3,1 , w define an isometric 3-cube of G, contrary to the assumption that G is cube-free. This finishes the analysis of Case 1.

Case 2. d G (x 1 , r) < k. This implies that d G (r, x 1 ) ≤ k -1 = d G (r, y).
Let r be the neighbor of r in the (r, y)-path of T . Notice that r / ∈ I(r, x 1 ) = P (r, x 1 ). Indeed, otherwise, r ∈ P (r, x 1 ) ∩ P (r, x 2 ) ∩ P (r, x 3 ) and we can replace the tree T by the subtree T rooted at r and consisting of the subpaths of P (r, x i ) comprised between r and x i , i = 1, 2, 3. Clearly T is a rooted tree with gated branches and x 1 , x 2 , x 3 ∈ Υ(u, T ), contrary to the minimality choice of the counterexample T . Thus r / ∈ P (r, x 1 ). Let also P (r, x 1 ) = (r, v 1 , . . . , v m-1 , v m =: x 1 ). Notice that r may coincide with y 1 and x 1 may coincide with v 1 . Since v 1 , r ∈ I(r, u), applying the quadrangle condition we will find a vertex

v 1 ∼ v 1 , r at distance d G (r, u) -2 from u. Since r / ∈ I(r, x 1 ), v 1 = v 2 . Since v 2 , v 1 ∈ I(v 1 , u), by quadrangle condition we will find v 2 ∼ v 2 , v 1 at distance d G (r, u) -3 from u. Again, since r / ∈ I(r, x 1 ), v 2 = v 3 .
Continuing this way, we will find the vertices r , v 1 , v 2 , . . . , v m-1 , v m =: x 1 forming an (r , x 1 )-path P (r , x 1 ) and such that v i ∼ v i , v i-1 , v i = v i+1 , and v i is one step closer to u than v i and v i-1 (see Figure 3, right). From its construction, the path P (r , x 1 ) is a shortest path. We assert that P (r , x 1 ) is gated. If this is not the case, by Lemma 2 and since P (r , x 1 ) is shortest, we can find two vertices v i-1 , v i+1 having a common neighbor z different from v i . Let z be the median of the triplet z , v i-1 , v i+1 . Then z is a common neighbor of z , v i-1 , v i+1 and z is different from v i (otherwise, we obtain a forbidden K 2,3 ). But then one can easily check that the

vertices v i-1 , v i , v i+1 , v i-1 , v i , v i+1 , z, z induce in G an isometric 3-cube, contrary to the assumption that G is cube-free. Consequently, P (r , x 1 ) is a gated path of G.
Let T be the tree rooted at r and consisting of the gated path P (r , x 1 ) and the gated subpaths of P (r, x 2 ) and P (r, x 3 ) between r and x 2 , x 3 , respectively. Clearly, T is a rooted tree with gated branches. Notice that x 1 , x 2 , x 3 ∈ Υ(u, T ). Indeed, if x 2 or x 3 belonged to I(x 1 , u), then x 1 would belong to I(x 1 , u) and we would conclude that x 2 or x 3 belongs to I(x 1 , u), which is impossible because x 1 ∈ Υ(u, T ). On the other hand, x 1 cannot belong to I(x 2 , u) or to

I(x 3 , u) because d G (x 1 , u) = d G (x 1 , u) -1 ≤ d G (x 2 , u) = d G (x 3 , u). Consequently, |Υ(u, T )| ≥ 3.
Since T contains less vertices than T , we obtain a contradiction with the minimality choice of T . This concludes the analysis of Case 2, thus T is quasigated. Applying Lemmas 11 and 12 to the cube-free median subgraph of G induced by the fiber F (x), we immediately obtain: Corollary 5. The total boundary ∂ * F (x) of any fiber F (x) is quasigated.

y x 1 x 2 x 3 r u y x 1 x 3 r u k k k x 2 x 1,2 x 1,3 x 2,3 w z r r v 1 v 1 v 2 v 2 x 1 x 1 u x 2 y x 3 v i v i v i-1 v i-1 v i+1 v i+1

5.3.

Classification of pairs of vertices. In Section 5.1 we classified the fibers of St(z) into panels and cones. Now, we use this classification to provide a classification of pairs of vertices of G with respect to the partition into fibers, which extends the one done in [START_REF] Chepoi | Distance and routing labeling schemes for non-positively curved plane graphs[END_REF] for planar median graphs.

Let z be an arbitrary fixed vertex of a cube-free median graph

G = (V, E). Let F z = {F (x) : x ∈ St(z)} denote the partition of V into the fibers of St(z).
Let u, v be two arbitrary vertices of G and suppose that u belongs to the fiber F (x) and v belongs to the fiber F (y) of F z . We say that u and v are roommates if they belong to the same fiber, i.e., x = y. We say that u and v are 1-neighboring if F (x) and F (y) are two neighboring fibers (then one of them is a panel and another is a cone). We say that u and v are 2-neighboring if F (x) and F (y) are distinct cones neighboring with a common panel, i.e., there exists a panel F (w) ∼ F (x), F (y). Finally, we say that u and v are separated if the fibers F (x) and F (y) are distinct, are not neighboring, and if both F (x) and F (y) are cones, then they are not 2-neighboring. For an illustration, see Figure 2. From the definition it easily follows that any two vertices u, v of G are either roommates, or separated, or 1-neighboring, or 2-neighboring. Notice also the following transitivity property of this classification: if u belongs to the same fiber F (x) as u and v belongs to the same fiber F (y) as v, then u , v are classified in the same category as u, v.

We continue with distance formulae for separated, 2-neighboring, and 1-neighboring vertices. The illustration of each of the formulae is provided in Figure 4.

Lemma 13. For vertices u and v belonging to the fibers F (x) and F (y) of St(z), respectively, the following conditions are equivalent:

(i) u and v are separated;

(ii) I(x, z) ∩ I(y, z) = {z};

(iii) d G (u, v) = d G (u, z) + d G (z, v), i.e., z ∈ I(u, v).
Proof. (ii)⇐⇒(iii): First, suppose that I(x, z) ∩ I(y, z) = {z}. To show that z ∈ I(u, v) it suffices to prove that z is the median of u, v, z. Suppose by way of contradiction that the median of u, v, z is the vertex w = z. Let s be a neighbor of z in I(z, w). Then obviously s ∈ St(z). Since I(x, z) ∩ I(y, z) = {z}, s does not belong to at least one of the intervals I(x, z) and I(y, z), say s / ∈ I(x, z). This implies that d G (s, x) = d G (z, x) + 1. Since x is the gate of u in St(z) and s ∈ St(z), necessarily x ∈ I(u, s). This implies that there is a shortest (s, u)-path passing via z and x, i.e., d G (s, u) = 1 + d G (z, u). On the other hand, since s ∈ I(z, w) ⊂ I(z, u), we conclude that d G (z, u) = 1 + d G (s, u). Comparing the two equalities, we obtain a contradiction.

Conversely, suppose that z ∈ I(u, v). This implies that z is the median of the triplet u, v, z and that I(u, z) ∩ I(v, z) = {z}. Since x is the gate of u and y is the gate of v in St(z), we conclude that x ∈ I(u, z) and y ∈ I(v, z). Consequently, I(x, z) ⊆ I(u, z) and I(y, z) ⊆ I(v, z), proving that I(x, z) ∩ I(y, z) = {z}. This establishes (iii)=⇒(ii).

Remark 5.1. The equivalence (ii)⇐⇒(iii) of Lemma 13 holds for all median graphs. Lemma 14. Let u and v be two 1-neighboring vertices such that u belongs to the panel F (x) and v belongs to the cone F (y). Let u 1 and u 2 be the two imprints of u on the total boundary ∂ * F (x) (it may happen that u 1 = u 2 ) and let v + be the gate of v in F (x). Then

d G (u, v) = min{d G (u, u 1 ) + d ∂ * F (x) (u 1 , v + ), d G (u, u 2 ) + d ∂ * F (x) (u 2 , v + )} + d G (v + , v).
Proof. By Lemma 6 F (x) is gated. Hence there must exist a shortest (u, v)-path passing via v + . The vertices u 1 , u 2 , and v + belong to the total boundary ∂ * F (x) of F (x). Since, by Lemma 9, ∂ * F (x) is an isometric tree and since, by Lemma 12, u has at most two imprints u 1 and u 2 in

∂ * F (x), we conclude that d G (u, v + ) = min{d G (u, u 1 ) + d ∂ * F (x) (u 1 , v + ), d G (u, u 2 ) + d ∂ * F (x) (u 2 , v + )}.
Consequently, there is a shortest (u, v)-path passing first via one of the vertices u 1 , u 2 and then via v + , establishing the asserted property.

Lemma 15. Let u and v be two 2-neighboring vertices belonging to the cones F (x) and F (y), respectively, and let F (w) be the panel neighboring F (x) and F (y). Let u + and v + be the gates of u and v in F (w).

Then d G (u, v) = d G (u, u + ) + d ∂ * F (w) (u + , v + ) + d G (v + , v).
Proof. Since the halfspace W (w, z) is convex and u, v ∈ F (x)∪F (w)∪F (y) ⊂ W (w, z), any shortest (u, v)-path P (u, v) is contained in W (w, z). We assert that P (u, v) ⊂ F (x) ∪ F (w) ∪ F (y). Indeed, since u ∈ F (x), v ∈ F (y) and the fibers F (x), F (y) are not neighboring, while moving from u to v along P (u, v), we have to leave F (x) and enter a panel neighboring F (x). But the cone F (x) has only two neighboring panels: F (w) and a panel F (w ) ⊂ W (z, w). Since P (u, v) ⊂ W (w, z), necessarily P (u, v) must enter F (w) (and not F (w )). Analogously, one can show that while moving from v to u along P (u, v) when we leave F (y) we must enter the same panel F (w). Consequently, since the fibers F (x), F (w), and F (y) are gated, the path P (u, v) must be included in their union.

Next we show that u + and v + belong to a common shortest (u, v)-path. Indeed, by what has been shown above, any shortest (u, v)-path intersects F (w), in particular, there exists a vertex s ∈ I(u, v) ∩ F (w). Since u + is the gate of u in F (w) and v + is the gate of v in F (w), we deduce that u + ∈ I(u, s) and v + ∈ I(v, s). Since s ∈ I(u, v), there exists a shortest path from u to v passing via u + , s, and v + . This shows that d

G (u, v) = d G (u, u + ) + d G (u + , v + ) + d G (v + , v). Since ∂ * F (w) is an isometric tree, d G (u + , v + ) = d ∂ * F (w) (u + , v + ), establishing the required equality d G (u, v) = d G (u, u + ) + d ∂ * F (w) (u + , v + ) + d G (v + , v).

Distance labeling scheme for cube-free median graphs

Let G = (V, E) be a cube-free median graph with n vertices and let c be a centroid of G. Let u, v be any pair of vertices of G for which we have to compute the distance d G (u, v). Applying Lemmas separated vertices 1-neighboring vertices

u v x y z F (x) F (y) u u 1 u 2 v + v z x y F (x) F (y) 2-neighboring vertices z u u + v + v y w x F (x) F (y) F (w) W (w, z)
* F (x) (u 1 , v + ), d ∂ * F (x) (u 2 , v + ), d ∂ * F (w) (u + , v + ).
Since the total boundaries are isometric trees, this can be done by keeping in the label of u the labels of u 1 , u 2 , and u + in a distance labeling scheme for a tree (as well as keeping in the label of v such a label of v + ). This shows that d G (u, v) can be computed in all cases except when u and v are roommates, i.e., they belong to a common fiber F (x) of St(c). Since F (x) is gated and thus median, we can apply the same recursive procedure to each fiber F (x) instead of G. Therefore, d G (u, v) is computed in the first recursive call when u and v will no longer belong to the same fiber of the current centroid. Since at each step the division into fibers is performed with respect to a centroid, |F (x)| ≤ n/2 by Lemma 10, thus the tree of recursive calls has logarithmic depth.

In this section, we present the formal description of the distance labeling scheme. The encoding scheme is described by the algorithm Distance_Encoding presented in Section 6.2. Section 6.3 presents the algorithm Distance used for answering distance queries. In Section 6.1 we formally present the distance labeling schemes for trees and stars. 6.1. Distance and routing labelings for trees and stars. We present the distance labeling scheme (Dist_Enc_Tree, Dist_Tree) for trees, which we briefly described in Section 2.2. The procedure Dist_Enc_Tree that gives a label LD T (v) to every vertex v of a tree T works as follows:

(1) Give to every vertex v a unique identifier id(v);

(2) Find a centroid c of T ;

(3) For every vertex v of T , concatenate (id(c), d T (v, c)) to the current label of v;

(4) Repeat Step 2 for each subtree with at least two vertices, created by the removal of c. Given two labels LD T (u) and LD T (v), the procedure Dist_Tree can find the last common separator c of u and v (i.e., the common centroid stored latest in their labels) and return d T (u, c) + d T (v, c) as the distance d T (u, v). The encoding Rout_Enc_Tree for routing in trees is similar, just replace (id(c), d T (u, c)) at step (3) by (id(c), port(u, c), port(c, u)). Then, the decoding function Rout_Tree(u,v), returns port(u, c) (stored in the label of u) if c = u, or port(c, v) (stored in the label of v) otherwise (where c is again the last common separator of u and v).

We present the distance labeling scheme for stars St(z) of any median graph G. It is based on the fact that median graphs are isometrically embeddable into hypercubes and that St(z) is gated, and thus is an isometric median subgraph of G. So, we can suppose that St(z) is isometrically embedded into a hypercube. Let ϕ : St(z) → Q d be such an isometric embedding so that ϕ(z) = ∅. Consequently, for each vertex x of St(z), ϕ(x) is a set of cardinality equal to the dimension of the cube I(x, z), thus ϕ(x) has size at most log 2 n, where n = | St(z)|. For any two vertices, x and y of

St(z), d St(z) (x, y) = |ϕ(x)∆ϕ(y)| := |(ϕ(x) ∪ ϕ(y)) \ (ϕ(x) ∩ ϕ(y))|.
Using the isometric embedding ϕ, we can describe a simple encoding Enc_Star(St(z)) of the vertices of St(z) which can be used to answer distance and routing queries. For a vertex x ∈ St(z), let L St(z) (x) = ϕ(x). Then Enc_Star(St(z)) gives to z the label ∅ and to every neighbor of z a unique label in {1, . . . , deg(z)}. For any vertex x at distance k from z, I(x, z) contains exactly k neighbors of z and the labels of these neighbors completely define ϕ(x) and L St(z) (x).

Giving unique labels to the neighbors of z require log 2 (deg(z)) bits and thus, in the worst case, Enc_Star(St(z)) gives labels of length O(deg(z) log(deg(z))). If the dimension of St(z) is a fixed constant, then Enc_Star(St(z)) gives labels of logarithmic length. For a vertex x of St(z) labeled by the set X := ϕ(x), the vertex of St(z) labeled by the value min{i : i ∈ X} is called the 1st of x, and the one labeled by max{i : i ∈ X} is called the 2nd of x.

For simplicity, we assume that for a vertex x labeled X and a vertex x labeled X = X \ {i}, i ∈ X, we have port(x, x ) = port(x , x) = i. Since ϕ is an isometric embedding, it is easy to see that for any two vertices x and y encoded by the sets X := L St(z) (x) = ϕ(x) and Y := L St(z) (y) = ϕ(y), the distance d St(z) (x, y) between x and y is |X Y |. This is exactly the value returned by Dist_Star(X, Y ). Routing decisions follow from the same property. Assume that |X| ≤ |Y |. If X ⊆ Y , Rout_Star(X,Y ) returns the port to any vertex labeled by X ∪ {i} with i ∈ Y \ X (say the minimal i). If X ⊂ Y , then Rout_Star(X,Y ) returns the port of any vertex labeled by X \ {i} for i ∈ X \ Y (say the minimal i).

LD 0 (u) LD 2nd[gate LDT] i (u) LD 1st[gate LDT] i (u) LD St[gate] i (u) LD St[Dist] i (u) LD 1st[Dist] i (u) LD 2nd[Dist] i (u) LD St[Cent] i (u)
Figure 5. Illustration of LD 0 (u) and of the information added to LD(u) at step i.

6.2.

Encoding. Let G = (V, E) be a cube-free median graph with n vertices. We describe now how Distance_Encoding constructs for every vertex u of G a distance label LD(u). This is done recursively and every depth of the recursion will be called a step. Initially, we suppose that every vertex u of G is given a unique identifier id(u). We define this naming step as Step 0 )) contains the necessary information relative to St(c) and is thus referred as the part "star" of the information LD 1 (u) given to u at Step 1. We denote this part by LD St 1 (u). We also set LD

St[Cent] 1 (u) := id(c), LD St[Dist] 1 (u) := d G (u, c) and LD St[gate] 1 (u) := L St(c) (u ↓ )
for the three components of the label LD St 1 (u).

Algorithm 1: Distance_Encoding(G, LD(V )) Input: A cube-free median graph G = (V, E) and a labeling LD(V ), initially consisting of a unique identifier id(u) for every u ∈

V 1 if V = {v} then stop; 2 Find a centroid c of G ; 3 Compute the partition F c of G into fibers ; 4 For each fiber F (x) of F c compute its total boundary ∂ * F (x) ; 5 L St(c) (St(c)) ← Enc_Star(St(c)) ; 6 foreach panel F (x) ∈ F c do 7 LD ∂ * F (x) (∂ * F (x)) ← Dist_Enc_Tree(∂ * F (x));
(d, d 1 , d 2 ) ← (d G (u, c), d G (u, u + 1 ), d G (u, u + 2 )) ; 22 L St ← (id(c), d, L St(c) (u ↓ )) ; 23 L 1st ← (LD ∂ * F (w1) (u + 1 ), d 1 ) ; 24 L 2nd ← (LD ∂ * F (w2) (u + 2 ), d 2 ) ; 25 LD(u) ← LD(u) • (L St , L 1st , L 2nd ) ; 26
Distance_Encoding(F (x), LD(V )).

Afterwards, at

Step 1, the algorithm considers each fiber F (x) of F c . If F (x) is a panel, then the algorithm computes the total boundary ∂ * F (x) of F (x), which is an isometric quasigated tree. The vertices v of this tree ∂ * F (x) are given special identifiers LD ∂ * F (x) (v) of size O(log 2 |V |) consisting of a distance labeling scheme for trees described in Section 6.1. For each vertex u of the panel F (x), the algorithm computes the two imprints u 1 and u 2 of u in ∂ * F (x) (it may happen that u 1 = u 2 ) and stores (LD

∂ * F (x) (u 1 ), d G (u, u 1 )) and (LD ∂ * F (x) (u 2 ), d G (u, u 2 )) in LD 1st
1 (u) and LD 2nd 1 (u).

If F (x) is a cone and F (w 1 ), F (w 2 ) are the two panels neighboring F (x), then for each vertex u of F (x), the algorithm computes the gates u + 1 and u + 2 of u in F (w 1 ) and F (w 2 ). Since

u + i ∈ ∂ x F (w i ) ⊂ ∂ * F (x), i = 1, 2, the labels LD ∂ * F (w 1 ) (u + 1 ) and LD ∂ * F (w 2 ) (u + 2 )
in the distance labelings of trees ∂ * F (w 1 ) and ∂ * F (w 2 ) are well-defined. Thus the algorithm stores

(LD ∂ * F (w 1 ) (u + 1 ), d G (u, u + 1 )) and (LD ∂ * F (w 2 ) (u + 2 ), d G (u, u + 2 )
) in LD 1st 1 (u) and LD 2nd 1 (u). This ends Step 1. Since F c partitions V into gated median subgraphs, the label LD 2 (u) added to LD(u) at Step 2 is obtained as LD 1 (u), where G is replaced by the fiber F (u ↓ ) containing u, and so on. Since each fiber contains no more than half of the vertices of the current graph, at Step log 2 |V | , each fiber consists of a single vertex, and the algorithm stops. Therefore, for each pair of vertices u and v of G, there exists a step of the recursion after which u and v are no longer roommates. For an illustration of the parts of LD i (u), see Fig. 5. For a vector L(v) := (t 1 , . . . , t k ) of vectors t 1 , . . . , t k and an arbitrary vector t, we denote by L(v) • t := (t 1 , . . . , t k , t) the concatenation of L(v) and t.

6.3. Distance queries. Let u and v be two vertices of a cube-free median graph G = (V, E) and let LD(u) and LD(v) be their labels returned by Distance_Encoding. Here we describe how the algorithm Distance can compute the information about the relative positions of u and v with respect to each other and how, using it, to compute the distance d G (u, v).

We continue with the formal description of the algorithm Distance.

The functions Distance_1-Neighboring, Distance_2-Neighboring, and Distance_Separated, used in this algorithm, are given below (the function Dist_Star is described in Section 6.1).

Given the vertices u and v, first the algorithm detects if u and v coincide. This is done in line 1 of Distance. If u = v, then Distance finds the largest integer i such that LD

St[Cent] i (u) = LD St[Cent] i (v) (line 2)
. This corresponds to the first time u and v belong to different fibers in a partition. Let c be a centroid vertex of the current graph. In lines 3,4,5, the algorithm Distance retrieves the distances d, d u , and d v between the gates u ↓ and v ↓ of u and v in the star St(c), and the distances from u ↓ and v ↓ to c, respectively. This is done by using the identifiers LD (v) and the distance decoder for distance labeling in stars. With this information at hand, one can easily decide for each of u and v if it belongs to a cone or to a panel, and, moreover, to decide if the vertices u and v are 1-neighboring, 2-neighboring, or separated. In each of these cases, a call to an appropriate function is done in lines 6-9.

Algorithm 2: Distance(LD(u), LD(v))

Input: The labels LD(u) and LD(v) of two vertices u and v of G Output: The distance between u and v in G

1 if LD 0 (u) = LD 0 (v) /* u = v */ then return 0 ;
2 Let i be the largest integer such that LD

St[Cent] i (u) = LD St[Cent] i (v) ; 3 d ← Dist_Star(LD St[gate] i (u), LD St[gate] i (v)) ; // d G (u ↓ , v ↓ ) 4 d u ← Dist_Star(LD St[gate] i (u), 0) ; // d G (u ↓ , c) 5 d v ← Dist_Star(LD St[gate] i (v), 0) ; // d G (v ↓ , c) 6 if d = 1 and d u = 1 then return Distance_1-Neighboring (LD i (u), LD i (v)) ; 7 if d = 1 and d v = 1 then return Distance_1-Neighboring (LD i (v), LD i (u)) ; 8 if d = 2 and d u = d v = 2 then return Distance_2-Neighboring (LD i (u), LD i (v)) ; 9 return Distance_Separated (LD i (u), LD i (v)).
First suppose that the vertices u and v are 1-neighboring (d = 1 and one of d u , d v is 1 and another is 2), i.e., one of the vertices u, v belongs to a cone and another one belongs to a panel, and the cone and the panel are neighboring. The function Distance_1-Neighboring returns the distance d G (u, v) in the assumption that u belongs to a panel and v belongs to a cone (if v belongs to a panel and u to a cone, it suffices to swap the names of the vertices u and v before using Distance_1-Neighboring). The function finds the gate v + of v in the panel of u by looking at LD St[gate] i (v) (it also retrieves the distance d G (v, v + )). It then retrieves the imprint u * of u (and the distance d G (u, u * )) on the total boundary of the panel that minimizes the distance of u to one of the two imprints plus the distance from this imprint to the gate v + using their tree distance labeling scheme. Finally, Distance_1-Neighboring

returns d G (u, u * ) + d G (u * , v + ) + d G (v + , v) as d G (v, u). function Distance_1-Neighboring(LD i (u), LD i (v)): dir ← 1st ; // If LD St[gate] i (u) = max{i : i ∈ LD St[gate] i (v)} if LD St[gate] i (u) = min{i : i ∈ LD St[gate] i (v)} then dir ← 2nd ; d 1 ← Dist_Tree(LD dir[gate_LDT] i (v), LD 1st[imp_LDT] i (u)) ;
// The distance from the gate to the first imprint

d 2 ← Dist_Tree(LD dir[gate_LDT] i (v), LD 2nd[imp_LDT] i (u)) ;
// The distance from the gate to the second imprint

return LD dir[Dist] i (v) + min d 1 + LD 1st[Dist] i (u), d 2 + LD 2nd[Dist] i (u) .
G (u, u + ) + d G (u + , v + ) + d G (v + , v) as d G (u, v). function Distance_2-Neighboring(LD i (u), LD i (v)): foreach x ∈ {u, v} do dir x ← 1st ; // The common panel is the 1st of the cone of x if LD St[gate] i (u) ∩ LD St[gate] i (v) = min{i : i ∈ LD St[gate] i (x)} then dir x ← 2nd ;
// The common panel is the 2nd of the cone of x d ← Dist_Tree(LD

diru[gate_LDT] i (u), LD dirv[gate_LDT] i (v)) ; return LD diru[Dist] i (u) + LD dirv[Dist] i (v) + d.
In the remaining cases, the vertices u and v are separated. By Lemma 13, there exists a shortest path between u and v passing via c. Both u and v have stored the centroid c and their distances to c. Therefore, Distance_Separated simply returns the sum of those two distances.

function Distance_Separated(LD i (u), LD i (v)): return LD St[Dist] i (u) + LD St[Dist] i (v).
6.4. The efficient implementation of Distance_Encoding. In this subsection we show how to implement a single run of the algorithm Distance_Encoding on an n-vertex cube-free median graph G in O(n) time. Since the algorithm is recursively called to the fibers F (x), x ∈ St(c) and these fibers have size at most n 2 and are cube-free median graphs, the total complexity of Distance_Encoding is O(n log 2 n). The main difficulty with this is that we have to compute centroids, fibers, gates, and imprints without knowing the distance matrix of G (with the distance matrix at hand, Distance_Encoding can be easily implemented in O(n 2 log n) time). 6.4.1. Computation of a centroid c. We compute a centroid c of G using a recent linear-time algorithm of [START_REF] Bénéteau | Medians in median graphs and their cube complexes in linear time[END_REF] for computing centroids/medians of arbitrary median graphs. For a median graph with m edges this algorithm has complexity O(m). By Corollary 1, G contains at most 2n edges, thus a centroid c of G can be computed in O(n) time. 6.4.2. Partition of a median graph into fibers. We describe how to partition in O(m) time any median graph G with m edges into fibers with respect to any gated subgraph H of G. For this, we adapt the classical Breadth-First-Search.

Recall that the Breadth-First Search (BFS) [START_REF] Cormen | Introduction to Algorithms[END_REF]Chapter 22] rooted at vertex v 0 uses a queue Q. For each vertex v of G, two variables d(v) and f (v) are computed. Initially, v 0 is inserted in Q, d(v 0 ) is set to 0, and f (v 0 ) is set to null. When a vertex u arrives at the head of Q, it is removed from Q and all the not yet discovered neighbors v of u are inserted in Q; u becomes the parent f (v) of v and d(v) is set to d(u) + 1. The edges f (v)v define the BFS-tree T (v 0 ) of G. The main property of BFS is that d(v) is the distance d G (v, v 0 ) and that f (v) belongs to a shortest (v, v 0 )-path.

First, given any subgraph H of any connected graph G, we adapt the classical BFS to compute, for each vertex v of G, a closest to v vertex of H, i.e., a vertex of

H realizing the distance d G (v, H) := min{d G (v, x) : x ∈ V (H)}.
For each vertex v of G, the algorithm computes the variables proj(v), d(v), and f (v). The vertices of H are first inserted in the queue Q and, for each x ∈ V (H), we set proj(x) := x, d(x) := 0, and f (x) is set to null. When a vertex u of G arrives at the head of Q, it is removed from Q and all not yet discovered neighbors v of u are inserted in Q; u becomes the parent f (v) of v, d(v) is set to d(u) + 1, and proj(v) is set to proj(u). We call this algorithm a BFS traversal of G with respect to H. Clearly, the algorithm has linear-time complexity O(m). Its correctness follows from the following lemma: Lemma 16. For any graph G, any subgraph H of G, and any vertex

v of G, proj(v) is a closest to v vertex of H and d(v) = d G (v, proj(v)) = d G (v, H).
Proof. The proof is inspired by the correctness proof of BFS; see, for example, the proof of [START_REF] Cormen | Introduction to Algorithms[END_REF]Theorem 22.5]. First, by induction on d(v) one can easily show that

d(v) ≥ d G (v, proj(v)). Indeed, let u = f (v) and x = proj(u) = proj(v). By induction assumption, d(u) ≥ d G (u, x). Since d(v) = d(u)+1 and d G (v, x) ≤ d G (u, x)+1, we deduce that d(v) = d(u)+1 ≥ d G (u, x)+1 ≥ d G (v, x).
Second, as in case of classical BFS, one can prove that at each execution of the algorithm, if the queue Q consists of the vertices

v 1 , v 2 , . . . , v k , then d(v 1 ) ≤ d(v 2 ) ≤ • • • ≤ d(v r ) and d(v r ) ≤ d(v 1 )+1
hold. Indeed, it can be easily seen that this invariant is preserved when a vertex is removed at the head of Q or is inserted at the end of Q.

Using these two properties, by induction on k := d G (v, H) we will show that proj(v) is a closest to v vertex of H and that d(v) = d G (v, proj(v)). Suppose by way of contradiction that d(v) > k, thus there exists a vertex y

= x of H such that d G (v, y) = k. Let u = f (v). Let also w be a neighbor of v in I(v, y). Since d G (w, H) = d G (w, y) = k -1, by induction hypothesis proj(w) = y and d(w) = d G (w, proj(w)) = d G (w, y) ≤ k -1.
Consider the moment when the vertex w is removed from the queue Q. If v is not yet in Q, since v ∼ w, the algorithm will pick w as the parent of v and y = proj(w) as proj(v). This contradicts the assumption that u = f (v) and proj(v) = x = y. On the other hand, if v is present in Q or if v has been already removed from Q, then necessarily u = f (v) was inserted in Q before w and from the invariant of the queue Q, we conclude that

d(u) ≤ d(w) ≤ k -1. Therefore d(v) = d(u) + 1 = k, contrary to the assumption d(v) > k. Hence d(v) = k = d G (v, H). Since d(v) is the length of a path between proj(v) and v, we conclude that d(v) = d G (v, proj(v)) = d G (v, H).
We apply the previous algorithm to a gated subgraph H of a median graph G. For a vertex v of G we use the same variables d(v) and f (v), but instead of proj(v) we use the variable fib(v) which is updated in the same way as proj(v). To compute the fibers {F (x) : x ∈ V (H)}, for each vertex x ∈ V (H), we construct a BFS-tree T (x) rooted at x and consisting of all vertices v such that fib(v) = x and of the edges of the form vf (v). Corollary 6. For any median graph G, any gated subgraph H of G, and any vertex v of G, fib(v) is the gate of v in H and d(v) = d G (v, fib(v)). For each vertex x ∈ V (H), the vertex-sets of the tree T (x) and of the fiber F (x) coincide.

Proof. The first assertion follows from Lemma 16. The equality of vertex-sets of T (x) and F (x) immediately follows from the definition of fibers and the first assertion. By Corollary 6, each T (x) is a spanning tree of F (x), whence the vertex-set of each fiber F (x) is computed. To compute the edge-set of each F (x), we traverse the edges of G and each edge uv such that d(u) < d(v) and fib(u) = fib(v) =: x is inserted in the fiber F (x). If we traverse the edges in a BFS-order with respect to H, then we will get the adjacency lists of the vertices from each fiber. The edges of G not included in the fibers are the edges running between neighboring fibers. Therefore, if uv is an edge such that x := fib(u) = fib(v) =: y, then u is inserted in ∂ y F (x) (the boundary of F (x) relative to F (y)) and v is inserted in ∂ x F (y) (the boundary of F (y) relative to F (x)). For the computation of gates, it will be useful that for vertex u in ∂ y F (x) we keep its neighbor v ∈ ∂ x F (y) and for v ∈ ∂ x F (y) we keep its neighbor u ∈ ∂ y F (x); for this we set neighbor x,y (u) = v and neighbor y,x (v) = u. Additionally, u is inserted in the total boundary ∂ * F (x) and v is inserted in the total boundary ∂ * F (y). This way, we constructed the vertex-sets of relative boundaries and of total boundaries of all fibers. Consequently, for each vertex x of H and each vertex v of F (x) (i.e., such that fib(v) = x) we can set tbd(v) = 1 if v ∈ ∂ * F (x) and tbd(v) = 0 otherwise. Notice that each vertex v ∈ ∂ * F (x) may be included in several relative boundaries ∂ y F (x). Since each such inclusion corresponds to an edge incident to v, the total size of all relative boundaries is at most twice the number of edges of G, i.e., O(m). The same conclusion holds about the total size of the lists neighbor x,y over all x, y ∈ V (H), x ∼ y. Finally, to compute the edge-sets of all total boundaries ∂ * F (x), x ∈ V (H), we traverse again all edges of G and we insert a current edge uv in the total boundary ∂ * F (x) if and only if x = fib(u) = fib(v) and tbd(u) = tbd(v) = 1. Consequently, we obtain the following result: Lemma 17. Given a median graph G with m edges and a gated subgraph H of G, the following entities can be computed in total linear time O(m) (O(n) time if G is cube-free):

• the vertex-sets and the edge-sets of all fibers F (x), x ∈ V (H);

• the vertex-sets and the-edge sets of all total boundaries ∂ * F (x), x ∈ V (H);

• the vertex-sets of all relative boundaries ∂ y F (x) and the lists neighbor x,y for all x, y ∈ V (H) with x ∼ y.

6.4.3.

Computation of gates to neighboring panels. Computation of gates is used in lines 9, 18, and 20 of Distance_Encoding. In lines 9 and 18, the gates of all vertices v in the star St(c) are computed. This can be done by running a BFS traversal of G with respect to the gated set St(c). By Corollary 6, fib(v) is the gate of any vertex v of G in St(v). Therefore, the lines 9 and 18 can be executed in O(n) time.

In line 20, for each vertex u belonging to a cone F (x) we have to compute the gates u + 1 and u + 2 of u in the two neighboring panels F (w 1 ) and F (w 2 ). Notice that u + 1 belongs to the relative boundary ∂ x F (w 1 ) and u + 2 belongs to the relative boundary ∂ x F (w 2 ). Consider the relative boundaries ∂ w 1 F (x) and ∂ w 2 F (x). They are gated subgraphs of F (x). We run two BFS traversals of F (x), one with respect to ∂ w 1 F (x) and the second one with respect to ∂ w 2 F (x). For a vertex u ∈ F (x), let gate 1 (u) and gate 2 (u) be the two gates of u in ∂ w 1 F (x) and in ∂ w 2 F (x), respectively, returned by the algorithms (in view of Lemma 6). Then we can set u + 1 to be the vertex neighbor w 1 ,x (gate 1 (u)) (which is the neighbor of gate 1 (u) in ∂ x F (w 1 )) and u + 2 to be the vertex neighbor w 2 ,x (gate 2 (u)) (which is the neighbor of gate 2 (u) in ∂ x F (w 2 )). Since gate 1 (u) and gate 2 (u) are the gates of u in ∂ w 1 F (x) and in ∂ w 2 F (x), u + 1 and u + 2 are the gates of u in ∂ x F (w 1 ) and ∂ x F (w 2 ), respectively. If the cone F (x) has n i vertices, then the computation of the gates u + 1 and u + 2 of all the vertices u ∈ F (x) will take O(n i ) time. Since the cones of G are pairwise disjoint, this computation takes total O(n) time. Consequently, we obtain: Lemma 18. Given a cube-free median graph G with n vertices, the following entities can be computed in total linear time O(n):

• the gates of all vertices v of G in the star St(c);

• the gates of all vertices v belonging to the cones of G in the two neighboring panels. Remark 6.1. For a median graph G with m edges and a gated subgraph H of G, the same algorithm computes in O(m) time the gates of the vertices of G in all the boundaries of their fibers. 6.4.4. Computation of imprints. In line 10 of Distance_Encoding, for each vertex u of a panel F (x) we have to compute the two imprints u 1 and u 2 of u on the total boundary ∂ * F (x). This computation is based on the following properties of imprints.

Lemma 19. The imprints u 1 , u 2 of u ∈ F (x) on ∂ * F (x) satisfy the following properties:

(a) there exist y 1 , y 2 ∈ St(c), y 1 = y 2 , and

x ∼ y 1 , y 2 such that u 1 is a gate of u in ∂ y 1 F (x) and u 2 is the gate of u in ∂ y 2 F (x); (b) u 1 , u 2 ∈ I(u, x); (c) if w is a neighbor of u in I(u, u i ), i ∈ {1, 2}, then u i is an imprint of w.
Proof. By Lemma 11, ∂ * F (x) is an isometric tree with gated branches. Recall also that ∂ * F (x) is the union of all relative boundaries ∂ y F (x), y ∼ x, which are all gated trees. Therefore, by the definition of imprints, u 1 and u 2 are the gates of u in all the relative boundaries to which they belong. This implies that u 1 and u 2 cannot belong to a common relative boundary, establishing (a). Since x belongs to every relative boundary, this also implies that u 1 , u 2 ∈ I(u, x), establishing (b). It remains to show property (c). If we suppose that u 1 is not an imprint of w, then from imprint's definition there exists z ∈ ∂ * F (x), z = u 1 such that z ∈ I(w, u 1 ). Since w ∈ I(u, u 1 ), we deduce that z ∈ I(w, u 1 ) ⊂ I(u, u 1 ) contrary to the assumption that u 1 is an imprint of u. Lemma 20. If uv is an edge of F (x), then either their imprints coincide, i.e., {u 1 , u 2 } = {v 1 , v 2 }, or one of the vertices of the pair {u 1 , u 2 } coincides with one of the vertices of the pair {v 1 , v 2 } and the two other vertices from each pair are adjacent.

Proof. We will use the following general assertion:

)+d G (b , a ) = d G (b, a ) ≤ d G (a, a ) + 1 ≤ d G (b, b ) + 1. This implies that d G (b , a ) ≤ 1. If a ∼ b , from previous inequalities we deduce that d G (a, a ) = d G (b, b ). If a = b , since G is bipartite and d G (a, a ) ≤ d G (b, b ), we must have d G (b, b ) = d G (a, a ) + 1.
To prove the lemma, suppose that

d G (v, v 1 ) is the smallest distance among {d G (u, u 1 ), d G (u, u 2 ), d G (v, v 1 ), d G (v, v 2 )}.
From imprint's definition it follows that one of the vertices u 1 , u 2 , say u 1 , belongs to I(u, v 1 ). By Claim 6.2 we conclude that either

u 1 ∼ v 1 and d G (u, u 1 ) = d G (v, v 1 ) or u 1 = v 1 and d G (u, u 1 ) = d G (v, v 1 ) + 1. Case 1. u 1 = v 1 and d G (u, u 1 ) = d G (v, v 1 ) + 1. Suppose without loss of generality that d G (v, v 2 ) ≤ d G (u, u 2 ) (the other case is similar). From imprint's definition it follows that one of the vertices u 1 , u 2 belongs to I(u, v 2 ). Since v 1 = u 1 is an imprint of v, this cannot be u 1 . Thus u 2 ∈ I(u, v 2 ). By Claim 6.2, either u 2 = v 2 or u 2 ∼ v 2 and d G (u, u 2 ) = d G (v, v 2 ), and we are done. Case 2. u 1 ∼ v 1 and d G (u, u 1 ) = d G (v, v 1 ). Suppose without loss of generality that d G (v, v 2 ) ≤ d G (u, u 2 )
. From imprint's definition it follows that one of the vertices u 1 , u 2 , belongs to I(u, v 2 ). First suppose that u 1 ∈ I(u, v 2 ). We assert that in this case v 1 belongs to I(v, v 2 ) contrary to the assumption that v 2 is an imprint of v. Indeed, since G is bipartite and

u ∼ v, either u ∈ I(v, v 2 ) or v ∈ I(u, v 2 ). If u ∈ I(v, v 2 ), then u 1 ∈ I(u, v 2 ) and v 1 ∈ I(v, u 1 ) imply that v 1 ∈ I(v, v 2 ). Otherwise, if v ∈ I(u, v 2 ), since v, u 1 ∈ I(u, v 2 ) and
Proof. Since we assume that v is the parent f (u) of u in the BFS with respect to ∂ * F (x), we have v 1 = u 1 =: z. In the proof we will use Lemma 20 and the fact that if the two imprints of a vertex of F (x) are different, then they cannot be adjacent (this easily follows from imprint's definition). Case 1. There exists i ∈ {1, 2} such that w i = z.

By Lemma 20, the second imprint u 2 of u coincides with one of the imprints v 2 , w j and coincides or is adjacent with the second imprint. This implies that if one of the vertices v 2 or w j coincides with z, then the second vertex also coincides with z. Indeed, suppose by way of contradiction that v 2 = z but w j = z (the case w j = z and v 2 = z is similar). If u 2 = z, then w j must be adjacent to u 2 = z = w i , which is impossible. Similarly, if u 2 = w j then by Lemma 20, u 2 must coincide or be adjacent to v 2 = z = w i , a contradiction. This concludes the case when one of the vertices v 2 or w j coincides with z. Now suppose that both v 2 or w j are different from z. In this case they are both not adjacent to z = v 1 = w i . If v 2 = w j , then clearly u 2 coincides with this vertex. Otherwise, since v, w ∈ I(u, x) and u 2 is one of v 2 , w j , by Lemma 20 and Corollary 7 we conclude that another vertex from this pair must be the parent of u 2 in ∂ * F (x). Since in line 10, the algorithm selects as imp 2 (v) the vertex of the pair v 2 , w j furthest from x (in ∂ * F (x) or in G), this shows that imp 2 (u) is indeed the second imprint u 2 of u.

Case 2. Both vertices w 1 , w 2 are distinct from z.

Since z = u 1 and w ∈ I(u, x), by Corollary 7 one of the imprints w 1 , w 2 , say w i must be adjacent to z and d G (u, z) = d G (w, w i ). Since u 1 = z, u 2 is different from w i . Note also that since w j is not adjacent to w i , we have w j = z. By Lemma 20, u 2 is adjacent or coincides with w j . Since this is impossible if u 2 = z, we conclude that u 2 = z. Consequently, u 2 is one of the vertices v 2 or w j . If v 2 = w j , then clearly, u 2 is that vertex. Otherwise, since v, w ∈ I(u, v), by Corollary 7, the vertex of the pair v 2 , w j which is different from u 2 is the parent of u 2 in ∂ * F (x). Since in line 10, the algorithm selects as imp 2 (v) the vertex of the pair v 2 , w j furthest from x (in ∂ * F (x) or in G), this shows that imp 2 (u) is indeed the second imprint u 2 of u. Consequently, in all cases we have u 2 = imp 2 (u), concluding the proof. Input: A panel F (x) and its total boundary ∂ * F (x) Output: For each vertex u ∈ F (x), its two imprints imp 1 (u) and imp 2 (u)

1 Run a first BFS on F (x) with respect to x in order to compute, for each vertex u, its distance d(u) to x and its predecessors pred 1 (u) and pred 2 (u) in I(u, x) ;

2 Run a second BFS on F (x) with respect to ∂ * F (x) in order to compute, for each vertex u, a closest to u vertex imp 1 (u) in ∂ * F (x), and the parent f (u) of u ;

3 Assume the vertices of F (x) ordered in the BFS-order computed by the first BFS traversal ; where k i=1 n i = n. Each of the fibers F i is a gated subgraph of G and thus is a cube-free median graph. Therefore, in F i we can compute a centroid c i by the algorithm of [START_REF] Bénéteau | Medians in median graphs and their cube complexes in linear time[END_REF] and partition F i into fibers with respect to St(c i ), and compute their boundaries and the imprints. All this can be done in O(n i ) time, leading to a total of k i=1 O(n i ) = O(n). Continuing this way, we conclude that at the partition iteration j, the total time to compute the centroid vertices, to partition the current fibers into smaller fibers, to compute their total boundaries and the imprints on them will take O(n) time. Since we have log 2 n partition steps, we conclude that the total complexity of the partition algorithm is O(n log n).

4 foreach u ∈ F (x) do 5 u 1 ← imp 1 (u) ; 6 (v, w) ← (pred 1 (u), pred 2 (u)) ; // pred 1 (u) = f (u) 7 (v 1 , v 2 ) ← (imp 1 (v), imp 2 (v)) ; // v = f (u) implies that u 1 = v 1 8 (w 1 , w 2 ) ← (imp 1 (w),
The correctness of the algorithm Distance_Encoding results from Lemmas 17,18,22 and the following properties of cube-free median graphs: stars and fibers are gated (Lemmas 5 and 6); total boundaries of fibers are quasigated (Corollary 5) isometric trees with gated branches (Lemma 11); and from the formulae for computing the distance between separated, 1-neighboring, and 2neighboring vertices (Lemmas 13, 14, and 15).

Given two labels LD(u) and LD(v), Distance can find the last common centroid of u and v by reading their label once. This can be done in time O(log 2 n) assuming the word-RAM model. This complexity can be improved to constant time by adding the following appropriate O(log 2 n) bits information concatenated to LD(u) and LD(v). For that, consider the tree T (of recursive calls) in which vertices at depth i are the centroids chosen at step i and in which the children of a vertex x are the centroids chosen at step i + 1 in the fibers generated by x at step i. We can observe that every vertex of G appears in this tree, that the last common centroid c of any two vertices u and v of G is their nearest common ancestor in the tree T , and that its depth j in this tree corresponds to its position in LD(u) and LD(v), i.e., LD

St[Cent] j (u) = LD St[Cent] j (v) = id(c).
As noticed in [START_REF] Peleg | Informative labeling schemes for graphs[END_REF], any distance labeling for trees T can be modified to support nearest common ancestor's depth (NCAD) queries by adding the depth depth(u) of u in T to the label L(u) given to each vertex u ∈ V (T ) by the distance labeling. Given two vertices u and v of T , the NCAD decoder then returns 1 2 (depth(u)+depth(v)-d T (u, v)). So, during the execution of Distance_Encoding, we can also construct the tree T of recursive calls and then give an NCAD label L (u) in T to every vertex of G. Now, the first step of Distance will consist in decoding L (u) and L (v) in order to find the last common median of u and v. Once this step is done, Distance has to call Dist_Star on labels of size O(log n) which requires a constant number of steps. After that, either the information necessary to compute d G (u, v) is directly encoded in LD(u) or LD(v), or Distance needs to to decode distance labels for trees, which can be done in constant time [START_REF] Freedman | Optimal distance labeling schemes for trees[END_REF]. Consequently Distance has a constant time complexity. The fact that Distance(LD(u), LD(v)) returns d G (u, v) follows from Lemmas 13,14 and 15. This completes the proof of Theorem 1.1.

Routing labeling schemes for cube-free median graphs

In this section we briefly describe the routing scheme; since there exists an important resemblance with the distance labeling scheme, a formal description of the routing scheme is given in the appendix. The idea of encoding is the same as the one for the distance labeling schemes: the graph G is partitioned recursively into fibers with respect to centroids. At every step, the labels of the vertices are given a vector of three parts, named "St", "1st", and "2nd" as before. However, the information stored in these parts is not completely the same as for distances. This is due to the fact that we need to keep the information specific for routing and also because, at the difference of distance queries, the routing queries are not commutative. For instance, for computing the distance between 1-neighboring vertices u and v, we assumed that u belongs to a panel and v to a cone. The case when u belongs to a cone and v belongs to a panel is reduced to the first case by calling the same corresponding function but commuting the arguments. This is no longer possible in the routing queries: routing from a panel to a cone is different from the routing from a cone to a panel.

As for distances, the routing decision is taken the first time u and v belong to different fibers of the current partition. Let c be a centroid vertex of the current graph under partition and let F (x) and F (y) be the two fibers containing u and v, respectively. If u and v are separated, then

d G (u, v) = d G (u, c) + d G (c, v)
, thus routing from u to v can be done by routing from u to c (unless u = c). Therefore, the encoding scheme must keep in the label of u the identifier of some neighbor of u in I(u, c). If u = c, then it suffices to route from u = c to the gate y of v in St(c). This is done by using the routing scheme for stars.

If u and v are 2-neighboring, then F (x) and F (y) are cones with a common neighboring panel F (w). Similarly to distance scheme, the algorithm finds F (w). Since the gates u + of u and v + of v in F (w) belong to a common shortest (u, v)-path, it suffices to route the message from u to u + . Therefore the encoding must keep in the label of u the identifier of a neighbor of u in I(u, u + ). The same information is required when u and v are 1-neighboring and F (x) is a cone and F (y) is a panel. Indeed, in this case there is a shortest (u, v)-path passing via the gate u + of u in F (y) and one of the imprints of v in ∂ * F (y). Therefore, to route from u to v it suffices to route from u to u + .

Finally, let u and v be 1-neighboring, however now F (x) is a panel and F (y) is a cone. Recall that in this case there exists a shortest (u, v)-path passing via one of the imprints u 1 or u 2 of u on ∂ * F (x) and the gate v + of v in F (x). Therefore, if u is different from v + then it suffices to route the message from u to a neighbor of u in I(u, u 1 ) or I(u, u 2 ) (depending of the position of v). Therefore, in the label of u we have to keep the identifiers of those two neighbors of u. To decide to which of them we have to route the message from u, we need to compare d G (u, u 1 ) + d G (u 1 , v + ) and d G (u, u 1 ) + d G (u 1 , v + ). Therefore, at the difference of the routing scheme in trees, our routing scheme for cube-free median graphs must incorporate the distance scheme. On the other hand, if u coincides with v + , then necessarily we have to route the message to a neighbor of u in I(u, v), which necessarily belong to the cone F (y) and not to F (x) (because v + is the gate of v in F (x)). There exists a unique vertex twin(v + ) of F (y) adjacent to v + . We cannot keep the identifier of twin(v + ) in the label of u = v + because a vertex in a panel may have arbitrarily many neighbors in the neighboring cones. Instead, we can keep the identifier of twin(v + ) in the label of v (recall that a cone has only two neighboring panels). Consequently, we obtain a routing scheme for cube-free median graphs with labels of vertices of size O(log 3 n).

Conclusion

In this paper we presented distance and routing labeling schemes for cube-free median graphs G with labels of size O(log 3 n). For that, we partitioned G into fibers (of size ≤ n/2) of the star St(c) of a centroid c of G. Each fiber is further recursively partitioned using the same algorithm. We classified the fibers into panels and cones and the pairs of vertices u, v of G into roommates, separated, 1-neighboring, and 2-neighboring pairs. If u and v are roommates, then d G (u, v) is computed at a later step of the recursion. Otherwise, we showed how to retrieve d G (u, v) by keeping in the labels of u and v some distances from those two vertices to their gates/imprints in a constant number of fibers. Our main technical ingredient is the fact that the total boundaries of fibers of cube-free median graphs are isometric quasigated trees.

This last property of total boundaries is a major obstacle in generalizing our approach to all median graphs, or even to median graphs of dimension 3. The main problem is that in this case the total boundaries are no longer median graphs.

Example 8.1. In Fig. 6 we present a median graph G of dimension 3, in which the total boundary of a fiber of a vertex c is not a median graph. The graph G is just the cubic grid 3 × 3 × 3 and the vertex c is one of the corners of this grid. The star St(c) of c is a single 3-cube Q. Let x be the vertex of Q opposite to c, and y, z, w are the three vertices of Q at distance 2 from c. Then the fiber F (x) is neighboring to F (y), F (z), and F (w). The total boundary ∂ * F (x) of F (x) consists of three squares ∂ y F (x), ∂ z F (x), and ∂ w F (x), pairwise intersecting in edges incident to x and all three intersecting in x. Consequently, ∂ * F (x) is not a median graph.

In this example, c is not a centroid of G. To repair this, we can consider the 5 × 5 × 5 cubic grid G in which G is embedded in such a way that c becomes the unique centroid of G . The star of c in G is a 3 × 3 × 3 grid. The vertex x belongs to this extended star, but the boundary of F (x) will still consists of the same three squares, thus ∂ * F (x) is not median. y z c w x Figure 6. A median graph of dimension 3 in which the total boundary of a fiber is not median. Therefore, we can no longer recursively apply to total boundaries the distance and routing labeling schemes for median graphs of smaller dimension (as we did in case of cube-free median graphs by applying such schemes for trees). Nevertheless, a more brute-force approach works for arbitrary median graphs G of constant maximum degree ∆. In this case, all cubes of G have constant size. Thus, the star St(c) cannot have more than O(2 ∆ ) vertices, i.e., St(c) has a constant number of fibers. Since every fiber is gated, at every step of the encoding algorithm, every vertex v can store in its label the distance from v to its gates in all fibers of St(c). Consequently, this leads to simple distance and routing labeling schemes with labels of (polylogarithmic) length for all median graph with maximum degree at most ∆: Proposition 1. Any median graph G with maximum degree ∆ admits distance and routing labeling schemes with labels of length O(2 ∆ log 3 n) bits.

Nevertheless, the maximum degree seems to be not the right complexity parameter of general median graphs. Similarly to high-dimensional computational geometry (where the dimension of the space is often constant), the largest dimension d of a cube of a median graph G might be considered as such a parameter. Consequently, we would like to formulate the following open question (which seems interesting and nontrivial already in dimension 3 and if we allow a constant stretch factor): Question 1. Does there exist a polylogarithmic distance labeling scheme (exact or approximate) for general median graphs or for median graphs of constant dimension?

In Section 3.2 we presented several problems from different research areas, which have a negative answer for all median graphs (viewed as CAT(0) cube complexes or domains of event structures) but can be positively solved for cube-free median graphs (alias 2-dimensional CAT(0) cube complexes). Our Question 1 can be cast in this type of problems (even if it is formulated for finite median graphs and is an algorithmic problem). On the other hand, the paper [START_REF] Chalopin | A counterexample to Thiagarajan's conjecture on regular event structures[END_REF] establishes that a conjecture from concurrency theory is false already for cube-free median graphs but (using a breakthrough result by Agol [START_REF] Agol | The virtual Haken conjecture[END_REF]) is true for hyperbolic median graphs. Gromov hyperbolicity is a parameter of a median graph, stronger than (cube-)dimension and in a sense is similar to the treewidth: the hyperbolicity of a median graph G is the size h of the largest h × h square grid isometrically embedded in G. Constant hyperbolicity implies constant dimension but not the vice-versa (already in case of cubefree median graphs). Gavoille and Ly [START_REF] Gavoille | Distance labeling in hyperbolic graphs[END_REF] established that general graphs of bounded hyperbolicity do not admit poly-logarithmic distance labeling schemes unless we allow a multiplicative error of order Ω(log log n), at least. We would like to finish this paper with a seemingly easier (but still open for us) version of Question 1: Question 2. Does there exist a polylogarithmic distance labeling scheme (exact or approximate) for median graphs of constant hyperbolicity?

Glossary

Notions and notations Definitions

Boundary ∂ y F (x) {u ∈ F (x) : ∃v ∈ F (y), uv ∈ E(G)}. Centroid c Vertex minimizing u → v∈V (G) d G (u, v). Cone F (x) w.r.t. to St(z) Fiber F (x) w.r.t. St(z) with d G (x, z) = 2. Convex subgraph H ⊆ G ∀u, v ∈ V (H), I(u, v) ⊆ V (H). Distance d G (u, v) Number of edges on a shortest (u, v)-path of G. Fiber F (x) w.r.t. H ⊆ G {u ∈ V (G) : x is the gate of u in H}. Gate of u in H ⊆ G u ∈ V (H) s.t. ∀v ∈ V (H), d G (u, v) = d G (u, u ) + d G (u , v). Gated subgraph H ⊆ G Every vertex u ∈ V (G) admits a gate in H. Halfspace W (u, v) {w ∈ V (G) : d G (u, w) < d G (v, w)}. Imprints set Υ(u, H) {w ∈ V (H) : I(u, w) ∩ V (H) = {w}}. Interval I(u, v) {w ∈ V (G) : d G (u, v) = d G (u, w) + d G (w, v)}. Isometric subgraph H ⊆ G ∀u, v ∈ V (H), d H (u, v) = d G (u, v). Locally convex subgraph H ⊆ G ∀u, v ∈ V (H), with d G (u, v) ≤ 2, I(u, v) ⊆ V (H). Panel F (x) w.r.t. to St(z) Fiber F (x) w.r.t. St(z) with d G (x, z) = 1. Quasigated H ⊆ G ∀u ∈ V (G), |Υ(u, H)| ≤ 2. Star St(z)
Union of the all hypercubes of G containing z.

Total boundary ∂ * F (x) y∼x ∂ y F (x).
and y ∈ I(z, x). This implies in particular that x ∼ y, u, v ∈ I(z, x), and z ∈ I(u, y) ∩ I(v, y). By quadrangle condition, there exists x ∼ u, v, one step closer to x than u and v. Then z, x ∈ I(u, y) and by quadrangle condition there exists a vertex y ∼ x , z one step closer to y than x and z. But then the vertices u, v, z, x , y induce a K 2,3 , which is a forbidden subgraph of median graphs.

Proof of Lemma 7. If x ∼ y, then F (x) ∼ F (y). Conversely, let F (x) ∼ F (y), i.e., there exists an edge x y of G such that x ∈ F (x) and y ∈ F (y). Since F (x) and F (y) are convex and G is bipartite, necessarily x ∈ I(y , x) and y ∈ I(x , y). Since x ∈ F (x), y ∈ F (y) and H is gated, we deduce that x ∈ I(x , y) and y ∈ I(y , x). From this we conclude that d G (x , x) = d G (y , y) and that d G (x, y) = d G (x , y ) = 1. This establishes the first assertion.

To prove the second assertion, let F (x) ∼ F (y) and we have to prove that ∂ y F (x) is gated. By induction on k = d G (x, x ), we can show that I(x , x) ⊆ ∂ y F (x) for any vertex x of ∂ y F (x). For we show that any neighbor x of x in I(x , x) belongs to ∂ y F (x). Let y be the neighbor of x in ∂ x F (y). Then x , y ∈ I(x , y), x , y ∼ x , and d G (x , y) = k +1, thus by quadrangle condition there exists a vertex y ∼ y , x at distance k -1 from y. Since y ∈ I(y , y) ⊂ F (y), we conclude that x ∈ ∂ y F (x). Thus I(x , x) ⊆ ∂ y F (x), yielding that the subgraph induced by ∂ y F (x) is connected.

By Lemma 2 it remains to show that ∂ y F (x) is locally-convex. Pick x , x ∈ ∂ y F (x) at distance two and let u ∼ x , x . Since F (x) is convex, u ∈ F (x). Let y and y be the neighbors of x and x , respectively, in F (y). Let v be the gate of u in F (y). Since d G (u, y ) = d G (u, y ) = 2 (because G is bipartite) and v ∈ I(u, y ) ∩ I(u, y ), we conclude that v is adjacent to u, y , and y . Hence v ∈ I(y , y ) ⊂ F (y), yielding u ∈ ∂ y F (x). This finishes the proof that ∂ y F (x) is gated.

If dim(∂ y F (x)) = dim(G) = d, then ∂ y F (x) contains a d-dimensional cube Q . Any vertex x of ∂ y F (x) is adjacent to a vertex y of F (y). Clearly, y must belong to ∂ x F (y). Since ∂ x F (y) is gated, y is the unique neighbor of x in ∂ x F (y). Let Q denote the subgraph of ∂ x F (y) induced by the neighbors y of vertices x of Q . We assert that Q is a d-cube. Indeed, if x x is an edge of Q , then since ∂ x F (y) is gated we conclude that the neighbors y and y of x and x must be adjacent, i.e., Q is a d-cube. Then Q and Q induce a (d + 1)-cube of G. Thus dim(∂ y F (x)) ≤ d -1.

Appendix B. Detailed description of the routing scheme

We present a detailed description of the labeling routing scheme. Let G = (V, E) be a cube-free median graph and let u be any vertex of G. Let i be any step of the algorithm Routing_Encoding applied to G and let c be a centroid of the current median subgraph containing u at step i. The "St" part LR St i (u) of the label of u is composed of the identifier of c, a port from u to c, a port from c to u, and the identifier of gate x := u ↓ of u to St(c) (i.e., of the fiber containing u). Note that c cannot store the ports to other vertices in order to answer routing queries from c. This is why the label of u contains the port LR (u) contains the identifier of the fiber containing u (i.e., the star labeling of u ↓ ).

The 1st and 2nd parts of the label of u contain similar information but they depend of whether u belongs to a panel or to a cone. If u belongs to a panel F (x) (recall that x = u ↓ ), then LR 1st i (u) is composed of the following four components:

(1) LR B.1. Routing queries. Let u and v be two arbitrary vertices of a cube-free median graph G and let LR(u) and LR(v) be their labels returned by the encoding algorithm Routing_Encoding. We describe how the routing algorithm Routing can decide by which port to send the message from u to v to a neighbor of u closer to v than u. B.1.1. The algorithm. We continue with the formal description of the routing algorithm Routing. The specific functions ensuring routing from panel to cone, from cone to panel, from cone to cone, or between separated vertices will be described in the next subsection. B.1.2. Description and functions. As for distance queries, the first thing to do in order to answer a routing query from u to v is to detect if u and v are 1-neighboring, 2-neighboring or separated, and the type (cone or panel) of the fibers containing them. This is done in the same way as explained in Section 6.3. Again, we assume that i is the first step such that u and v are no longer roommates. Denote by c the median vertex used at this step. We denote by F (x) the fiber containing u and by F (y) the fiber containing v (recall that x is the gate of u in St(c) and y is the gate of v in St(c)).

If u and v are 1-neighboring, the answer is computed differently when the source u is in a cone and when u is in a panel. If u is in a cone F (x) (and thus v is in a panel F (y)), we use the function Routing_Cone_to_Panel. This function determines which part (LR 1st i (v) or LR 2nd i (v)) of LR i (v) contains the information about the gate u + of u on F (y). Then the function returns the port port(u, u + ) to the gate u + of u in F (y), stored as LR If F (x) is a panel and F (y) is a cone, then u stored the distances to its two imprints u 1 and u 2 on the total boundary ∂ * F (x) and v stored the distance to its gate v + in F (x) (v + also belongs to ∂ * F (x)) and its twin twin(v + ) in F (y). When u is different from v + , the function Routing_Panel_to_Cone finds the tree distance labeling of v + , computes min{d G (u, u 1 ) + d T (u 1 , v + ), d G (u, u 2 ) + d T (u 2 , v + )}, and returns the port to the imprint of u minimizing the two distance sums. If u belong to the total boundary ∂ * F (x), then we distinguish two cases. If u = v + , then using the label LR i (v) of v the algorithm returns the port from twin(v + ) to v + = u. If u belongs to ∂ * F (x) but u = v + , since LR i (u) and LR i (v) contain a labeling for routing in trees of u and v + , Routing_Panel_to_Cone computes port(u, v + ) using the routing decoder for trees and returns it. Finally, if u and v are separated, two cases have to be considered depending of whether u is the centroid c or not. If u is not the centroid, then u stored port(u, c). Since a shortest path from u to v passes via c, Routing_Separated returns port(u, c). If u coincides with c, the port port(c, v) is not stored in LR i (u) but in LR

Figure 1 .

 1 Figure 1. Two cube-free median graphs. The left graph is used as a running example.

For

Lemma 3 .

 3 Intervals of a median graph G are convex.

Lemma 4 .Corollary 1 .Corollary 2 .

 412 [START_REF] Mulder | The Interval Function of a Graph[END_REF] Any median graph G satisfies the downward cube property.Lemma 4 immediately implies the following upper bound on the number of edges of G: If a median graph G has n vertices, m edges, and dimension d, then m ≤ dn ≤ n log 2 n. In particular, m ≤ 2n if G is cube-free.Lemma 4 also implies the following useful property of cube-free median graphs: If u and v are any two vertices of a cube-free median graph G, then v has at most two neighbors in the interval I(u, v).

Figure 2 .

 2 Figure 2. A star St(z) (in gray), its fibers (cones in blue, and panels in red), and an illustration of the classification of pairs of vertices: the pairs of empty circle points are roommates, of disk points are 2-neighboring,of empty square points are 1-neighboring, and of full square and diamond points are separated.

Figure 3 .

 3 Figure 3. Cases 1 and 2 of Lemma 12.

  (i)⇐⇒(ii): Notice that u and v are separated if and only if x = y and either F (x) and F (y) both are panels, or both are cones not having a neighboring panel, or one is a cone and another is a panel and the cone and the panel are not neighboring. If F (x) and F (y) are panels, then I(x, z) = {x, z} and I(y, z) = {y, z}, thus I(x, z) ∩ I(y, z) = {z}. If F (x) and F (y) are cones, then I(x, z) and I(y, z) are two squares Q x and Q y . By Lemma

Figure 4 .

 4 Figure 4. An illustration of Lemmas 13, 14 and 15: examples of shortest paths (in red) between separated, 1-neighboring, and 2-neighboring vertices u and v. The total boundaries of the panels appear in blue.

  and we denote the corresponding part of LD(u) by LD 0 (u) (i.e., LD 0 (u) := id(u)). At Step 1, Distance_Encoding computes a centroid c of G, the star St(c) of c, and the partition F c := {F (x) : x ∈ St(c)} of V into fibers. Every vertex u of G (c included) receives the identifier id(c) of c and its distance d G (u, c) to c. After that, every vertex x of St(c) receives a special identifier L St(c) (x) of size O(log |V |) consisting of a labeling for the star St(c), as described in Section 6.1. Then, Distance_Encoding computes the gate u ↓ in St(c) of every vertex u of G and adds its identifier L St(c) (u ↓ ) to LD(u). Note that the identifiers L St(c) (x) of the vertices of St(c) can also be used to distinguish the fibers of St(c). This triple (id(c), d G (u, c), L St(c) (u ↓

8 foreach u ∈ F (x) do 9 Find 10 Find the imprints u 1 11 L 12 L 13 L 19 Find 20 Find the gates u + 1 and u + 2

 8910111121319202 the gate u ↓ of u in St(c) ; and u 2 of u on∂ * F (x); (d, d 1 , d 2 ) ← (d G (u, c), d G (u, u 1 ), d G (u, u 2 )) ; St ← (id(c), d, L St(c) (u ↓ )) ; 1st ← (LD ∂ * F (x) (u 1 ), d 1 ) ; 2nd ← (LD ∂ * F (x) (u 2 ), d 2 ) ; 14 LD(u) ← LD(u) • (L St , L 1st , L 2nd ); 15 Distance_Encoding(F (x), LD(V )) ; 16 foreach cone F (x) ∈ F c do 17 foreach u ∈ F (x) do 18Find the gate u ↓ of u in St(c) ; the panels F (w 1 ) and F (w 2 ) neighboring F (x); of u in F (w 1 ) and F (w 2 ) ; 21

  Now suppose that the vertices u and v are 2-neighboring (i.e., d= d u = d v = 2).Then both u and v belong to cones. By inspecting LD St[gate] i (u) and LD St[gate] i(v), the function Distance_2-Neighboring determines the panel F (w) sharing a border with the cones F (u ↓ ) and F (v ↓ ). Then the function retrieves the gates u + and v + of u and v in this panel F (w) and the distances d G (u, u + ) and d G (v, v + ). The distance between the gates u + and v + is retrieved using the distance decoder for trees. The algorithm returns d

Claim 6 . 2 .

 62 If a, b, a , b are vertices of a bipartite graph G such that a ∼ b, d G (a, a ) ≤ d G (b, b ), and b ∈ I(b, a ), then either a = b and d G (b, b ) = d G (a, a ) + 1 or a ∼ b and d G (b, b ) = d G (a, a ). Proof. From the choice of the quadruplet a, b, a , b we deduce that d G (b, b

Algorithm 3 :

 3 ComputeImprints(F (x), ∂ * F (x))

  St[fromCent] i(u) from c to u. Here are the components of LR St i (u):(1) LR St[Cent] i (u) := id(c) is the unique identifier of c; (2) LR St[toCent] i (u)consists of a port to take from u in order to reach c; (3) LR St[fromCent] i (u) consists of a port to take from c in order to reach u; (4) LR St[gate] i

  1st[imp_LDT] i (u) is the tree distance labeling of the first imprint u 1 of u on ∂ * F (x); (2) LR 1st[imp_LRT] i (u) is the tree routing labeling of u 1 in the tree ∂ * F (x); (3) LR 1st[toImp] i (u) is port(u, u 1 ); (4) LR 1st[Dist] i (u) is the distance d G (u, u 1 ).

Algorithm 5 :

 5 Routing(LR(u), LR(v)) Input: The labels LR(u) and LR(v) of two vertices u and v of G, where u is the source and v the target Output: port(u, v)1 if LR 0 (u) = LR 0 (v) /* u = v */ then return 0 ; 2 Let i be the highest integer such that LR St[Cent] i (u) = LR St[Cent] i (v);

  3 d ← Dist_Star(LR St[gate] i (u), LR St[gate] i (v)) ; // d G (u ↓ , v ↓ ) 4 d u ← Dist_Star(LR St[gate] i (u), 0) ; // d G (u ↓ , c) 5 d v ← Dist_Star(LR St[gate] i (v), 0) ; // d G (v ↓ , c) 6 if d = 1 and d u = 1 then return Routing_Panel_to_Cone (LR i (u), LR i (v)) ; 7 if d = 1 and d v = 1 then return Routing_Cone_to_Panel (LR i (u), LR i (v)) ; 8 if d = 2 and d u = d v = 2 then return Routing_Cone_to_Cone (LR i (u), LR i (v)) ; 9 return Routing_Separated (LR i (u), LR i (v), LR 0 (u)).

  St[fromCent] i(v), and Routing_Separated returns it.function Routing_Separated(LR i (u), LR i (v), id(u)): if LR St[Cent] i (v) = id(u) then return LR

  Then F (x) and F (y) are not neighboring if and only if the edge yz is not an edge of the square Q x , i.e., if and only if I(x, z) ∩ I(y, z) = {z}.

[START_REF] Bandelt | Retracts of hypercubes[END_REF]

, Q x and Q y intersect in an edge wz if and only if F (w) is a panel neighboring F (x) and F (y), i.e., if and only if u and v are not separated. Finally, if F (x) is a cone and F (y) is a panel, then I(x, z) is the square Q x and I(y, z) is the edge yz.

  imp 2 (w)) ; 2} s.t. w i = u 1 = v 1 then 10 Set as imp 2 (u) the vertex of {v 2 , w j } furthest from x ; Set as imp 2 (u) the vertex of {v 2 , w j } furthest from x ; 6.4.5. The size of labels. Consider now the length of labels given by Distance_Encoding. To analyze the distance decoder, we consider a RAM model in which standard arithmetical operations on words of size O(log n) (additions, comparisons, etc.) are supposed to take constant time.Lemma 23. Distance_Encoding gives to every vertex of an n-vertex cube-free median graph G = (V, E) a label of length O(log 3 n) bits.Proof. Since at each division step we select a centroid, by Lemma 10 every vertex v ∈ V will appear in at most log 2 |V | different fibers. For each of these fibers, LD(v) will receive O(log 2 n) new bits. Indeed, the information stored correspond to Lines 11, 12 and 13 (or 22, 23 and 24) of Algorithm 1. L St clearly has size O(log n) because so does L St(c) (v ↓ ) as seen in Section 6.1 for stars, and L 1st and L 2nd both have size O(log 2 n) because the tree labeling they contain has size O(log 2 n) as seen in Section 6.1 for trees. 6.4.6. Complexity and correctness. Suppose that the partition of G into fibers contains k fibers F 1 , . . . , F k with n 1 , . . . , n k vertices, respectively,

	9	if ∃i ∈ {1,

11 else 12 Let i ∈ {1, 2} be such that w i is the parent of u 1 = v 1 in ∂ * F (x) ; 13 if w j = v 2 then imp 2 (u) ← v 2 ; 14 else

  Routing_Cone_to_Panel(LR i (u), LR i (v)): dir ← 2nd ;

						1st[toGate] i	(u) or LR 2nd[toGate] i	(u).
	if LR	St[gate] i	(v) = min{i : i ∈ LR	St[gate] i	(u)} then
	dir ← 1st ;
	return LR	dir[toGate] i	(u).

function

  function Routing_Panel_to_Cone(LR i (u), LR i (v)): dir v ← 2nd ; /* u is on the border */ then Let dir u ∈ {1st, 2nd} be such that LR ; // u is the gate of v on the panel F (x) ← 1st ; if d 2nd = min{d 1st , d 2nd } then dir u ← 2nd ; // u 2nd is the gate of u on a shortest path to v If u and v are 2-neighboring, then F (x) and F (y) are cones and the function Routing_Cone_to_Cone is similar to the function Routing_Cone_to_Panel. The common panel F (w) neighboring F (x) and F (y) can be found by inspecting LR As in the case of Routing_Cone_to_Panel, the function Routing_2-Neighboring returns the port port(u, u + ) from u to its gate u + in F (w). function Routing_Cone_to_Cone(LR i (u), LR i (v)): dir ← 2nd ;

	if LR	St[gate] i	(u) = min{i : i ∈ LR	St[gate] i	(v)} then
	dir v ← 1st ;
	if LR	1st[toGate] i	(u) = 0 or LR	2nd[toGate] i	(u) = 0 diru[toGate] i	(u) = 0 ;
	if LR return LR diru[gate_LDT] i dirv[fromGate] (u) = LR i (v) return Rout_Tree(LR dirv[gate_LDT] i diru[gate_LRT] i (u), LR (v) then dirv[gate_LRT] i	(v)) ;
	d 1st ← LR 1st[Dist] i	(u) + Dist_Tree(LR	1st[gate_LDT] i	(u), LR dirv[gate_LDT] i	(v)) ;
	d 2nd ← LR	2nd[Dist] i	(u) + Dist_Tree(LR	2nd[gate_LDT] i	(u), LR	dirv[gate_LDT] i	(v)) ;
	dir u return LR	diru[toGate] i	(u).
	St[gate] i (v). if LR (u) and LR St[gate] i St[gate] i (u) ∩ LR St[gate] i (v) = min{i : i ∈ LR St[gate] i (u)} then
	dir ← 1st ;
	return LR	dir[toGate] i	(u).

Acknowledgements. We would like to acknowledge the referees of this paper for careful reading of the manuscript and numerous suggestions that helped us to improve the readability of the paper. The work on this paper was supported by ANR project DISTANCIA (ANR-17-CE40-0015).

v 1 ∈ I(v, u 1 ), the convexity of intervals (Lemma 3) implies that v 1 ∈ I(u, v 2 ). Since v ∈ I(u, v 1 ), we conclude that v 1 ∈ I(v, v 2 ). This shows that u 1 ∈ I(u, v 2 ) is impossible. Suppose now that u 2 ∈ I(u, v 2 ). By Claim 6.2, either u 2 = v 2 or u 2 ∼ v 2 and d G (u, u 2 ) = d G (v, v 2 ). It remains to show that the second possibility is impossible.

Suppose by way of contradiction that u 1 ∼ v 1 and u 2 ∼ v 2 hold, and among all such edges of F (x) suppose that the edge uv is closest to ∂ * F (x). This implies that, in the tree ∂ * F (x), one of the vertices u i , v i (i = 1, 2) is the parent of another one. Suppose without loss of generality that d G (u, x) < d G (v, x). Since v i ∈ I(u i , v) and, by Lemma 19(b), v 1 , v 2 ∈ I(v, x) and u 1 , u 2 ∈ I(u, x), we conclude that, for each i = 1, 2, u i is the parent of v i . Let z be a neighbor of u in I(u, u 1 ). Since v, z ∈ I(u, v 1 ), by quadrangle condition there exists a common neighbor w of v and z one step closer to v 1 . Analogously, let z be a neighbor of u in I(u, u 2 ) and w be a common neighbor of z and v in I(v, v 2 ). Since u, w, w are neighbors of v in I(v, x) and the median graph G is cube-free, Corollary 2 implies that two of the vertices u, w, w must coincide. By definition of w, w we have w = u and w = u, thus necessarily w = w . This yields z = z . Consequently, w = w ∈ I(v, v 1 ) ∩ I(v, v 2 ) and z = z ∈ I(u, u 1 ) ∩ I(u, u 2 ). By Lemma 19(c), the vertices v 1 , v 2 are the imprints of w = w and the vertices u 1 , u 2 are the imprints of z = z and we obtain a counterexample (the edge wz) closer to ∂ * F (x) than uv, contrary to the choice of the edge uv.

From Lemma 20 and its proof we obtain the following corollary:

Proof. Since u 2 and v 2 are adjacent in the tree ∂ * F (x), one must be the parent of other. Suppose by way of contradiction that u 2 is the parent of v 2 . Since v 2 ∈ I(v, x), u 2 ∈ I(v 2 , v), and u ∈ I(u 2 , v), we conclude that u ∈ I(v, x) contrary to the assumption that d G (x, v) < d G (x, u). Lemma 21. If v, w are the neighbors of u in I(x, u), then the imprints u 1 , u 2 of u belong to the set {v 1 , v 2 , w 1 , w 2 } of imprints of v and w.

Proof. By Lemma 19(b), u 1 , u 2 ∈ I(u, x). Let z be a neighbor of u in I(u, u 1 ) and z be a neighbor of u in I(u, u 2 ). By Lemma 19(c), u 1 is an imprint of z and u 2 is an imprint of z . Since z ∈ I(u, u 1 ) ⊆ I(u, x) and z ∈ I(u, u 2 ) ⊆ I(u, x), z , z must be neighbors of u in I(u, x), i.e., z , z ∈ {v, w}. If z = z = v, then u 1 and u 2 are imprints of v and we are done. Otherwise, if z = v and z = w, then u 1 is an imprint of v and u 2 is an imprint of w, and we are done again.

We continue with an algorithm for computing the imprints of vertices u of F (x). It consists in running three BFS traversals of F (x). The first BFS (with respect to x) computes the distances d(u) = d G (u, x) from each vertex u ∈ F (x) to x and the (at most two) neighbors of u in the interval I(u, x). The second BFS (with respect to the total boundary ∂ * F (x)) computes the first imprint u 1 of each u ∈ F (x) as a closest to u vertex of ∂ * F (x). It also computes the distance d 1 (u) from u to this imprint u 1 and the parent f (u) of u belonging to the interval I(u, u 1 ). By Lemma 19, u 1 is also an imprint of f (u) (this explain why in line 7, v = f (u) implies v 1 = u 1 ). Finally, the vertices of F (x) are traversed for the third time according to the order computed by the first BFS traversal. For each vertex u ∈ F (x), in the assumption that the two imprints of its predecessors v, w ∈ I(u, x) have been already computed, the algorithm returns one of these four vertices as the second imprint imp 2 (u) of u. This choice is justified by Lemma 20. In the pseudocode of Algorithm 3 and in the proof of Lemma 22 we use the convention that whenever i denotes an element of the pair {1, 2}, j is the remaining element of {1, 2}, i.e., an element such that {i, j} = {1, 2}. Clearly, Algorithm 3 is linear in the number of vertices of F (x). Its correctness follows from the following lemma:

Appendices Appendix A. Fibers in median graphs

In this section we give the proofs of the well-known properties of median graphs stated in Section 4.

Proof of Lemma 1. Let x be the median of the triplet u, v, w. Then x must be adjacent to v and w. Since x ∈ I(u, v) ∩ I(u, w), necessarily d G (u, x) = k -1. Since any vertex x adjacent to v, w and having distance k -1 to u is a median of u, v, w, we conclude that x = x, concluding the proof.

Proof of Lemma 2. Obviously, any gated set is convex and any convex set is connected and locallyconvex. Assume that A is convex but not gated. Then there exists a vertex u ∈ V \ A which does not have a gate in A. Let x be a closest to u vertex of A. Since x is not the gate of u, there exists a vertex y ∈ A such that x / ∈ I(u, y). Let m be the median of the triplet u, x, y. Since x / ∈ I(u, y), m = x. Since m ∈ I(x, y) and H is convex, m belongs to A. Since m ∈ I(x, u) and m = x, d G (u, m) < d G (u, x), contrary to the choice of x.

Finally suppose that A is connected and locally-convex and we will show that A is convex. Let u and v be any two vertices of A. We show that I(u, v) ⊆ A by induction on the distance d H (u, v) between u and v in H. If d H (u, v) = 2, then the property holds by local convexity of

Pick any vertex x ∈ I(u, v). Let u be the neighbor of u on a shortest (u, v)-path of G passing via x. Let also u be the neighbor of u on a shortest (u, v)-path of H.

In the second case, obviously z ∈ I(x, y) ⊆ I(u, v). In the first case, let z , z be the medians of the triplets u, x, y and v, x, y, respectively. Then z ∈ I(u, x) ⊆ I(u, v) and z ∈ I(x, v) ⊆ I(u, v). Therefore, if z coincide with one of the vertices z , z , then we are done. Otherwise, the vertices x, y, z, z , z induce a forbidden K 2,3 .

Proof of Lemma 5. We will only sketch the proof (for a complete proof, see Theorem 6.17 of [START_REF] Chalopin | Weakly modular graphs and nonpositive curvature[END_REF] and its proof for a more general class of graphs). By Lemma 2 it suffices to show that St(z) is locally convex. Let x, y ∈ St(z) be two vertices at distance two and let v ∼ x, y. Then Q x = I(x, z) and Q y = I(y, z) are two cubes of St(z). We can suppose without loss of generality that v / ∈ Q x ∪Q y . This implies that x, y ∈ I(z, v), i.e., we can suppose that

By quadrangle condition, there exists u such that d G (u, z) = k -1 and u ∼ x, y. Necessarily I(u, z) is a (k -1)-cube Q u included in the k-cubes Q x and Q y . Therefore z has a neighbor x such that I(x, x ) is a (k -1)-cube disjoint from Q u and which together with Q u gives Q x . Analogously, z has a neighbor y such that I(y, y ) is a (k -1)-cube disjoint from Q u and which together with Q u gives Q y . By quadrangle condition there exists v ∼ x , y at distance k -1 to v. Then one can show that I(v, v ) induces a (k -1)-cube, which together with the k-cubes Q x and Q y define the (k + 1)-cube Q v = I(v, z). This establishes that v belongs to St(z).

Proof of Lemma 6. Each fiber F (x) induces a connected subgraph of G, thus it suffices to show that F (x) is locally convex. Pick u, v ∈ F (x) with d G (u, v) = 2 and let z be any common neighbor of u and v. Suppose by way of contradiction that z ∈ F (y) for y ∈ V (H), y = x. Then x ∈ I(u, y)∩I(v, y) The 2nd part LR 2nd i (u) of the label of u is defined in a similar way with respect to the second imprint u 2 of u on ∂ * F (x).

If u belongs to a cone F (x), then F (x) has two neighboring panels F (w 1 ) and F (w 2 ). The components LR 1st i (u) and LR 2nd i (u) of the 1st and 2nd parts of the label of u, each consists of four components. For example, LR 1st i (u) is composed of the following data: (1) LR i (u) of the label of u is defined in a similar way with respect to the gate u + 2 of u in the panel F (w 2 ). We assume that no port is given the number 0. If Routing returns 0 or if a label stores a port equal to 0, it means that there is no need to move. Here is the encoding algorithm:

Input: A cube-free median graph G = (V, E) and a labeling LR(V ) initially consisting on a unique identifier id(v) for every