2
$\begingroup$

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).

$\endgroup$
6
  • $\begingroup$ What does "equivalent" mean to you here? $\endgroup$ Aug 4, 2017 at 11:23
  • 1
    $\begingroup$ Have you heard of the line graph: en.wikipedia.org/wiki/Line_graph? $\endgroup$ Aug 4, 2017 at 15:00
  • $\begingroup$ For equivalent I mean, for example, that I can solve subgraph-isomorphism on one and get the same answer on the corresponding transformed graph. $\endgroup$
    – Kuzeko
    Aug 4, 2017 at 18:57
  • $\begingroup$ I was not aware of Line graphs. Taking a look right now, thanks! $\endgroup$
    – Kuzeko
    Aug 4, 2017 at 18:58
  • $\begingroup$ Given that each vertex $v$ is labeled by a label $l(v)$ we can label each edge $(v,u)$ by a pair $(l(v), l(u))$. $\endgroup$ Aug 8, 2017 at 1:20

1 Answer 1

2
$\begingroup$

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|$
$\endgroup$

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.