4
$\begingroup$

I am wondering if there is a name for a graph transformation that involves splitting up vertices in a directed graph into multiple vertices (one for each incoming and one for each outgoing edge of the original vertex), and then adding edges between these split up vertices in order to create an edge for each possible 'turn' in the original graph while still maintaining the original edges of the graph.

A simple algorithm for applying this transformation to a graph $G(E,V)$ would go as follows:

  • For each vertex $v$ in $G$ create a line graph using the edges that are connected to $v$
  • For each edge $e$ in $G$ add an edge $e'$ between the two line graphs that were created using the vertices in the original graph that connect to $e$.
    • $e'$ is placed between the two vertices in the new line graphs that were created from $e$

Below is a visual representation of this graph transformation done on a small graph:

Original Graph

Transformed Graph

$\endgroup$
  • $\begingroup$ I didn't quite understand your description, and in your example, only one of the vertices is split, but I suspect line graph is what you are looking for. $\endgroup$ – Blackbird Oct 17 '17 at 19:15
  • $\begingroup$ The result of the transform is that every vertex has either in-degree or out-degree of $1$. Do you know if these types of vertices have a special name? I would be tempted to called them distributors and collectors. Maybe we could coin a term for the action as "mediation"? $\endgroup$ – Joffan Oct 17 '17 at 19:24
  • 1
    $\begingroup$ @Blackbird It does look like vertices 6a,6b,6c,6d and the edges that connect them form the line graph of the original graph, but this transformation also has all of the edges from the original graph to connect the clusters of "line graphs" that are created. $\endgroup$ – atasca10 Oct 17 '17 at 20:10

Your Answer

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

Browse other questions tagged or ask your own question.