Abstract:
The height of a face in a 3-polytope is the maximum degree of the incident vertices of the face, and the height of a 3-polytope, h, is the minimum height of its faces. A face is pyramidal if it is either a 4-face incident with three 3-vertices, or a 3-face incident with two vertices of degree at most 4. If pyramidal faces are allowed, then h can be arbitrarily large; so we assume the absence of pyramidal faces. In 1940, Lebesgue proved that every quadrangulated 3-polytope has h⩽11. In 1995, this bound was lowered by Avgustinovich and Borodin to 10. Recently, we improved it to the sharp bound 8. For plane triangulation without 4-vertices, Borodin (1992), confirming the Kotzig conjecture of 1979, proved that h⩽20 which bound is sharp. Later, Borodin (1998) proved that h⩽20 for all triangulated 3-polytopes. Recently, we obtained the sharp bound 10 for triangle-free 3-polytopes. In 1996, Horňák and Jendrol' proved for arbitrarily 3-polytopes that h⩽23. In this paper we improve this bound to the sharp bound 20.
Keywords:plane map, planar graph, 3-polytope, structure properties, height of face.
The first author was supported by the Russian Foundation for Basic Research (Grants 15-01-05867 and 16-01-00499) and the State Maintenance Program for the Leading Scientific Schools of the Russian Federation (Grant
NSh-1939.2014.1). The second author worked within the governmental task “Organization of Scientific Research”.
Citation:
O. V. Borodin, A. O. Ivanova, “The height of faces of 3-polytopes”, Sibirsk. Mat. Zh., 58:1 (2017), 48–55; Siberian Math. J., 58:1 (2017), 37–42
This publication is cited in the following 4 articles:
O. V. Borodin, A. O. Ivanova, “Heights of minor faces in 3-polytopes”, Siberian Math. J., 62:2 (2021), 199–214
O. V. Borodin, A. O. Ivanova, “Low faces of restricted degree in 3-polytopes”, Siberian Math. J., 60:3 (2019), 405–411
O. V. Borodin, M. A. Bykov, A. O. Ivanova, “More about the height of faces in 3-polytopes”, Discuss. Math. Graph Theory, 38:2 (2018), 443–453
Borodin O.V. Ivanova A.O., “New Results About the Structure of Plane Graphs: a Survey”, Proceedings of the 8th International Conference on Mathematical Modeling (ICMM-2017), AIP Conference Proceedings, 1907, ed. Egorov I. Popov S. Vabishchevich P. Antonov M. Lazarev N. Troeva M. Troeva M. Ivanova A. Grigorev Y., Amer Inst Physics, 2017, UNSP 030051