MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Is this graph transformation G_1 to G_2 efficiently computable?

  1. All vertices in G_1 are unique edges in G_2
  2. Adjacent vertices in G_1 are adjacent edges in G_2

The inverse transformation (edges to vertices) is trivial.

I can encode it as CSP, but I am not sure solving is tractable:

adjacent V1,V2 in G_1 to (V1',V1''), (V2',V2'') in G_2, must share a vertex, constraints: V1'=V2' / V1'=V2'' / V1''=V2' / V1''=V2'' and some disequations.

References, search terms will be apreciated. Thank you.

share|cite|improve this question
up vote 2 down vote accepted

This is only possible if $G_1$ is the line graph of $G_2$. Not all graphs are line graphs.

A graph $G$ is the line graph of some other graph, if and only if it is possible to find a collection of cliques in $G$, partitioning the edges of $G$, such that each vertex of $G$ belongs to at most two of the cliques.

Here you can find am algorithm to recover the original graph from it's line graph.

share|cite|improve this answer
Thank you very much. – Chris Haarn Sep 14 '10 at 14:04

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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