I'm currently documenting an algorithm which involves deleting a node in a directed dependency graph while maintaining the implied dependencies between its parents and children.

Take for example the following graph:

Before and after node deletion

Edges are added from all parents to children before node X is deleted to ensure that the implied dependencies are maintained.

Question: Is there a standard terminology for such an operation?

Update: Thanks to a change in my algorithm, node X is now guaranteed to have only one parent. This reduces the above operation to a simple node contraction with the parent. While my immediate problem is now solved, I'm leaving the question open and unanswered as I'm still curios to know the solution had my requirements not changed.

  • 1
    $\begingroup$ I would just say "the successors of $X$ are added as children of the predecessors of $X$, and $X$ is removed." It's a little cumbersome I guess. $\endgroup$ – nullUser Aug 15 '12 at 14:26
  • $\begingroup$ What ever happened with this? Did you ever find what you were looking for? $\endgroup$ – mikeazo Jan 12 '15 at 19:51

bipartite or multimodal projection


The Wikipedia page on graph subdivision refers to this procedure as smoothing. They restrict it to vertices of degree 2 (in which case the old graph was a subdivision of the new graph), so this might not be an exact fit.

A related procedure is edge contraction; that page also mentions vertex contraction, but that is different from what is called for here.

  • $\begingroup$ Thanks Nate. I had previously considered using the term "vertex contraction" but as you mentioned that does not quite fit the bill. "Smoothing" is close, but as I'm dealing with vertices of degree >2 it would not apply. $\endgroup$ – Shawn Chin Aug 15 '12 at 14:49
  • 1
    $\begingroup$ This operation (for undirected graphs) came up naturally as part of my research into Graph Domination; we used the name vertex contraction and the notation G/v: (arxiv.org/abs/1206.5926). The only other place I found the concept used this notation too and was by Matthew Walsh: ijmcs.future-in-tech.net/R-Walsh+.pdf $\endgroup$ – jp26 Aug 15 '12 at 20:03
  • $\begingroup$ That's interesting, thanks @jp26. I can certainly see that being applicable for undirected graphs. I'm wary about using the name vertex contraction as it has other definitions which are not completely applicable in my case. $\endgroup$ – Shawn Chin Aug 16 '12 at 9:13
  • 1
    $\begingroup$ For me the other concept is vertex identification. For a new name, how about vertex subsumption? Colligation is an apt word, but it is more about the rejoining, and doesn't mention the removal of the vertex... $\endgroup$ – jp26 Aug 16 '12 at 15:18
  • $\begingroup$ @jp26 vertex subsumption... I like that. $\endgroup$ – Shawn Chin Sep 3 '12 at 12:42

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.