An Optimal Algorithm to Detect a Line Graph and Output Its Root Graph
Philippe G. H. Lehot · Journal of the ACM · 1974
Given a graph H with E edges and N nodes, a graph G is sought such that H is the line graph of G , if G exists. The algorithm does this within the order of E steps, in fact in E + O ( N ) steps. This algorithm is optimal in its complexity.