A dynamic algorithm for line graph recognition

For a graph G=(V, E) its line graph L(G) has the node set E and two nodes of L(G) are adjacent if the corresponding edges of G have a common endpoint. The problem of finding G for a given L was already optimally solved by Lehot[7] and Roussopoulos[11]. Here we present a new dynamic solution to this problem, where we can add or delete a node v in L(G) in time proportional to the size of its adjacency list.