Medial graph

A plane graph (in blue) and its medial graph (in red).

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.

Formal definition

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.

Properties

The two red graphs are both medial graphs of the blue graph, but they are not isomorphic.

• Since the medial graph depends on a particular embedding, the medial graph of a planar graph is not unique in the sense that 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.
• In the other direction, non-isomorphic graphs can have the same medial graph. In particular, a plane graph and its dual graph have the same medial graph.
• Medial graphs are 4-regular graphs.
• 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 only other graph with the same medial graph as a given plane graph is its dual.^[1]

Applications

For a plane graph G, twice the evaluation of the Tutte polynomial at the point (3,3) 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 (that is, the number of vertices with incident edges cyclicly ordered "in, out, in out").^[2] 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

A plane graph (in blue) and its directed medial graph (in red).

The medial graph definition can 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 boarded by one black face and one white face. Then each edge is orientated so that the black face is on its left.

A plane graph and its dual do not have the same directed medial graph since 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 (3,3). For a plane graph G, n times the evaluation of the Tutte polynomial at the point (n+1,n+1) equals the weighted sum over all edge colorings using n colors in the directed medial graph of G so that each (possibly empty) 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.^[3]

See also

• Line graph
• Knots and graphs
• Tait graph
• Rectification (geometry) - The equivalent operation on polyhedrons

References

• Brylawski, Thomas; Oxley, James (1992). "The Tutte Polynomial and Its Applications". In White, Neil. Matriod Applications. Cambridge University Press. pp. 123–225.