Coxeter complexes and graph-associahedra

Given a graph Gamma, we construct a simple, convex polytope, dubbed graph-associahedra, whose face poset is based on the connected subgraphs of Gamma. This provides a natural generalization of the Stasheff associahedron and the Bott-Taubes cyclohedron. Moreover, we show that for any simplicial Coxeter system, the minimal blow-ups of its associated Coxeter complex has a tiling by graph-associahedra. The geometric and combinatorial properties of the complex as well as of the polyhedra are given. These spaces are natural generalizations of the Deligne-Knudsen-Mumford compactification of the real moduli space of curves. (C) 2005 Elsevier B.V. All rights reserved.