and described linear time algorithms for recognizing line graphs and reconstructing their original graphs. generalized these methods to directed graphs. described an efficient data structure for maintaining a dynamic graph, subject to vertex insertions and deletions, and maintaining a representation of the input as a line graph (when it exists) in time proportional to the number of changed edges at each step.