[Math] Transform Node-Labeled Graph to equivalent Edge-Labeled

graph theory

Given a Node-Labeled graph, i.e., a graph where only vertices have labels, I would like to create an equivalent Edge-Labeled graph, i.e., a graph where only edges have labels.

I know how to do the opposite.
In particular, given an edge-labeled node-unlabeled graph, I can transform each labeled edge (with unlabeled source and destination) to a pair of edges with a new node, where the original source and destination nodes have a default NIL label, the new node has label the original edge-label, and the edge (s)-label-(d) becomes the pair of edges (s)--(label) and (label)--(d).

Best Answer

From the various comments, here is the possible solutions I've found:

1) Construct the corresponding Line Graph, informally meaning:

  • For each edge (u,v) create a new node n(u,v) (label for the node is the edge label

  • For each new node, connect it to all other new nodes that have the same incident node in the original graph (in practice each node in the graph is transformed into a clique)

    (by @bob-krueger)

1.1) Pros/Cons

  • Number of Nodes in the new graphs = Number of Edges in the original
  • A great number of cliques is created
  • Number of labels stays the same
  • Theoretically sound and well understood

2) Transfer Node labels directly onto Edges

  • Given that each vertex v is labeled by a label l(v)
  • label each edge (v,u) by a pair (l(v),l(u))

  • (in practice one can concatenate strings)

    (by @alex-ravsky)

2.1) Pros/Cons

  • Graph structure is preserved (Nodes/Edges)
  • Works with undirected graphs
  • Number of labels is now $|L|^2$

2bis) Transfer Node labels directly onto Edges, preserve direction

** this is only for node labeled, edge directed graphs. **

  • Same as above, but
  • Given that each vertex v is labeled by a label l(v) , and
  • Each edge is a tuple ${\langle}v,u{\rangle} \neq {\langle}u,v{\rangle}$
  • label each edge ${\langle}v,u{\rangle}$ by the single l(v)

2.1) Pros/Cons

  • Graph structure is preserved (Nodes/Edges)
  • Works with undirected graphs
  • Number of labels still the same $|L|$
Related Question