Abstract
Let G be an infinite graph embedded in a closed 2-manifold, such that each open face of the embedding is homeomorphic to an open disk and is bounded by finite number of edges. For each vertex x of G, define the combinatorial curvature
as that of [8], where d(x) is the degree of x, F(x) is the multiset of all open faces σ in the embedding such that the closure \(\bar\sigma\) contains x (the multiplicity of σ is the number of times that x is visited along ∂σ), and |σ| is the number of sides of edges bounding the face σ. In this paper, we first show that if the absolute total curvature ∑ x∈V(G) |Φ G (x)| is finite, then G has only finite number of vertices of non-vanishing curvature. Next we present a Gauss-Bonnet formula for embedded infinite graphs with finite number of accumulation points. At last, for a finite simple graph G with 3 ≤ d G (x) < ∞ and Φ G (x) > 0 for every x ∈ V(G), we have (i) if G is embedded in a projective plane and #(V(G)) = n ≥ 1722, then G is isomorphic to the projective wheel P n ; (ii) if G is embedded in a sphere and #(V(G)) = n ≥ 3444, then G is isomorphic to the sphere annulus either A n or B n ; and (iii) if d G (x) = 5 for all x ∈ V(G), then there are only 49 possible embedded plane graphs and 16 possible embedded projective plane graphs.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Banchoff, T.: Critical points and curvature for embedded polyhedra. J. Diff. Geom. 1, 245–256 (1967)
Cheeger, J.: A lower bound for the lowest eigenvalue of the Laplacian. In: Problems in Analysis, A Symposium in honor of S. Bochner, 195–199, Princeton Univ. Press (1970)
Cheeger, J., Mller, W., Schrader, R.: On the curvature of piecewise flat spaces. Comm. Math. Phys. 92, 405–454 (1984)
Chen, B.: The Gram-Sommerville and Gauss-Bonnet theorems and the combinatorial geometric measures for noncompact polyhedra. Advances in Math. 91, 269–291 (1992)
Devos, M., Mohar, B.: An analogue of the Descartes-Euler formula for infinite graphs and Higuch’s conjecture. Trans. Amer. Math. Soc. 359, 3287–3300 (2007)
Forman, R.: Bochner’s method for cell complexes and combinatorial Ricci curvature. Discrete Comput. Geom. 29, 323–374 (2003)
Gromov, M.: Hyperbolic groups, Essays in group theory, S. M. Gersten, (Editor), M.S.R.I. Publ. 8, Springer, pp. 75–263 (1987)
Higuchi, Y.: Combinatorial curvature for planar graphs. J. Graph Theory 38, 220–229 (2001)
Ishida, M.: Pseudo-curvature of a graph, Lecture at ‘Workshop on topological graph theory’. Yokohama National University (1990)
Luo, F., Stong, R.: Combinatorics of triangulations of 3-manifolds. Trans. Amer. Math. Soc. 337, 891–906 (1993)
Stone, D.: A Combinatorial Analogue of a Theorem of Myers. Illinois. J. Math. 20, 12–21 (1976)
Sun, L., Yu, X.: Positively curved cubic plane graphs are finite. J. Graph Theory 47, 241–274 (2004)
Thurston, W.P.: Shapes of polyhedra and triangulations of the sphere, in “The Epstein birthday schrift”, 511–549 (electronic), Geom. Topol. Monogr., 1, Geom. Topol. Publ., Coventry (1998)
West, D.: Introduction to Graph Theory, 2nd ed., Prentice Hall Inc., Upper Saddle River, NJ (2001)
Author information
Authors and Affiliations
Corresponding author
Additional information
Received: February 20, 2007. Final version received: January 1, 2008.
Beifang Chen: The first author was supported by the RGC Competitive Earmarked Research Grant 600703.
Guantao Chen: The second author was partially supported by NSF DMS-0070514 and NSA-H98230-04-1-0300.
Rights and permissions
About this article
Cite this article
Chen, B., Chen, G. Gauss-Bonnet Formula, Finiteness Condition, and Characterizations of Graphs Embedded in Surfaces. Graphs and Combinatorics 24, 159–183 (2008). https://doi.org/10.1007/s00373-008-0782-z
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00373-008-0782-z
Keywords
- Combinatorial curvature
- Gauss-Bonnet formula
- Euler relation
- Infinite graph
- Embedding
- Face cycle
- Finiteness theorem