Medial graph

In the mathematical discipline of graph theory, the medial graph of plane graph G is another graph M(G) that represents the adjacencies between edges in the faces of G. Medial graphs were introduced in 1922 by Ernst Steinitz to study combinatorial properties of convex polyhedra, although the inverse construction was already used by Peter Tait in 1877 in his foundational study of knots and links. Given a connected plane graph G, its medial graph M(G) has a vertex for each edge of G and an edge between two vertices for each face of G in which their corresponding edges occur consecutively. The medial graph of a disconnected graph is the disjoint union of the medial graphs of each connected component. The definition of medial graph also extends without modification to graph embeddings on surfaces of higher genus. The medial graph of any plane graph is a 4-regular plane graph. For any plane graph G, the medial graph of G and the medial graph of the dual graph of G are isomorphic. Conversely, for any 4-regular plane graph H, the only two plane graphs with medial graph H are dual to each other. Since the medial graph depends on a particular embedding, the medial graph of a planar graph is not unique; the same planar graph can have non-isomorphic medial graphs. In the picture, the red graphs are not isomorphic because the two vertices with self loops share an edge in one graph but not in the other. Every 4-regular plane graph is the medial graph of some plane graph. For a connected 4-regular plane graph H, a planar graph G with H as its medial graph can be constructed as follows. Color the faces of H with just two colors, which is possible since H is Eulerian (and thus the dual graph of H is bipartite). The vertices in G correspond to the faces of a single color in H. These vertices are connected by an edge for each vertex shared by their corresponding faces in H. Note that performing this construction using the faces of the other color as the vertices produces the dual graph of G. The medial graph of a 3-regular plane graph coincides with its line graph.