Computing Reviews
Today's Issue Hot Topics Search Browse Recommended My Account Log In
Review Help
Search
Curvature, geometry and spectral properties of planar graphs
Keller M. Discrete & Computational Geometry46 (3):500-525,2011.Type:Article
Date Reviewed: Jun 28 2012

Keller characterizes theorems of planar graphs, using curvature functions. A curvature function is defined as a function on corners, on vertices, or on faces of the graph. The main part of the paper deals with different characterization theorems, which I cover without technical details in this review.

The first two theorems deal with nonpositive curvature. Theorem 1 essentially states that if one of the curvature functions is nonpositive, then the graph is infinite and locally tessellating. Theorem 2 is more technical, but concludes that the graph is locally similar to a tessellation, again when there is nonpositive curvature and when some technical conditions are satisfied.

A metric space can be associated with a graph. In the third theorem, it is shown that this metric space has no cut locus, if the locally finite planar graph has a nonpositive curvature. The fourth theorem, which is rather technical, describes boundary distance balls. Both theorems refer to the curvature functions on the corners.

The fifth and sixth theorems connect negative curvature with bounds for the growth of distance balls, and with bounds for Cheeger’s constant, respectively. These theorems involve curvature with relation to vertices.

The seventh theorem, on curvature with relation to corners, states that any minimal bigon has an empty interior under certain additional assumptions, and, with one more assumption, concludes that the graph is Gromov hyperbolic. Finally, two theorems describe spectral implications, again in the case of nonpositive curvature.

It is noteworthy that the author introduces a notion of curvature for general planar graphs, generalizing an existing notion for tessellations. As such, the author is able to study the geometry and spectral properties of planar graphs, making this paper an interesting contribution to this field.

Reviewer:  Jan De Beule Review #: CR140318 (1211-1162)
Bookmark and Share
  Featured Reviewer  
 
Discrete Mathematics (G.2 )
 
 
Continuation (Homotopy) Methods (G.1.5 ... )
 
 
Eigenvalues And Eigenvectors (Direct And Iterative Methods) (G.1.3 ... )
 
 
Hyperbolic Equations (G.1.8 ... )
 
Would you recommend this review?
yes
no
Other reviews under "Discrete Mathematics": Date
 Discrete mathematics and its applications
Rosen K., McGraw-Hill Higher Education, Columbus, OH, 2002.  928, Type: Book (9780072424348)
May 7 2003
Derandomization of auctions
Aggarwal G., Fiat A., Goldberg A., Hartline J., Immorlica N., Sudan M.  Theory of computing (Proceedings of the Thirty-Seventh Annual ACM Symposium on Theory of Computing, Baltimore, MD, May 22-24, 2005)619-625, 2005. Type: Proceedings
Jul 31 2006
Algorithms on strings
Crochemore M., Hancart C., Lecroq T., Cambridge University Press, New York, NY, 2007.  392, Type: Book (9780521848992)
Apr 8 2008
more...

E-Mail This Printer-Friendly
Send Your Comments
Contact Us
Reproduction in whole or in part without permission is prohibited.   Copyright 1999-2024 ThinkLoud®
Terms of Use
| Privacy Policy