Line graph

The name line graph comes from a paper by Harary & Norman (1960) although both Whitney (1932) and Krausz (1943) used the construction before this.

Line graphs are characterized by nine forbidden subgraphs and can be recognized in linear time.

For instance, the green vertex on the right labeled 1,3 corresponds to the edge on the left between the blue vertices 1 and 3.

Green vertex 1,3 is adjacent to three other green vertices: 1,4 and 1,2 (corresponding to edges sharing the endpoint 1 in the blue graph) and 4,3 (corresponding to an edge sharing the endpoint 3 in the blue graph).

[11] Analogues of the Whitney isomorphism theorem have been proven for the line graphs of multigraphs, but are more complicated in this case.

[13] They may also be characterized (again with the exception of K8) as the strongly regular graphs with parameters srg(n(n – 1)/2, 2(n – 2), n – 2, 4).

When both sides of the bipartition have the same number of vertices, these graphs are again strongly regular.

[18] Equivalently, a graph is line perfect if and only if each of its biconnected components is either bipartite or of the form K4 (the tetrahedron) or K1,1,n (a book of one or more triangles all sharing a common edge).

Given such a family of cliques, the underlying graph G for which L is the line graph can be recovered by making one vertex in G for each clique, and an edge in G for each vertex in L with its endpoints being the two cliques containing the vertex in L. By the strong version of Whitney's isomorphism theorem, if the underlying graph G has more than four vertices, there can be only one partition of this type.

In the example above, the four topmost vertices induce a claw (that is, a complete bipartite graph K1,3), shown on the top left of the illustration of forbidden subgraphs.

For graphs with minimum degree at least 5, only the six subgraphs in the left and right columns of the figure are needed in the characterization.

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.

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: Each step either takes constant time, or involves finding a vertex cover of constant size within a graph S whose size is proportional to the number of neighbors of 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.

These include, for example, the 5-star K1,5, the gem graph formed by adding two non-crossing diagonals within a regular pentagon, and all convex polyhedra with a vertex of degree four or more.

It has the same vertices as the line graph, but potentially fewer edges: two vertices of the medial graph are adjacent if and only if the corresponding two edges are consecutive on some face of the planar embedding.

[30] For regular polyhedra or simple polyhedra, the medial graph operation can be represented geometrically by the operation of cutting off each vertex of the polyhedron by a plane through the midpoints of all its incident edges.

[35] The concept of the line graph of G may naturally be extended to the case where G is a multigraph.

For many types of analysis this means high-degree nodes in G are over-represented in the line graph L(G).

For instance, consider a random walk on the vertices of the original graph G. This will pass along some edge e with some frequency f. On the other hand, this edge e is mapped to a unique vertex, say v, in the line graph L(G).

If we now perform the same type of random walk on the vertices of the line graph, the frequency with which v is visited can be completely different from f. If our edge e in G was connected to nodes of degree O(k), it will be traversed O(k2) more frequently in the line graph L(G).