The Wikipedia page on graph homeomorphism describes an opposite operation of edge subdivision that it calls smoothing.

What is the customary name of this operation in mathematics? Is there a name for the graph obtained by performing "smoothing" repeatedly as many times as possible?

I have seen the term subdivision used in many places, but I have not seen the term smoothing anywhere else than on Wikipedia.

In particular, I am looking for a good name to use in a software package for the following operation: perform smoothing as many times as possible (thus removing all degree-2 vertices). Is smoothen a reasonable name for this operation, that would feel natural to a mathematician?

  • $\begingroup$ Suppression is the word, well, the only one I've ever heard. $\endgroup$ – Countingstuff Apr 30 '18 at 13:42
  • $\begingroup$ @Countingstuff Searching along those lines, I also found the term topological minor. Is there a separate term for the unique smallest possible topological minor of a graph. I mean this allowing self-loops and multi-edges, i.e. for a cycle graph we'd get a single vertex graph with a self-loop. $\endgroup$ – Szabolcs Apr 30 '18 at 13:50

Wikipedia also calls it edge contraction. There is a very similar MSE question 197972 removing degree-2 vertices from a graph.

  • $\begingroup$ Edge contraction is a more general term; you can only "smooth" out a vertex of degree $2$ (which is equivalent to contracting one of its edges), but by contracting other edges you can get other behavior, too. $\endgroup$ – Misha Lavrov Apr 30 '18 at 22:36
  • $\begingroup$ You are correct. Edge contraction is a more general term. $\endgroup$ – Somos Apr 30 '18 at 22:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.