Matroids determine the embeddability of graphs in surfaces
Thomas Zasĺavsky · Proceedings of the American Mathematical Society · 1989
The embeddability of a graph in a given surface is determined entirely by the polygon matroid of the graph. That is also true for cellular embeddability in nonorientable surfaces but not in orientable surfaces.