Abstract In this article, we characterize the graphs G that are the retracts of Cartesian products of chordal graphs. We show that they are exactly the weakly modular graphs that do not contain K 2,3 , the 4-wheel minus one spoke W − 4 , and the k-wheels W k (for k ≥ 4) as induced subgraphs. We also show that these graphs G are exactly the cage-amalgamation graphs as introduced by Brešar and Tepeh Horvat (Cage-amalgamation graphs, a common generalization of chordal and median graphs, Eur J Combin 30 (2009), 1071-1081); this solves the open question raised by these authors. Finally, we prove that replacing all products of cliques of G by products of Euclidean simplices, we obtain a polyhedral cell complex which, endowed INTRODUCTION Median graphs constitute one of the most important classes of graphs investigated in metric graph theory and occur in different areas of discrete mathematics, metric geometry, and computer science. Median graphs and related median structures (median algebras and median complexes) have many nice properties and admit numerous characterizations. All median structures are intimately related to hypercubes: median graphs are isometric subgraphs of hypercubes; in fact, by a classical result of Bandelt [1] , they are the retracts of hypercubes into which they embed isometrically. It was also shown by Isbell [25] and van de Vel [33] that every finite median graph G can be obtained by successive applications of gated amalgamations from hypercubes, thus showing that the only prime median graph is the two-vertex complete graph K 2 (a graph with at least two vertices is said to be prime if it is neither a Cartesian product nor a gated amalgam of smaller graphs). A related construction of median graphs via convex expansions is given in [27, 28] . Median graphs also have a remarkable algebraic structure, which is induced by the ternary operation on the vertex set that assigns to each triplet of vertices the unique median vertex, and their algebra can be characterized using four natural axioms [7, 25] among all discrete ternary algebras. Finally, it was shown in [16] , [29] that the cubical complexes derived from median graphs by replacing graphic cubes by solid cubes are exactly the CAT(0) cubical complexes. Thus, due to a result of Gromov [22] , median complexes can be characterized as simply connected cubical complexes with triangle-free links of vertices. For more detailed information about median structures, the interested reader can consult the survey [6] and the books [19, 24, 28, 34] . INTRODUCTION This structure theory of graphs based on two fundamental operations, viz., Cartesian multiplication and gated amalgamation, was further elaborated for more general classes of graphs. Some of the results for median graphs have been extended to quasi-median graphs introduced by Mulder [28] and further studied in [8, 10, 35] : quasi-median graphs are precisely the weakly modular graphs not containing induced K 2,3 and K 4 − e; they can also be characterized as the retracts of Hamming graphs (Cartesian products of complete graphs) and can be obtained from complete graphs by Cartesian products and gated amalgamations. More recently, Bandelt and Chepoi [3] - [5] presented a similar decomposition scheme of weakly median graphs and characterized the prime graphs with respect to this decomposition: the hyperoctahedra and their subgraphs, the 5-wheel W 5 , and the 2-connected plane triangulations in which all inner vertices have degrees ≥ 6. Using these results and a result of Chastand [13, 14] , they further showed that weakly median graphs are the retracts of the Cartesian products of their primes and presented an axiomatic characterization of underlying weakly median algebras. The extensive research on generalizations of median graphs leads to a general framework for the study of classes of graphs, closed for Cartesian products and gated amalgamations, proposed in [9, 13, 14] . INTRODUCTION In this article, we continue this line of research and characterize the graphs G which are retracts of Cartesian products of chordal graphs. We show that they are exactly the weakly modular graphs which do not contain K 2,3 , W − 4 and the k-wheels W k for k ≥ 4 as induced subgraphs. We establish that these graphs G are exactly the cage-amalgamation graphs as introduced by Brešar and Tepeh Horvat [11] , that is, the graphs which can be obtained via successive gated amalgamations from Cartesian products of chordal graphs; this solves the open question raised in [11] . This result along with definitions and preliminary observations is presented in the next section, while its proof is the contents of Section 3. Finally in Section 4, we show that replacing all products of cliques of G by products of Euclidean simplices, we will obtain a polyhedral cell complex which, endowed with an intrinsic l 2 -metric, is a CAT(0) space. This generalizes similar results about median graphs as retracts of hypercubes (products of edges) and median graphs as 1-skeletons of CAT(0) cubical complexes. PRELIMINARIES AND THE CHARACTERIZATIONS In this section, we present all the necessary definitions and preliminary results so that at the end we formulate two characterizations of the retracts of products of chordal graphs. PRELIMINARIES AND THE CHARACTERIZATIONS All graphs G = (V, E ) occurring in this article are undirected, connected, and without loops or multiple edges. The distance d (u, v) PRELIMINARIES AND THE CHARACTERIZATIONS }. An induced subgraph of G (or the corresponding vertex set A) is called convex if it includes the interval of G between any pair of its vertices. An induced subgraph H of a graph G is said to be gated if for every vertex x outside H there exists a vertex x (the gate of x) in H such that each vertex y of H is connected with x by a shortest path passing through the gate x (i.e., x ∈ I(x, y)). The smallest convex (or gated, respectively) subgraph containing a given subgraph S is the convex hull (or gated hull, respectively) of S. PRELIMINARIES AND THE CHARACTERIZATIONS for all x, y ∈ W . The subgraph of H induced by the image of H under ϕ is referred to as a retract of H. PRELIMINARIES AND THE CHARACTERIZATIONS A graph G is a gated amalgam of two graphs G 1 and G 2 if G 1 and G 2 are (isomorphic to) two intersecting gated subgraphs of G whose union is all of G. The Cartesian product [24] PRELIMINARIES AND THE CHARACTERIZATIONS . . , G n has the n-tuples (x 1 , . . . , x n ) as its vertices (with vertex x i from G i ) and an edge between two vertices x = (x 1 , . . . , x n ) and y = (y 1 , . . . , y n ) if and only if, for some i, the vertices x i and y i are adjacent in G i , and x j = y j for the remaining j = i. PRELIMINARIES AND THE CHARACTERIZATIONS In regard to a decomposition scheme involving multiplication and amalgamation, a graph with at least two vertices is said to be prime if it is neither a Cartesian product nor a gated amalgam of smaller graphs. For instance, the only prime median graph is the two-vertex complete graph K 2 [25, 33] and the prime quasi-median graphs are exactly the complete graphs [8, 25] . A graph G is weakly modular [2, 15] if its distance function d satisfies the following triangle and quadrangle conditions (see Fig. 1 ): Triangle condition: For any three vertices u, v, w ): Quadrangle condition: For any four vertices u, v, w, z ): A weakly median graph is a weakly modular graph in which the vertex x defined in the triangle and quadrangle conditions is always unique. Equivalently, weakly median graphs can be defined as the weakly modular graphs in which each triplet of vertices has a unique quasi-median. Median graphs are the bipartite weakly median graphs and, equivalently, can be defined as the graphs in which each triplet of vertices u, v, w has a unique median vertex, that is, |I(u, v) ∩ I(u, w) ∩ I(v, w)| = 1. Bridged graphs constitute another important subclass of weakly modular graphs. Recall that a graph is called bridged [17, 18, 31] if it does not contain any isometric cycle of length greater than 3, or alternatively, if the closed neighborhood N[A] = A ∪ {y ∈ V : y is adjacent to some x ∈ A} of every convex set A of G is convex. Chordal graphs constitute the most famous subclass of bridged graphs. A graph is said to be chordal if it does not contain induced cycles of length greater than 3. In this article, we will investigate the finite graphs G, which are obtained from Cartesian products of chordal graphs via gated amalgamations. These graphs have been introduced by Brešar and Tepeh Horvat [11] and are called cageamalgamation graphs. More precisely, the Cartesian products of connected cutvertexfree chordal graphs were called in [11] cages, and the graphs that can be obtained by a sequence of gated amalgamations from cages were called cage-amalgamation graphs. It can be easily shown that cage-amalgamation graphs are weakly modular graphs and that they do not contain induced K 2,3 , wheels W k , and almost-wheels W − k (the wheel W k is a graph obtained by connecting a single vertex-the central vertex-to all vertices of the k-cycle; the almost-wheel W − k is the graph obtained from W k by deleting a spoke (i.e., an edge between the central vertex and a vertex of the k-cycle), see Figure 2 for examples. It was conjectured in [11] that in fact this list of forbidden subgraphs completely characterizes the cage-amalgamation graphs. The main result of our article proves this conjecture (in fact, we note that just W − 4 suffices in the list of forbidden almost wheels). Theorem 1. For a finite graph G = (V, E ), the following conditions are equivalent: The proof of this theorem is provided in the following section. The most difficult part of the proof is the implication (ii) ⇒ (iii), which we establish in two steps. First, we show that if G is a weakly modular graph not containing induced K 2,3 , wheels W k , and almost-wheels W − k for k ≥ 3, then all its prime graphs are 2-connected chordal graphs or a K 2 . In the second part, using the techniques developed in [3] , we show that G can be obtained via gated amalgamations from Cartesian products of prime graphs. PROOF OF THEOREM 1 The implication (i) ⇒ (ii) is obvious: chordal graphs are weakly modular and do not contain induced K 2,3 , wheels W k , and almost-wheels PROOF OF THEOREM 1 The implication (iii) ⇒ (i) is a particular case of Theorem 1 and Corollary 4 of [4] (the proof of Corollary 4 also follows from a more general result of Chastand [14] ). By Theorem 1 of [4] , any cage-amalgamation graph G embeds isometrically into the Cartesian product H = H 1 · · · H k of its prime graphs. Corollary 4 of [4] then shows that there exists a retraction from H to G, establishing (iii) ⇒ (i). PROOF OF THEOREM 1 The proof of the implication (ii) ⇒ (iii) is the main contribution of this section. We start with the lemma that shows that only W The proof of (ii) ⇒ (iii) employs the fact that each finite chordal graph admits a perfect elimination scheme, which can be computed by maximum cardinality search (MCS) algorithm [20, 30, 32] . Running a modification of MCS on the gated hull of a triangle in a graph G satisfying the condition (ii) of Theorem 1, we show that the level subgraphs returned by MCS are all convex subgraphs of G. This allows us to show that the gated hull of each triangle of G is a 2-connected chordal graph, thus identifying the prime graphs of G. To show that G can be obtained from Cartesian products of 2-connected chordal graphs and edges using successive amalgamations, we adapt the second part of the proof of Theorem 1 of [3] . PROOF OF THEOREM 1 A simplicial vertex of a graph G is a vertex v such that its neighborhood N(v) = {u ∈ V (G) : u is adjacent to v} induces a complete subgraph of G. A perfect elimination ordering (PEO) of a graph G = (V, E ) with n vertices is a total ordering v 1 , . . . , v n of its vertices such that each v i is a simplicial vertex in the subgraph G i induced by the level set L i = {v 1 , . . . , v i }. It is well known (see [20] ) that a finite graph G admits a PEO if and only if G is chordal. A PEO of a chordal graph G can be found (in linear time) either using Lexicographic Breadth-First-Search (LexBFS) [30] or MCS introduced by Tarjan and Yannakakis [32] . MCS algorithm works as follows: the first vertex is chosen arbitrarily, and the (i + 1)th vertex is the unlabeled vertex that has the largest number of already numbered neighbors, breaking ties arbitrarily. We will denote by α(v) the number of v in a total ordering PROOF OF THEOREM 1 We start with two properties of MCS in chordal graphs. PROOF OF THEOREM 1 The following result is a part of folklore, and we give its short proof only to make the article self-contained. Lemma 2. Let G be a chordal graph and α an ordering of vertices produced by MCS. If a vertex z belongs to an induced path between two vertices x, y, then α(z) < max{α(x), α(y)}. Proof. Assume without loss of generality that α(x) < α(y) and let P be an induced path between x and y. Suppose by way of contradiction that P contains a vertex z such that α(z) > α(y) and suppose without loss of generality that z is the vertex of P with the largest index i = α(z). Then among all vertices of P the vertex z was labeled last. Hence z and its neighbors z , z in P all belong to the subgraph G i . Since z and z are not adjacent, z is not a simplicial vertex of G i , contradicting the fact that on chordal graphs MCS returns a PEO. Lemma 2. Let G be a chordal graph and α an ordering of vertices produced by MCS. If a vertex z belongs to an induced path between two vertices x, y, then α(z) < max{α(x), α(y)}. A minimal (vertex) separator of a graph G = (V, E ) is a subset of vertices K of G such that the subgraph of G induced by V − K contains at least two connected components A and B, and that K is minimal by inclusion with respect to this separating property. Then K necessarily separates any two vertices x ∈ A and y ∈ B in the sense that all (x, y)-paths share a vertex with K. It is well known [20] that any minimal separator K of a chordal graph G induces a complete subgraph of G and, moreover, K separates two vertices x and y such that both x and y are adjacent to all vertices of K. Lemma 3. Let K be a minimal separator of a chordal graph G, let A and B be two connected components of G − K, and let u ∈ A be a vertex that is adjacent to all vertices of K. Let α be an ordering of vertices produced by MCS. If α labels some vertex of A before any vertex of B is labeled, then α labels u before any vertex of B. Proof. Let a 0 ∈ A be the vertex with the smallest index α(a 0 ) among all vertices of A ∪ B. Since A is connected, we can choose P := (a 0 , a 1 , . . . , a k = u) to be a shortest (and therefore induced) path connecting the vertices a 0 and u in A. Suppose by the way of contradiction that there exists b ∈ B that was labeled before u, that is α(b) < α(u), and let b be the first such vertex with respect to α. Denote by L(x) the set of labeled neighbors of a vertex x at the moment of time when b was labeled. Let K 0 := L(b). Since K separates A from b ∈ B, from the choice of b and our assumption we conclude that K 0 ⊆ K (see also Fig. 3) . Lemma 3. Let K be a minimal separator of a chordal graph G, let A and B be two connected components of G − K, and let u ∈ A be a vertex that is adjacent to all vertices of K. Let α be an ordering of vertices produced by MCS. If α labels some vertex of A before any vertex of B is labeled, then α labels u before any vertex of B. We assert that for each vertex a i of P, the inequality α(a i ) < α(b) holds. Indeed, let t be an arbitrary vertex in K 0 and let P t := (a 0 , . . . , a k , t ) be the path from a 0 to t, obtained from P by adding t at the end. Since α(u) > α(b) > α(t ) by the assumption and α(u) > α(a 0 ) from the choice of a 0 , by Lemma 2 the path P t is not induced. Since P is induced, the only possible chords on this path are the chords of the form ta i , where 0 ≤ i < k. Let i t be the smallest index such that t and a i t are adjacent. To avoid induced cycles of length greater than 3 in G, for all j comprised between i t + 1 and k, the vertices t and a j must be adjacent as well. Since the subpath (a 0 , . . . , a i t , t ) of P t is induced, by Lemma 2 we infer that all vertices of this path must be labeled either before t or before a 0 , but in either case we have α( Lemma 3. Let K be a minimal separator of a chordal graph G, let A and B be two connected components of G − K, and let u ∈ A be a vertex that is adjacent to all vertices of K. Let α be an ordering of vertices produced by MCS. If α labels some vertex of A before any vertex of B is labeled, then α labels u before any vertex of B. As a result, we obtain the following property for the vertices of P: every vertex a j ∈ {a 0 , . . . , a q } was labeled before b, that is, α(a j ) < α(b). On the other hand, all vertices a q+1 , . . . , a k = u are adjacent to all Lemma 3. Let K be a minimal separator of a chordal graph G, let A and B be two connected components of G − K, and let u ∈ A be a vertex that is adjacent to all vertices of K. Let α be an ordering of vertices produced by MCS. If α labels some vertex of A before any vertex of B is labeled, then α labels u before any vertex of B. The claimed assertion is thus proven. Now, since a k = u, this assertion implies that α(u) < α(b), as desired. Lemma 3. Let K be a minimal separator of a chordal graph G, let A and B be two connected components of G − K, and let u ∈ A be a vertex that is adjacent to all vertices of K. Let α be an ordering of vertices produced by MCS. If α labels some vertex of A before any vertex of B is labeled, then α labels u before any vertex of B. For the remainder of this section, let G be a weakly modular graph that does not contain any of K 2,3 , W k , and W − k , k ≥ 4, as an induced subgraph. We will show that G can be obtained by a sequence of gated amalgamations from Cartesian products of chordal graphs. We commence by establishing a number of auxiliary results. A subgraph H of G is said to be -closed if, for every triangle having two vertices in H, the third vertex belongs to H as well; then the smallest -closed subgraph containing S is the -closure of S. In order to check whether a given subgraph of G is convex or gated the following lemma is useful. This essentially coincides with Theorem 7 of [15] and can be proved quite easily by induction. Lemma 4. A connected subgraph H of a weakly modular graph G is convex if and only if H is locally convex, that is, for every pair of nonadjacent vertices u, v of H all common neighbors of u and v belong to H whenever at least one common neighbor does. Moreover, a convex subgraph is gated if and only if it is -closed. Now we will prove that the gated hull H of each triangle T = {a, b, c} of G is a convex chordal subgraph of G. For this, we perform a (partial) MCS α in G starting with α(a) = 1, α(b) = 2, α(c) = 3 until the moment when all yet unlabeled vertices have at most one previously labeled neighbor. Denote by H the subgraph of G induced by all labeled vertices at the end of the procedure, and let H i be the subgraph of H induced by the first i labeled vertices. Proposition 1. For any i, H i is a chordal and convex subgraph of G. Proof. We proceed by induction on i. Clearly, H 1 , H 2 , and H 3 are all chordal and convex subgraphs of G. By way of contradiction, assume that for some i ≥ 3, H i is convex and chordal but Proposition 1. For any i, H i is a chordal and convex subgraph of G. , which are both adjacent to u and v i+1 . Now, we will prove that any vertex in H i , adjacent to v i+1 is also adjacent to v. Proposition 1. For any i, H i is a chordal and convex subgraph of G. From the definition of the labeling α, we know that such a vertex exists. By induction assumption, H i is convex, hence x and y are adjacent because they have a common neighbor v i+1 not in H i . First, suppose that the vertices u and y are adjacent. To avoid forbidden W − 4 and W 4 , the vertex v must be adjacent to x and to y, and we are done. Thus, we may assume that u and y are not adjacent. We distinguish two cases. . Thus, we may further assume that the vertices v and y are not adjacent (see Fig. 4, left) . By the triangle condition, there exists a common neighbor t of u, v, and y. Since H i is convex and t ∈ I(u, y), necessarily t ∈ V (H i Since H i is chordal and the path P is induced, to avoid an induced cycle of length ≥ 4 formed by some vertices of P ∪ {x}, the vertex x must be adjacent to all vertices of P. To avoid a forbidden wheel W k induced by v, v i+1 , x and the vertices of P, necessarily v or v i+1 is adjacent to some vertex of P. Since P is induced and H i is convex, v can be adjacent only with the neighbor u of u in P and v i+1 can be adjacent only with the neighbor y of y in P. If u = y (see Fig. 4 , center) or only one of the edges vu or v i+1 y exists, then still we can find there an induced wheel W k , k ≥ 4. Hence, u = y and v, v i+1 are both adjacent to u = y (see Fig. 4, right) . Since the induced path P is arbitrary, we infer that each induced path in H i between u and y is of length 2, and all common neighbors of u and y are adjacent to both v and v i+1 . As a conclusion, the set K = {z ∈ H i : u, y ∈ N(z)} is a minimal (by inclusion) Let uv be an edge in G and, from now on, let H be the gated hull of the graph induced by {u, v} in G. If uv does not belong to a triangle of G, then {u, v} is convex and -closed, thus {u, v} itself is a gated set of G. In this case, H is isomorphic to K 2 and is clearly chordal. If u, v lie in a triangle T , then H coincides with the gated hull of T and can obtained by the (partial) MCS procedure as described above. By Proposition 2, H is chordal as well. t ∈ I(u, y), necessarily t ∈ V (H i Any gated subset S of G gives rise to a partition W a (a ∈ S) of the vertex set of G; viz., the fiber W a of a relative to S consists of all vertices x (including a itself) having a as their gate in S. For adjacent vertices a, b of S, let U ab be the set of vertices from W a which are adjacent to vertices from W b . Let also U a = {x ∈ W a : ∃y ∈ W a , xy ∈ E(G)}. By some abuse of notation, W a , U a , and U ab will denote both the sets and the subgraphs induced by these sets. An example is given in Figure 5 . By using the quadrangle condition for a, x, y, and z (or, if x and y are adjacent, using the triangle condition for a, x, and y), we conclude that x and y have a common neighbor t such that d(a, t ) = k − 1. Since t ∈ I(x, a), clearly t ∈ W a and thus d(b, t ) = k. Applying the quadrangle condition for b, t, z, and x, we infer that t and z have a common neighbor s such that d(b, s) = k − 1. It is easy to see that t is not adjacent to z and that s is not adjacent to x and y. Consequently, the vertices x, y, z By Lemma 5, we infer that any vertex x ∈ U ab = U a has exactly one neighbor in U ba = U b . Indeed, since each fiber W b is gated, there cannot be a vertex not in W b adjacent to two vertices of W b . This fact combined with Lemma 6 gives rise to the following natural mapping: f ab : U a −→ U b that maps x ∈ U a to the neighbor of x in U b . Lemma 7. Let a, b be two adjacent vertices of H. Then U a and U b are isomorphic subgraphs of G and f ab is an isomorphism between the graphs U a and U b . Proof. Let x, y be two adjacent vertices of U a , and suppose that their neighbors x , y in U b are not adjacent. By Lemma 5 each W a is gated, thus convex. Since W b is convex, we infer that d W b (x , y ) = 2. Let z ∈ W b be a common neighbor of x and y . Since d(y, z ) = d(y, x ) = 2, by the triangle condition we infer that there exists a common neighbor u of y, x , and z . Since W b is -closed, we conclude that u ∈ W b . But then y ∈ U a has two neighbors u and y in U b , which is impossible. Lemma 8. The subgraphs U a are gated for all a ∈ V (H ) and are mutually isomorphic. Their union is isomorphic to H U, where U is any of U a . Proof. Since H is connected, from Lemma 7, we immediately infer that the subgraphs U a are all mutually isomorphic. Since each fiber W a is gated, to prove that U a is gated it suffices to show that U a is locally convex and -closed in the subgraph W a . Let x, y ∈ U a be two vertices having a common neighbor z ∈ U a and suppose that there is a vertex s ∈ W a \ U a that is adjacent to both x and y but not to z (the case when s is adjacent to z is covered by -closedness of U a established below). Let b be a neighbor of a in H and let x , z , y ∈ U b be the neighbors of x, z, y, respectively. By Lemma 7, we conclude that z is adjacent to x and y but x and y are not adjacent. Then d(s, x ) = d(s, y ) = d(s, z ) − 1 = 2 and by the quadrangle condition we find that x , y and s have a common neighbor s . Since W b is convex, s ∈ U b which in turn implies that s ∈ U a , a contradiction. This shows that U a is locally convex. Lemma 8. The subgraphs U a are gated for all a ∈ V (H ) and are mutually isomorphic. Their union is isomorphic to H U, where U is any of U a . Let x, y ∈ U a be two adjacent vertices and suppose that there is a vertex s ∈ W a \ U a adjacent to both x and y. Let b be a neighbor of a in H and let x , y ∈ U b be the neighbors of x, y, respectively. By Lemma 7, we know that x is adjacent to y . Then d(s, x ) = d(s, y ) = 2 and by the triangle condition we find that x , y , and s have a common neighbor s . Since N(s) ⊆ U a , it implies that either x or y has two neighbors in U a , a contradiction. This shows that U a is -closed. Thus U a is indeed gated. Lemma 8. The subgraphs U a are gated for all a ∈ V (H ) and are mutually isomorphic. Their union is isomorphic to H U, where U is any of U a . The structure of the union of all U a ,a ∈ V (H ), is now completely described. Its vertex set is isomorphic to V (H ) × V (U ), where U is isomorphic to U a for any a ∈ V (H ). For any vertices a, c ∈ V (H ) and any x ∈ U a , y ∈ U c , x is adjacent to y if and only if either a = c and xy ∈ E(U a ), or a and c are adjacent and y is the unique neighbor of x in U c . Hence, the union of U a over all a ∈ V (H ) is isomorphic to H U. Lemma 8. The subgraphs U a are gated for all a ∈ V (H ) and are mutually isomorphic. Their union is isomorphic to H U, where U is any of U a . We collected all results to conclude the proof of the implication (ii) ⇒ (iii) of Theorem 1. We proceed by induction on the cardinality of G. First, if H (the gated hull of {u, v} in G) is equal to whole graph G, then G is chordal, hence G is a cage-amalgamation graph. Therefore, we can suppose that H is a proper subgraph of G. Now, suppose that for any a ∈ V (H ), the set W a coincides with U a . By Lemma 8, G is isomorphic to H W a = H U a , where H is a chordal graph. Since W a has smaller cardinality than G and since W a is a weakly modular graph without K 2,3 , W k , and W − k , k ≥ 4 (as a gated subgraph of G), by induction hypothesis W a is a cage-amalgamation graph. Since Cartesian products and gated amalgams commute (see also Lemma 3.1 of [11] ), G = H W a is a cageamalgamation graph as well. Finally, suppose that for some a ∈ V (H ) the set W a − U a is nonempty. Since U a is gated and is a separator of G, we conclude that G is the gated amalgam of W a and G − (W a − U a ) along the common gated subgraph U a . Since both those graphs W a and G − (W a − U a ) have smaller cardinality that G, they are cageamalgamation graphs, and thus so is G. This concludes the proofs of the implication (ii) ⇒ (iii) and of Theorem 1. THE PRISM COMPLEXES OF CAGE-AMALGAMATION GRAPHS The second result of this article concerns the geometry of prism complexes derived from cage-amalgamation graphs. Namely, we show that all such complexes endowed with intrinsic l 2 -metric are CAT(0) metric spaces. We continue with the definition of piecewise Euclidean (PE) cell complexes and of CAT(0) metric spaces. THE PRISM COMPLEXES OF CAGE-AMALGAMATION GRAPHS A Euclidean cell is a convex polytope in some Euclidean space. By a PE cell complex, we will mean a space X formed by gluing together Euclidean cells via isometries of their faces, together with the decomposition of X into cells. Additionally, we assume that the intersection of two cells is either empty or a single face of each of the cells. If all cells of X are Euclidean simplexes (respectively, cubes), we will say that X is a simplicial (respectively, cubical) cell complex. If all cells of X are Euclidean prisms, that is, Cartesian products of simplices, then X is called a prism complex; the precise definition is given below. For a PE complex X denote by V (X) and E(X) the vertex set and the edge set of X, namely, the set of all zero-dimensional and one-dimensional faces of X. The pair (V (X), E(X)) is called the (underlying) graph or the 1-skeleton of X and is denoted by G(X). THE PRISM COMPLEXES OF CAGE-AMALGAMATION GRAPHS With each simplicial or cubical PE complex X one can associate in a canonical way an abstract simplicial or cubical complex. Recall that an abstract simplicial complex X is a collection of sets (called simplices) such that σ ∈ X and σ ⊆ σ implies σ ∈ X. A cubical complex X is a set of (graph) cubes of any dimensions that is closed under taking subcubes and nonempty intersections. Simplices or cubes of the respective complexes are called faces. The link of a vertex x in a simplicial complex X, denoted link(x, X) is simplicial complex consisting of all simplexes σ of X such that x / ∈ σ and σ together with x defines a simplex of X. A simplicial complex X is a flag complex (or a clique complex) if any set of vertices is included in a face of X whenever each pair of its vertices is contained in a face of X (in the theory of hypergraphs, this condition is called conformality). A flag complex can therefore be recovered by its underlying graph G(X): the complete subgraphs of G(X) are exactly the simplices of X. Conversely, for a graph G one can derive a simplicial complex X(G) by taking all complete subgraphs (simplices) as faces of the complex. Analogously, for a graph G one can also derive a cubical complex C(G) by taking all induced subhypercubes as faces. If G is a median graph, then C(G) consists of all hypercubes which are obtained as Cartesian products of the prime graphs (as we noticed above, they are all two-vertex complete graphs K 2 ). The simplicial complexes arising as clique complexes of bridged graphs were characterized in [16] as simply connected simplicial complexes in which the links of vertices do not contain induced 4-and 5-cycles (these complexes have been rediscovered and investigated by Januszkiewicz and Swiatkowski [26] , who called them "systolic complexes" and considered them as simplicial complexes satisfying combinatorial nonpositive curvature property, see the definition below). THE PRISM COMPLEXES OF CAGE-AMALGAMATION GRAPHS In the context of graphs G obtained via Cartesian products and gated amalgamations from prime graphs containing cliques of arbitrary size, it is natural to associate to each prime graph G i of G a PE simplicial complex X(G i ) obtained by replacing each simplex of the clique complex of G i by an Euclidean simplex. Then the prism complex of G is the PE cell complex H(G) obtained by taking all Hamming subgraphs of G (Cartesian products of complete subgraphs of prime graphs) and replacing them by respective Euclidean prisms. Then each face τ of H(G) is the Cartesian product τ = σ 1 × · · · × σ k , where σ i is a simplex of X(G i ), i = 1, . . . , k. This is consistent with the standard definition of the product of two (or more) polytopes given on pp. 9-10 of the book of Ziegler [36] : given two polytopes P ⊂ R n and Q ⊂ R m , the product of P and Q is the set P × Q = {(x, y) : x ∈ P, y ∈ Q}. P × Q is a polytope of dimension dim(P) + dim(Q), whose nonempty faces are the products of nonempty faces of P and nonempty faces of Q. It is well known (see e.g., p. 110 of [36] ) that the product σ 1 × · · · × σ k of Euclidean simplices σ 1 , . . . , σ k is a convex polyhedron τ, called a prism. Notice that if G is a median graph (or more generally, a triangle-free graph), then the prism complex of G coincides with the cubical complex C(G) defined before. THE PRISM COMPLEXES OF CAGE-AMALGAMATION GRAPHS Let (X, d) be a metric space. The interval between two points x, y of X is the set THE PRISM COMPLEXES OF CAGE-AMALGAMATION GRAPHS ) is said to be geodesic if every pair of points x, y ∈ X is joined by a geodesic (which is necessarily included in I(x, y) ) [12] . Every complete Menger-convex metric space is geodesic [12] . Any finite PE cell complex X can be endowed with an intrinsic l 2 -metric [12] , transforming X into a complete geodesic space. Suppose that inside every cell of X the distance is measured according to the Euclidean l 2 -metric. The intrinsic l 2 -metric d 2 of X is defined by assuming that the distance between two points x, y ∈ X lying in different cells equals to the infimum of the lengths of the paths joining them. Here a path in X from x to y is a sequence P of points x = x 0 , x 1 . . . Now, we will briefly review the definitions and some characterizations of CAT(0) metric spaces (geodesic metric spaces of global nonpositive curvature). This theory originates from the classical papers of Alexandrov, Busemann, Bruhat, Cartan, Hadamard, Tits, Toponogov, and others. In most generality it has been defined in the seminal paper of Gromov [22] . CAT(0) spaces represent a far-reaching common generalization of Euclidean spaces, classical real-hyperbolic spaces (which are spaces with negative curvature), and Riemannian manifolds of strictly negative sectional curvature. CAT(0) spaces play a vital role in modern combinatorial group theory, where various versions of hyperbolicity are related to group-theoretic properties [21] , [22] ; many arguments in this area have a strong metric graph-theoretic flavor. For a survey in more depth and background, the reader should refer to the book of Bridson and Haefliger [12] , whose terminology we follow. THE PRISM COMPLEXES OF CAGE-AMALGAMATION GRAPHS A geodesic triangle (x 1 , x 2 , x 3 ) in a geodesic metric space (X, d) consists of three distinct points in X (the vertices of ) and a geodesic between each pair of vertices (the sides of ). A comparison triangle for ( THE PRISM COMPLEXES OF CAGE-AMALGAMATION GRAPHS ) is defined to be a CAT(0) space [22] if all geodesic triangles (x 1 , x 2 , x 3 ) of X satisfy the comparison axiom of Cartan-Alexandrov-Toponogov (this explains the acronym CAT(0)): THE PRISM COMPLEXES OF CAGE-AMALGAMATION GRAPHS If y is a point on the geodesic between x 1 and x 2 in the triangle (x 1 , x 2 , x 3 ) and y is the unique point on the line segment THE PRISM COMPLEXES OF CAGE-AMALGAMATION GRAPHS This simple axiom turns out to be very powerful, because CAT(0) spaces have many properties and can be characterized in several natural ways. For example, a geodesic metric space (X, d) is CAT (0) if and only if the distance function f (t ) = d(α(t ), β(t )) is convex for any geodesics α and β. From this property, one can immediately conclude that in CAT(0) spaces (such as in bridged graphs) the r-neighborhoods B r (A) = {x : d(x, A) ≤ r} of convex sets A are convex. The convexity of balls yields that CAT(0) spaces are contractible. The convexity of the distance function also implies that CAT(0) spaces do not contain isometrically embedded cycles. Any two points of a CAT(0) space can be joined by a unique geodesic; furthermore, a PE complex X is CAT(0) if and only if any two points of X can be joined in X by a unique geodesic. Other characterizations (in particular, via links) and properties of CAT(0) PE complexes can be found in the book [12] . In the case of cube complexes, Gromov [22] presented a nice combinatorial characterization of CAT(0) condition: a cube complex X is CAT(0) if and only if X is simply connected and the links of vertices are flag simplicial complexes. Now, we formulate the second result of this article. It was already noticed in [16] , [23] that clique complexes of chordal graphs lead to CAT(0) simplicial complexes. Gromov called them (p. 121 of [23] ) tree-like polyhedra and also noticed to be CAT(0). In the rest of this section, we prove Theorem 2. if and only if the distance function f (t ) = d(α(t ), β(t )) The proof of Theorem 2 uses the decomposition scheme from Theorem 1 and runs in three steps: first we show that a PE simplicial complex derived from the clique complex of a chordal graph is CAT(0), then we establish that the prism complex of a Cartesian product of chordal graphs is CAT(0) as well, and finally we show that gated amalgams of cage-amalgamation graphs preserve the CAT(0) property of their prism complexes. The proof employs the following known property of CAT(0) spaces due to Reshetnyak and which is a particular case of the basic gluing theorem 11.1 of [12] . if and only if the distance function f (t ) = d(α(t ), β(t )) Gluing Theorem. if and only if the distance function f (t ) = d(α(t ), β(t )) We first recall the proof of Corollary 8.4 of [16] showing that any simplicial complex X(G) derived from the clique complex of a finite chordal graph G is CAT(0). We recall this short proof here because the proof of Theorem 2 is based on the same principle. We proceed by induction on the number of vertices of G. Let x be a simplicial vertex of G. Then x belongs to the unique maximal by inclusion simplex σ of X(G) induced by x and all its neighbors in G. Consequently, X(G) can be obtained by gluing σ and X , where X is the subcomplex of X(G) spanned by the facet σ of σ not containing x (i.e., by link(x, X(G)) and the maximal simplexes of X(G) distinct from σ (in fact, X is a simplicial complex derived from the clique complex of the chordal graph G := G − {x}). Since the gluing is performed along a convex set σ of both complexes σ and X , from the result of Reshetnyak mentioned above, we obtain that X(G) is CAT(0) if and only if σ and X are CAT(0). Since X = X(G ) and the graph G is chordal, by the induction assumption, X is CAT(0), and we are done. In view of perfect elimination schemes of chordal graphs G, X(G) can be written as a directed union n i=1 X i where X i = X i−1 ∪ σ i and the simplex σ i meets X i−1 over a single face σ i . Now suppose that G is a cage-amalgamation graph whose prime graphs are the chordal graphs G 1 , . . . , G m . Each of these graphs occurs as a gated subgraph of G. Let x be a simplicial vertex of G 1 . Denote by σ x the unique maximal by inclusion simplex of X(G 1 ) induced by x and all its neighbors in G 1 and let σ x be the facet of σ x not containing the vertex x. For each vertex a of G 1 , denote by W a its fiber in G relative to some copy of the gated subgraph G 1 . From Lemma 5, each such fiber W a is gated. From Lemmas 7 and 8, we conclude that the boundaries U a of these fibers W a are isomorphic gated subgraphs of G. Denote by H σ x (resp. H σ x ) the prism complexes of the subgraphs of G induced by the unions a∈σ x U a (resp. a∈σ x U a ). Notice that H σ x is a subcomplex of H σ x and that both H σ x and H σ x are subcomplexes of H(G). Lemma 9. If p, q are two points of H σ x , then any geodesic connecting p and q in Proof. Suppose by way of contradiction that such a geodesic γ (p, q) contains a point in the set H σ x − H σ x (see Fig. 6 for an illustration). Let π 1 , . . . , π k be the maximal by inclusion prisms of H σ x intersected by γ (p, q) labeled in order in which they are traversed by γ (p, q). Let π i be the facet of Lemma 9. If p, q are two points of H σ x , then any geodesic connecting p and q in The intersection of any two consecutive prisms π i and π i+1 is a face τ i of each of them. Let τ i denote the facet of τ i in π i (and π i+1 ). Let r i ∈ γ (p, q) ∩ τ i . The orthogonal projection of each prism π i on its facet π i is a nonexpansive map f i . Moreover, each point r i is mapped by f i and f i+1 to the same point r i belonging to τ i . As a result, the length of the path γ (p, q) between p = r 0 and q = r k consisting of line segments connecting the consecutive points p, r 1 , r 2 , . . . , r k−1 , q is at most the length of γ (p, q). Since p, q ∈ H σ x and γ (p, q) passes via a point of H σ x − H σ x , at least one
{'paper_id': '6728441', 'title': 'Retracts of Products of Chordal Graphs', 's2_url': 'https://api.semanticscholar.org/CorpusID:6728441', 'source': 'S2ORC'}