## Matroids determine the embeddability of graphs in surfaces

HTML articles powered by AMS MathViewer

- by Thomas Zaslavsky PDF
- Proc. Amer. Math. Soc.
**106**(1989), 1131-1135 Request permission

## Abstract:

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.## References

- Dan Archdeacon and Phil Huneke,
*A Kuratowski theorem for nonorientable surfaces*, J. Combin. Theory Ser. B**46**(1989), no. 2, 173–231. MR**992991**, DOI 10.1016/0095-8956(89)90043-9 - Joseph Battle, Frank Harary, and Yukihiro Kodama,
*Every planar graph with nine points has a nonplanar complement*, Bull. Amer. Math. Soc.**68**(1962), 569–571. MR**155314**, DOI 10.1090/S0002-9904-1962-10850-7
R. W. Decker, - R. W. Decker, H. H. Glover, and J. P. Huneke,
*Computing the genus of the $2$-amalgamations of graphs*, Combinatorica**5**(1985), no. 4, 271–282. MR**845136**, DOI 10.1007/BF02579241 - Richard A. Duke,
*The genus, regional number, and Betti number of a graph*, Canadian J. Math.**18**(1966), 817–822. MR**196731**, DOI 10.4153/CJM-1966-081-6 - Jack Edmonds,
*On the surface duality of linear graphs*, J. Res. Nat. Bur. Standards Sect. B**69B**(1965), 121–123. MR**182962** - Henry H. Glover, John P. Huneke, and Chin San Wang,
*103 graphs that are irreducible for the projective plane*, J. Combin. Theory Ser. B**27**(1979), no. 3, 332–370. MR**554298**, DOI 10.1016/0095-8956(79)90022-4 - Jonathan L. Gross and Thomas W. Tucker,
*Topological graph theory*, Wiley-Interscience Series in Discrete Mathematics and Optimization, John Wiley & Sons, Inc., New York, 1987. A Wiley-Interscience Publication. MR**898434**
B. Richter, - R. Bruce Richter,
*On the Euler genus of a $2$-connected graph*, J. Combin. Theory Ser. B**43**(1987), no. 1, 60–69. MR**897240**, DOI 10.1016/0095-8956(87)90030-X - Neil Robertson and P. D. Seymour,
*Generalizing Kuratowski’s theorem*, Proceedings of the fifteenth Southeastern conference on combinatorics, graph theory and computing (Baton Rouge, La., 1984), 1984, pp. 129–138. MR**777718**
—, - Saul Stahl,
*Generalized embedding schemes*, J. Graph Theory**2**(1978), no. 1, 41–52. MR**485488**, DOI 10.1002/jgt.3190020106 - Saul Stahl and Lowell W. Beineke,
*Blocks and the nonorientable genus of graphs*, J. Graph Theory**1**(1977), no. 1, 75–78. MR**460165**, DOI 10.1002/jgt.3190010114 - W. T. Tutte,
*Lectures on matroids*, J. Res. Nat. Bur. Standards Sect. B**69B**(1965), 1–47. MR**179781** - D. J. A. Welsh,
*Matroid theory*, L. M. S. Monographs, No. 8, Academic Press [Harcourt Brace Jovanovich, Publishers], London-New York, 1976. MR**0427112** - Neil White (ed.),
*Theory of matroids*, Encyclopedia of Mathematics and its Applications, vol. 26, Cambridge University Press, Cambridge, 1986. MR**849389**, DOI 10.1017/CBO9780511629563
—, - Hassler Whitney,
*Non-separable and planar graphs*, Trans. Amer. Math. Soc.**34**(1932), no. 2, 339–362. MR**1501641**, DOI 10.1090/S0002-9947-1932-1501641-2
—, $2$ - Nguyen Huy Xuong,
*How to determine the maximum genus of a graph*, J. Combin. Theory Ser. B**26**(1979), no. 2, 217–225. MR**532589**, DOI 10.1016/0095-8956(79)90058-3

*The genus of certain graphs*, Ph.D. dissertation, Ohio State University, 1978.

*On the non-orientable genus of a*$2$

*-connected graph*, J. Combin. Theory Ser. B

**43**(1987), 48-59.

*Graph minors*: VIII.

*A Kuratowski theorem for general surfaces*, submitted. —,

*Graph minors*: XV.

*Wagner’s conjecture*, submitted.

*Combinatorial geometries*, Encycl. of Math. and Its Appl., vol. 29, Cambridge Univ. Press, Cambridge, Eng., 1987. MR 88g:05048.

*-isomorphic graphs*, Amer. J. Math.

**55**(1933), 245-254.

## Additional Information

- © Copyright 1989 American Mathematical Society
- Journal: Proc. Amer. Math. Soc.
**106**(1989), 1131-1135 - MSC: Primary 05C10; Secondary 05B35
- DOI: https://doi.org/10.1090/S0002-9939-1989-0979055-7
- MathSciNet review: 979055