Remote Access Proceedings of the American Mathematical Society
Green Open Access

Proceedings of the American Mathematical Society

ISSN 1088-6826(online) ISSN 0002-9939(print)

 
 

 

Matroids determine the embeddability of graphs in surfaces


Author: Thomas Zaslavsky
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
Full-text PDF

Abstract | References | Similar Articles | Additional Information

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 [Enhancements On Off] (What's this?)

  • [1] D. Archdeacon and P. Huneke, A Kuratowski theorem for nonorientable surfaces, J. Combin. Theory Ser. B 46 (1989), 173-231. MR 992991 (90f:05049)
  • [2] J. Battle, F. Harary, Y. Kodama, and J. W. T. Youngs, Additivity of the genus of a graph, Bull. Amer. Math. Soc. 68 (1962), 569-571. MR 27 #5247. MR 0155314 (27:5248)
  • [3] R. W. Decker, The genus of certain graphs, Ph.D. dissertation, Ohio State University, 1978.
  • [4] R. W. Decker, H. H. Glover, and J. P. Huneke, Computing the genus of the $ 2$-amalgamations of graphs, Combinatorica 5 (1985), 271-282. MR 87f:05054. MR 845136 (87f:05054)
  • [5] R. A Duke, The genus, regional number, and Betti number of a graph, Canad. J. Math. 18 (1966), 817-822. MR 33 #4917. MR 0196731 (33:4917)
  • [6] J. Edmonds, On the surface duality of linear graphs, J. Res. Nat. Bur. Standards (U.S.A.) Sect. B 69B (1965), 121-123. MR 32 #444. MR 0182962 (32:444)
  • [7] H. H. Glover, J. P. Huneke, and C. S. Wang, 103 graphs that are irreducible for the projective plane, J. Combin. Theory Ser. B 27 (1979), 332-370. MR 81h:05060. MR 554298 (81h:05060)
  • [8] J. L. Gross and T. W. Tucker, Topological graph theory, Wiley-Interscience, New York, 1987. MR 898434 (88h:05034)
  • [9] B. Richter, On the non-orientable genus of a $ 2$-connected graph, J. Combin. Theory Ser. B 43 (1987), 48-59.
  • [10] -, On the Euler genus of a $ 2$-connected graph, J. Combin. Theory Ser. B 43 (1987), 60-69. MR 897240 (88g:05055)
  • [11] N. Robertson and P. D. Seymour, Generalizing Kuratowski's theorem, in Proc. Fifteenth Southeastern Conf. on Combinatorics, Graph Theory and Computing (Baton Rouge, 1984), Congressus Numerantium 45 (1984), 129-138. MR 86f:05058. MR 777718 (86f:05058)
  • [12] -, Graph minors: VIII. A Kuratowski theorem for general surfaces, submitted.
  • [13] -, Graph minors: XV. Wagner's conjecture, submitted.
  • [14] S. Stahl, Generalized embedding schemes, J. Graph Theory 2 (1978), 41-52. MR 58 #5318. MR 0485488 (58:5318)
  • [15] S. Stahl and L. W. Beineke, Blocks and the nonorientable genus of graphs, J. Graph Theory 1 (1977), 75-78. MR 57 #161. MR 0460165 (57:161)
  • [16] W. T. Tutte, Lectures on matroids, J. Res. Nat. Bur. Standards (U.S.A.) Sect. B 69B (1965), 1-47. MR 31 #4023. Reprinted with commentary in D. McCarthy and R. G. Stanton, eds., Selected papers of W. T. Tutte, vol. II, Charles Babbage Research Centre, St. Pierre, Man., Canada, 1979, 439-496. MR 0179781 (31:4023)
  • [17] D. J. A. Welsh, Matroid theory, Academic Press, London, 1976. MR 55 #148. MR 0427112 (55:148)
  • [18] Neil White, ed., Theory of matroids, Encycl. of Math. and Its Appl., vol. 26, Cambridge Univ. Press, Cambridge, Eng., 1986. MR 87k:05054. MR 849389 (87k:05054)
  • [19] -, Combinatorial geometries, Encycl. of Math. and Its Appl., vol. 29, Cambridge Univ. Press, Cambridge, Eng., 1987. MR 88g:05048.
  • [20] H. Whitney, Non-separable and planar graphs, Trans. Amer. Math. Soc. 34 (1932), 339-362. MR 1501641
  • [21] -, $ 2$-isomorphic graphs, Amer. J. Math. 55 (1933), 245-254.
  • [22] N. H. Xuong, How to determine the maximum genus of a graph, J. Combin. Theory Ser. B 26 (1979), 217-225. MR 80k:05051. MR 532589 (80k:05051)

Similar Articles

Retrieve articles in Proceedings of the American Mathematical Society with MSC: 05C10, 05B35

Retrieve articles in all journals with MSC: 05C10, 05B35


Additional Information

DOI: https://doi.org/10.1090/S0002-9939-1989-0979055-7
Keywords: Primary, graph embedding, genus, demigenus, crosscap number, genus range, crosscap range, Secondary, polygon matroid, cycle matroid
Article copyright: © Copyright 1989 American Mathematical Society

American Mathematical Society