# What is this combinatorial operation on cell complexes?

I am considering the following transformation on two-dimensional cell-complexes—aka polyhedral surfaces. (It can be defined in higher dimension, but I only care about dimension two.) Since it is obvious, I suppose it is well-known, and I would like to know what its name is.

Assuming no boundary,

• each edge is doubled, i.e. replaced by a pair of edges,
• each vertex is replaced by $d$ vertices, where $d$ is the vertex’ degree
• extra faces are added between pairs of edges and at each blown vertex.

Here's an example with the tetrahedron (where the outside represents the fourth face):

Note that this transformation is not exactly a subdivision since some of the previous elements (edges and vertices) are not preserved. It may pictured and realized for a convex polyhedron $K$ by a scraping operation, slicing by a plane at each vertex and along each edge. Or, more mathematically, by interpolating between $K$ and its polar $K^\circ$.

Has anybody met this operation?

It seems to go by the name of cantellation or expansion.

• Thanks. That definitely gives a name (two actually) to the operation on polytopes. I still wonder whether and how it is used in a purely combinatorial setup. – Pascal Romon Mar 3 '17 at 14:57

This is the GEM (graph-encoded maps), a representation of surface-embedded graphs described in the book Topological Graph Theory (Bonnington & Little, 1995). Every flag of the original embedding (an incident triple of vertex-edge-face) becomes a vertex in the new graph, and each vertex in the new graph has exactly three edges representing the three different ways that one can substitute one of the three things in the triple for a different thing of the same type.

Update (see comments): this is not the GEM, because it has only one vertex for each vertex-face incidence of the original map, while the GEM has two (one for each edge at the incidence). It can be constructed from the GEM by contracting the GEM edges connecting pairs of flags with the same vertex and face as each other.

• That is interesting, and more combinatorial. I couldn't get my hand on Topological Graph Theory, only on Lins' Graph-Encoded Maps, and I see how the construction of GEMs involves my combinatorial operation. But it seems a bit different; in particular the new graph is cubic (the old vertices give rise to faces of degree $2 d$. – Pascal Romon Mar 3 '17 at 14:55
• Oops, you're right, the GEM uses $2d$ new vertices per old degree-$d$ vertex, not $d$ as in your figure. Your figure can be constructed from the GEM by contracting the edges that connect two flags with the same vertex and face and different edges. So you have a vertex for each vertex-face incidence of the original map, not for each flag. – David Eppstein Mar 4 '17 at 0:47

This operation is called "complete truncation" in

Lee, Carl W., Sweeping the cd-index and the toric $h$-vector, Electron. J. Comb. 18, No. 1, Research Paper P66, 20 p. (2011). ZBL1216.52009.

Note that complete truncation is dual to the barycentric subdivision: The complete truncation of $P$ is $(\mathrm{sd}(P^*))^*$, where $\mathrm{sd}$ is the barycentric subdivision, and $^*$ denotes the combinatorial dual.

• Thanks Ivan, it makes sense. But my remark above on @j-c 's answer still holds: it's more polytope oriented than combinatorial. – Pascal Romon Mar 27 '17 at 9:12
• Yes, "truncation" has a certain geometric context. Actually, although Lee defines it for polytopes, he uses poset terminology speaking about chains (totally ordered subsets of the incidence lattice). In my opinion, "cobarycentric subdivision" could be a good name. – Ivan Izmestiev Mar 27 '17 at 13:56