# Is the graph transformation vertices to edges efficiently computable?

Is this graph transformation G_1 to G_2 efficiently computable?

1. All vertices in G_1 are unique 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.

-

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.