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, The genus of certain graphs, Ph.D. dissertation, Ohio State University, 1978.
- 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, On the non-orientable genus of a $2$-connected graph, J. Combin. Theory Ser. B 43 (1987), 48-59.
- 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 —, Graph minors: VIII. A Kuratowski theorem for general surfaces, submitted. —, Graph minors: XV. Wagner’s conjecture, submitted.
- 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 —, Combinatorial geometries, Encycl. of Math. and Its Appl., vol. 29, Cambridge Univ. Press, Cambridge, Eng., 1987. MR 88g:05048.
- 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$-isomorphic graphs, Amer. J. Math. 55 (1933), 245-254.
- 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
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