Light subgraphs of graphs embedded in the plane—A survey

It is well known that every planar graph contains a vertex of degree at most 5. A theorem of Kotzig states that every 3-connected planar graph contains an edge whose endvertices have degree-sum at most 13. Fabrici and Jendrol’ proved that every 3-connected planar graph GG that contains a kk-vertex path contains also a kk-vertex path PP such that every vertex of PP has degree at most 5k5k. A result by Enomoto and Ota says that every 3-connected planar graph GG of order at least kk contains a connected subgraph HH of order kk such that the degree sum of vertices of HH in GG is at most 8k−18k−1. Motivated by these results, a concept of light graphs has been introduced. A graph HH is said to be light in a family GG of graphs if at least one member of GG contains a copy of HH and there is an integer w(H,G)w(H,G) such that each member GG of GG with a copy of HH also has a copy KK of HH such that ∑v∈V(K)degG(v)≤w(H,G)∑v∈V(K)degG(v)≤w(H,G).In this paper we present a survey of results on light graphs in different families of plane graphs and multigraphs. A similar survey dealing with the family of all graphs embedded in surfaces other than the sphere was prepared as well.