Editing Line graph (section)

=== 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>