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. 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. However, this is not true for medial graphs of plane graphs that have vertices of degreegreater than three.
Applications
For a plane graph G, twice the evaluation of the Tutte polynomial at the point equals the sum over weighted Eulerian orientations in the medial graph of G, where the weight of an orientation is 2 to the number of saddle vertices of the orientation. Since the Tutte polynomial is invariant under embeddings, this result shows that every medial graph has the same sum of these weighted Eulerian orientations.
Directed medial graph
The medial graph definition can be extended to include an orientation. First, the faces of the medial graph are colored black if they contain a vertex of the original graph and white otherwise. This coloring causes each edge of the medial graph to be bordered by one black face and one white face. Then each edge is oriented so that the black face is on its left. A plane graph and its dual do not have the same directed medial graph; their directed medial graphs are the transpose of each other. Using the directed medial graph, one can effectively generalize the result on evaluations of the Tutte polynomial at. For a plane graph G, n times the evaluation of the Tutte polynomial at the point equals the weighted sum over all edge colorings using n colors in the directed medial graph of G so that each set of monochromatic edges forms a directed Eulerian graph, where the weight of a directed Eulerian orientation is 2 to the number of monochromatic vertices.
