zbMATH — the first resource for mathematics

Height of minor faces in plane normal maps. (English. Russian original) Zbl 0913.05039
Discrete Appl. Math. 135, No. 1-3, 31-39 (2004); translation from Diskretn. Anal. Issled. Oper., Ser. 1 5, No. 4, 6-17 (1998).
The well-known Lebesgue theorem on planar normal maps (1940) and some more recent results by O. V. Borodin and S. V. Avgustinovich and by M. Horňák and S. Jendrol’ are strengthened. The main result is as follows: In any planar normal map without faces of the form \((4,4,\infty)\), \((3,5,\infty)\), \((3,3,3, \infty)\), there exists either a 3-face of height at most 20, or a 4-face of height at most 11, or a 5-face of height at most 5. Moreover, the estimates for 3- and 5-faces are unimprovable. The hypothesis is formulated that the above estimation for 4-faces is unimprovable, too.

05C10 Planar graphs; geometric and topological aspects of graph theory
05C75 Structural characterization of families of graphs
Full Text: DOI
[1] Avgustinovich, S.V.; Borodin, O.V., Neighborhoods of edges in normal maps, Discrete anal., 2, 3, 3-9, (1995), (in Russian) · Zbl 0856.05031
[2] Borodin, O.V., Solution of kotzig’s and Grunbaum’s problems about the separability of cycle in plane graphs, Matem. zametki, 46, 5, 10-12, (1989), (in Russian)
[3] Borodin, O.V., Maximum weight of a face in plane triangulations, Matem. zametki, 51, 1, 16-19, (1992), (in Russian) · Zbl 0755.05091
[4] Borodin, O.V., Triangulated 3-polytopes without faces of low weight, Discrete math., 186, 281-285, (1998) · Zbl 0956.52010
[5] Horn̆ák, M.; Jendrol’, S., Unavoidable sets of face types for planar maps, Discuss. math. graph theory, 16, 2, 207-218, (1996), (Polish journal)
[6] A.B. Ivanov, Semiregular polytopes, in: Mathematical Encyclopedia, Moscow, Soviet Encyclopedia, Vol. 53, 1984, p. 463.
[7] Kotzig, A., On the theory of Eulerian polyhedra, Mat. -fyz. casopis, 13, 1, 20-34, (1963) · Zbl 0134.19601
[8] Kotzig, A., Extremal polyhedral graphs, Proceedings of the second international conference on combinatorial mathematics, New York Academic sciences, New York, ann. New York acad. sci., 319, 569-570, (1978)
[9] Lebesgue, H., Quelques conséquences simples de la formule d’Euler, J. math. pures appl., 19, 27-43, (1940) · JFM 66.0736.03
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.