Editing Line graph (section)

== Generalizations ==

=== Medial graphs and convex polyhedra ===
{{main article|Medial graph}}
When a [[planar graph]] {{mvar|G}} has maximum [[degree (graph theory)|vertex degree]] three, its line graph is planar, and every planar embedding of {{mvar|G}} can be extended to an embedding of {{math|''L''(''G'')}}. However, there exist planar graphs with higher degree whose line graphs are nonplanar. These include, for example, the 5-star {{math|''K''{{sub|1,5}}}}, the [[gem graph]] formed by adding two non-crossing diagonals within a regular pentagon, and all [[convex polyhedron|convex polyhedra]] with a vertex of degree four or more.<ref>{{harvtxt|Sedláček|1964}}; {{harvtxt|Greenwell|Hemminger|1972}}.</ref>

An alternative construction, the [[medial graph]], coincides with the line graph for planar graphs with maximum degree three, but is always planar. 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. The medial graph of the [[dual graph]] of a plane graph is the same as the medial graph of the original plane graph.<ref>{{citation
 | last = Archdeacon | first = Dan | author-link = Dan Archdeacon
 | doi = 10.1016/0012-365X(92)90328-D
 | issue = 2
 | journal = [[Discrete Mathematics (journal)|Discrete Mathematics]]
 | mr = 1172842
 | pages = 111–141
 | title = The medial graph and voltage-current duality
 | volume = 104
 | year = 1992| doi-access = free
 }}.</ref>

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.<ref>{{citation
 | last = McKee | first = T. A.
 | contribution = Graph-theoretic model of geographic duality
 | doi = 10.1111/j.1749-6632.1989.tb22465.x
 | location = New York
 | mr = 1018637
 | pages = 310–315
 | publisher = New York Acad. Sci.
 | series = Ann. New York Acad. Sci.
 | title = Combinatorial Mathematics: Proceedings of the Third International Conference (New York, 1985)
 | volume = 555
 | year = 1989| issue = 1
 | bibcode = 1989NYASA.555..310M
 | s2cid = 86300941
 }}.</ref> This operation is known variously as the second truncation,<ref>{{citation|title=Polyhedra: A Visual Approach|first=Anthony|last=Pugh|publisher=University of California Press|year=1976|isbn=9780520030565}}.</ref> degenerate truncation,<ref>{{citation|title=Space Structures—their Harmony and Counterpoint|first=Arthur Lee|last=Loeb|edition=5th|publisher=Birkhäuser|year=1991|isbn=9783764335885}}.</ref> or [[rectification (geometry)|rectification]].<ref>{{mathworld|title=Rectification|id=Rectification}}</ref>

===Total graphs===
The total graph {{math|''T''(''G'')}} of a graph {{mvar|G}} has as its vertices the elements (vertices or edges) of {{mvar|G}}, and has an edge between two elements whenever they are either incident or adjacent. The total graph may also be obtained by subdividing each edge of {{mvar|G}} and then taking the [[Graph power|square]] of the subdivided graph.<ref>{{harvtxt|Harary|1972}}, p.&nbsp;82.</ref>

===Multigraphs===
The concept of the line graph of {{mvar|G}} may naturally be extended to the case where {{mvar|G}} is a multigraph. In this case, the characterizations of these graphs can be simplified: the characterization in terms of clique partitions no longer needs to prevent two vertices from belonging to the same to cliques, and the characterization by forbidden graphs has seven forbidden graphs instead of nine.{{sfnp|Ryjáček|Vrána|2011}}

However, for multigraphs, there are larger numbers of pairs of non-isomorphic graphs that have the same line graphs. For instance a complete bipartite graph {{math|''K''{{sub|1,''n''}}}} has the same line graph as the [[dipole graph]] and [[Shannon multigraph]] with the same number of edges. Nevertheless, analogues to Whitney's isomorphism theorem can still be derived in this case.<ref name="z97">{{harvtxt|Zverovich|1997}}</ref>

===Line digraphs{{anchor|Line digraph}}===
[[File:DeBruijn-as-line-digraph.svg|thumb|360px|Construction of the [[de Bruijn graph]]s as iterated line digraphs]]
It is also possible to generalize line graphs to directed graphs.{{sfnp|Harary|Norman|1960}} If {{mvar|G}} is a directed graph, its '''directed line graph''' or '''line digraph''' has one vertex for each edge of {{mvar|G}}. Two vertices representing directed edges from {{mvar|u}} to {{mvar|v}} and from {{mvar|w}} to {{mvar|x}} in {{mvar|G}} are connected by an edge from {{mvar|uv}} to {{mvar|wx}} in the line digraph when {{math|1=''v'' = ''w''}}. That is, each edge in the line digraph of {{mvar|G}} represents a length-two directed path in {{mvar|G}}.  The [[de Bruijn graph]]s may be formed by repeating this process of forming directed line graphs, starting from a [[complete graph|complete directed graph]].{{sfnp|Zhang|Lin|1987}}

===Weighted line graphs===
In a line graph {{math|''L''(''G'')}}, each vertex of degree {{mvar|k}} in the original graph {{mvar|G}} creates {{math|''k''(''k'' − 1)/2}} edges in the line graph.  For many types of analysis this means high-degree nodes in {{mvar|G}} are over-represented in the line graph {{math|''L''(''G'')}}.  For instance, consider a [[random walk]] on the vertices of the original graph {{mvar|G}}.  This will pass along some edge {{mvar|e}} with some frequency {{mvar|f}}. On the other hand, this edge {{mvar|e}} is mapped to a unique vertex, say {{mvar|v}}, in the line graph {{math|''L''(''G'')}}.  If we now perform the same type of random walk on the vertices of the line graph, the frequency with which {{mvar|v}} is visited can be completely different from ''f''.  If our edge {{mvar|e}} in {{mvar|G}} was connected to nodes of degree {{math|''O''(''k'')}}, it will be traversed {{math|''O''(''k''{{sup|2}})}} more frequently in the line graph {{math|''L''(''G'')}}.  Put another way, the Whitney graph isomorphism theorem guarantees that the line graph almost always encodes the topology of the original graph {{mvar|G}} faithfully but it does not guarantee that dynamics on these two graphs have a simple relationship.  One solution is to construct a weighted line graph, that is, a line graph with [[Weighted graph|weighted edges]].  There are several natural ways to do this.{{sfnp|Evans|Lambiotte|2009}} For instance if edges {{mvar|d}} and {{mvar|e}} in the graph {{mvar|G}} are incident at a vertex {{mvar|v}} with degree {{mvar|k}}, then in the line graph {{math|''L''(''G'')}} the edge connecting the two vertices {{mvar|d}} and {{mvar|e}} can be given weight {{math|1/(''k'' − 1)}}.  In this way every edge in {{mvar|G}} (provided neither end is connected to a vertex of degree 1) will have strength 2 in the line graph {{math|''L''(''G'')}} corresponding to the two ends that the edge has in {{mvar|G}}. It is straightforward to extend this definition of a weighted line graph to cases where the original graph {{mvar|G}} was directed or even weighted.{{sfnp|Evans|Lambiotte|2010}}  The principle in all cases is to ensure the line graph {{math|''L''(''G'')}} reflects the dynamics as well as the topology of the original graph {{mvar|G}}.

===Line graphs of hypergraphs===
{{main article|Line graph of a hypergraph}}
The edges of a [[hypergraph]] may form an arbitrary [[family of sets]], so the [[line graph of a hypergraph]] is the same as the [[intersection graph]] of the sets from the family.

=== Disjointness graph ===
The '''disjointness graph''' of {{mvar|G}}, denoted {{math|''D''(''G'')}}, is constructed in the following way: for each edge in {{mvar|G}}, make a vertex in {{math|''D''(''G'')}}; for every two edges in {{mvar|G}} that do ''not'' have a vertex in common, make an edge between their corresponding vertices in {{math|''D''(''G'')}}.<ref>{{Cite journal|last=Meshulam|first=Roy|date=2001-01-01|title=The Clique Complex and Hypergraph Matching|journal=Combinatorica|language=en|volume=21|issue=1|pages=89–94|doi=10.1007/s004930170006|s2cid=207006642|issn=1439-6912}}</ref> In other words, {{math|''D''(''G'')}} is the [[complement graph]] of {{math|''L''(''G'')}}. A [[Clique (graph theory)|clique]] in {{math|''D''(''G'')}} corresponds to an independent set in {{math|''L''(''G'')}}, and vice versa.