Embeddings of infinite graphs. (English) Zbl 0591.05028

Mohar, Bojan

J. Comb. Theory, Ser. B 44, No. 1, 29-43 (1988).

Embeddings of infinite graphs in surfaces (not necessarily compact) without boundary are considered. Cellular embeddings are studied in details. Each rotation system of a locally finite graph G gives rise to a cellular embedding of G into some surface, and every cellular embedding with all 2-cells of finite size can be obtained in this way. The graphs which admit cellular embeddings with all cells finite are characterized. It is shown that there is a surjective continuous mapping \(\psi\) : \(\beta\) (G)\(\to \beta (S)\) mapping the ends \(\beta\) (G) of a graph G onto the space of ends \(\beta\) (S) of the surface S into which G is cellularly embedded. If this embedding has only faces of finite size then \(\psi\) is a homeomorphism. Finally the genus of infinite graphs is considered. It is shown that the minimum genus of surfaces into which G has embedding is equal to the supremum of genera of finite subgraphs of G. To determine the genus, it suffices to consider cellular embeddings, but restriction to embeddings with finite faces does not always give genus embeddings.

MSC:

05C10

Planar graphs; geometric and topological aspects of graph theory

Keywords:

embeddings; infinite graphs; cellular embeddings; genus; noncompact surfaces; end of a graph

References:

[1]	Ahlfors, L. V.; Sario, L., (Riemann Surfaces (1960), Princeton Univ. Press: Princeton Univ. Press Princeton, NJ) · Zbl 0196.33801
[2]	Bryant, R. P.; Singerman, D., Foundations of the theory of maps on surfaces with boundary, Quart. J. Math. Oxford, 36, 2, 14-41 (1985) · Zbl 0565.05026
[3]	Edmonds, J. R., A combinatorial representation for polyhedral surfaces, Notices Amer. Math. Soc., 7, 646 (1960)
[4]	Freudenthal, H., Über die Enden topologischer Räume und Gruppen, Math. Z., 33, 692-713 (1931) · JFM 57.0731.01
[5]	Gross, J. L.; Tucker, T. W., (Topological Graph Theory (1987), Wiley: Wiley NY) · Zbl 0621.05013
[6]	Halin, R., Über unendliche Wege in Graphen, Math. Ann., 157, 125-137 (1964) · Zbl 0125.11701
[7]	Heffter, L., Über das Problem der Nachbargebiete, Math. Ann., 38, 477-508 (1891) · JFM 23.0543.01
[8]	Hoffman, P.; Richter, B., Embedding graphs in surfaces, J. Combin. Theory, Ser. B, 36, 65-84 (1984) · Zbl 0514.05028
[9]	Jones, G. A.; Singerman, D., Theory of maps on orientable surfaces, (Proc. London Math. Soc., 37 (1978)), 273-307, (3) · Zbl 0391.05024
[10]	Kerekjarto, B., (Vorlesungen über Topologie (1923), Springer-Verlag: Springer-Verlag Berlin) · JFM 49.0396.07
[11]	Massey, W. S., (Algebraic Topology: An Introduction (1967), Harcourt, Brace and World: Harcourt, Brace and World New York) · Zbl 0153.24901
[13]	Radó, T., Über den Begriff der Riemannschen Fläche, Acta Litt. Sci. Szeged, 2, 101-121 (1925) · JFM 51.0273.01
[14]	Richards, I., On the classification of noncompact surfaces, Trans. Amer. Math. Soc., 106, 259-269 (1963) · Zbl 0156.22203
[15]	Ringel, G., The combinatorial map color theorem, J. Graph Theory, 1, 141-155 (1977) · Zbl 0386.05030
[16]	Stahl, S., The generalized embedding schemes, J. Graph Theory, 2, 41-52 (1978) · Zbl 0396.05013
[17]	Stahl, S., The embedding of a graph—A survey, J. Graph Theory, 2, 275-298 (1978) · Zbl 0406.05027
[18]	White, A. T., (Graphs, Groups and Surfaces (1984), North-Holland: North-Holland Amsterdam)
[19]	White, A. T.; Beineke, L. W., Topological graph theory, (Beineke, L. W.; Wilson, R. J., Selected Topics in Graph Theory (1978), Academic Press: Academic Press London/Orlando) · Zbl 0439.05018
[20]	Youngs, J. W.T, Minimal imbeddings and the genus of a graph, J. Math. Mech., 12, 303-315 (1963) · Zbl 0109.41701
[21]	Imrich, W., On Whitney’s theorem on the unique embeddability of 3-connected planar graphs, (Recent Advances in Graph Theory (1975), Academia: Academia Prague) · Zbl 0329.05102