Editing Line graph (section)

===Algorithms===
{{harvtxt|Roussopoulos|1973}} and {{harvtxt|Lehot|1974}} described linear time algorithms for recognizing line graphs and reconstructing their original graphs. {{harvtxt|Sysło|1982}} generalized these methods to [[directed graph]]s. {{harvtxt|Degiorgi|Simon|1995}} 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.

The algorithms of {{harvtxt|Roussopoulos|1973}} and {{harvtxt|Lehot|1974}} are based on characterizations of line graphs involving odd triangles (triangles in the line graph with the property that there exists another vertex adjacent to an odd number of triangle vertices). However, the algorithm of {{harvtxt|Degiorgi|Simon|1995}} uses only Whitney's isomorphism theorem.  It is complicated by the need to recognize deletions that cause the remaining graph to become a line graph, but when specialized to the static recognition problem only insertions need to be performed, and the algorithm performs the following steps:
*Construct the input graph {{mvar|L}} by adding vertices one at a time, at each step choosing a vertex to add that is adjacent to at least one previously-added vertex. While adding vertices to {{mvar|L}}, maintain a graph {{mvar|G}} for which {{math|1=''L'' = ''L''(''G'')}}; if the algorithm ever fails to find an appropriate graph {{mvar|G}}, then the input is not a line graph and the algorithm terminates.
*When adding a vertex {{mvar|v}} to a graph {{math|''L''(''G'')}} for which {{mvar|G}} has four or fewer vertices, it might be the case that  the line graph representation is not unique. But in this case, the augmented graph is small enough that a representation of it as a line graph can be found by a [[brute force search]] in constant time.
*When adding a vertex {{mvar|v}} to a larger graph {{mvar|L}} that equals the line graph of another graph {{mvar|G}}, let {{mvar|S}} be the subgraph of {{mvar|G}} formed by the edges that correspond to the neighbors of {{mvar|v}} in {{mvar|L}}. Check that {{mvar|S}} has a [[vertex cover]] consisting of one vertex or two non-adjacent vertices. If there are two vertices in the cover, augment {{mvar|G}} by adding an edge (corresponding to {{mvar|v}}) that connects these two vertices. If there is only one vertex in the cover, then add a new vertex to {{mvar|G}}, adjacent to this vertex.
Each step either takes constant time, or involves finding a vertex cover of constant size within a graph {{mvar|S}} whose size is proportional to the number of neighbors of {{mvar|v}}. Thus, the total time for the whole algorithm is proportional to the sum of the numbers of neighbors of all vertices, which (by the [[handshaking lemma]]) is proportional to the number of input edges.