On 2-cell embeddings of graphs with minimum numbers of regions. (English) Zbl 0586.05015

Let \(\gamma_ M(G)\) denote the maximum genus of a graph G and let \(\beta\) (G) denote its Betti number. A graph G is upper embeddable provided that \(\gamma_ M(G)=\lfloor \beta (G)/2\rfloor\). Given G and a spanning subgraph J, the author derives necessary and sufficient conditions for when there exists an upper embeddable H with \(J\subset H\subset G\) (supposing that J is connected). He also derives necessary and sufficient conditions for when every such H is upper embeddable (supposing that G is connected).
Reviewer: D.S.Archdeacon


05C10 Planar graphs; geometric and topological aspects of graph theory
Full Text: EuDML


[1] M. Behzad G. Chartrand, and L. Lesniak-Foster: Graphs & Digraphs. Prindle, Weber & Schmidt, Boston 1979. · Zbl 0403.05027
[2] F. Harary: Graph Theory. Addison-Wesley, Reading (Mass.) 1969. · Zbl 0196.27202
[3] N. P. Homenko N. A. Ostroverkhy, and V. A. Kusmenko: The maximum genus of a graph. (in Ukrainian, English summary), \(\varphi\)-peretvorennya grafiv (N. P. Homenko IM AN URSR, Kiev 1973, pp. 180-210.
[4] M. Jungerman: A characterization of upper embeddable graphs. Trans. Amer. Math. Soc. 241 (1978), 401-406. · Zbl 0379.05025
[5] L. Nebeský: A new characterization of the maximum genus of a graph. Czechoslovak Math. J. 31 (106) (1981), 604-613. · Zbl 0482.05034
[6] L. Nebeský: A note on upper embeddable graphs. Czechoslovak Math. J. 33 (108) (1983), 37-40.
[7] L. Nebeský: On a diffusion of a set of vertices in a connected graph. Graphs and Other Combinatorial Topics (Proc. Third Czechoslovak Symp. Graph Theory held in Prague, 1982) (M. Fiedler, Teubner-Texte zur Mathematik, Band 59, Teubner, Leipzig 1983, pp. 200-203.
[8] E. A. Nordhaus R. D. Ringeisen B. M. Stewart, and A. T. White: A Kuratowski-type theorem for the maximum genus of a graph. J. Combinatorial Theory 12 B (1972), 260-267. · Zbl 0217.02301
[9] G. Ringel: The combinatorial map color theorem. J. Graph Theory 1 (1977), 141 - 155. · Zbl 0386.05030
[10] N. H. Xuong: How to determine the maximum genus of a graph. J. Combinatorial Theory 26 B (1979), 217-225. · Zbl 0403.05035
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.