In the

mathematical Mathematics is an area of knowledge that includes the topics of numbers, formulas and related structures, shapes and the spaces in which they are contained, and quantities and their changes. These topics are represented in modern mathematics ...

discipline of

graph theory In mathematics, graph theory is the study of ''graphs'', which are mathematical structures used to model pairwise relations between objects. A graph in this context is made up of '' vertices'' (also called ''nodes'' or ''points'') which are conne ...

, the medial graph of

plane graph In graph theory, a planar graph is a graph that can be embedded in the plane, i.e., it can be drawn on the plane in such a way that its edges intersect only at their endpoints. In other words, it can be drawn in such a way that no edges cross ...

''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 Ernst Steinitz (13 June 1871 – 29 September 1928) was a German mathematician. Biography Steinitz was born in Laurahütte (Siemianowice Śląskie), Silesia, Germany (now in Poland), the son of Sigismund Steinitz, a Jewish coal merchant, and ...

to study combinatorial properties of

convex polyhedra A convex polytope is a special case of a polytope, having the additional property that it is also a convex set contained in the n-dimensional Euclidean space \mathbb^n. Most texts. use the term "polytope" for a bounded convex polytope, and the wo ...

, although the inverse construction was already used by

Peter Tait Peter Tait may refer to: * Peter Tait (physicist) (1831–1901), Scottish mathematical physicist * Peter Tait (footballer) (1936–1990), English professional footballer * Peter Tait (mayor) (1915–1996), New Zealand politician * Peter Tait (radio ...

in 1877 in his foundational study of knots and links.

Formal definition

Given a connected

''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.

Properties

* 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 In the mathematical discipline of graph theory, the dual graph of a plane graph is a graph that has a vertex for each face of . The dual graph has an edge for each pair of faces in that are separated from each other by an edge, and a self-loop ...

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 In mathematics, an isomorphism is a structure-preserving mapping between two structures of the same type that can be reversed by an inverse mapping. Two mathematical structures are isomorphic if an isomorphism exists between them. The word is ...

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 In the mathematical discipline of graph theory, the line graph of an undirected graph is another graph that represents the adjacencies between edges of . is constructed in the following way: for each edge in , make a vertex in ; for every ...

. However, this is not true for medial graphs of plane graphs that have vertices of degree greater than three.

Applications

For a plane graph ''G'', twice the evaluation of the

Tutte polynomial The Tutte polynomial, also called the dichromate or the Tutte–Whitney polynomial, is a graph polynomial. It is a polynomial in two variables which plays an important role in graph theory. It is defined for every undirected graph G and contai ...

at the point (3,3) equals the sum over weighted

Eulerian orientation In graph theory, an Eulerian trail (or Eulerian path) is a trail in a finite graph that visits every edge exactly once (allowing for revisiting vertices). Similarly, an Eulerian circuit or Eulerian cycle is an Eulerian trail that starts and ends ...

s 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 cyclically ordered "in, out, in out"). 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 In linear algebra, the transpose of a matrix is an operator which flips a matrix over its diagonal; that is, it switches the row and column indices of the matrix by producing another matrix, often denoted by (among other notations). The tr ...

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

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.

Formal definition

Properties

Applications

Directed medial graph

See also

References

Further reading