Question

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.

Answer 1

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.