Content deleted Content added
m math formatting Tags: Mobile edit Mobile app edit iOS app edit |
m Fixed typo Tags: Mobile edit Mobile app edit iOS app edit |
||
Line 166:
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 {{
*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.
| |||