ℓ²-homology and planar graphs
Timothy A. Schroeder
Colloquium Mathematicae, Tome 131 (2013), p. 129-139 / Harvested from The Polish Digital Mathematics Library

In his 1930 paper, Kuratowski proves that a finite graph Γ is planar if and only if it does not contain a subgraph that is homeomorphic to K₅, the complete graph on five vertices, or K3,3, the complete bipartite graph on six vertices. This result is also attributed to Pontryagin. In this paper we present an ℓ²-homological method for detecting non-planar graphs. More specifically, we view a graph Γ as the nerve of a related Coxeter system and construct the associated Davis complex, ΣΓ. We then use a result of the author regarding the (reduced) ℓ²-homology of Coxeter groups to prove that if Γ is planar, then the orbihedral Euler characteristic of ΣΓ/WΓ is non-positive. This method not only implies as subcases the classical inequalities relating the number of vertices V and edges E of a planar graph (that is, E ≤ 3V-6 or E ≤ 2V-4 for triangle-free graphs), but it is stronger in that it detects non-planar graphs in instances the classical inequalities do not.

Publié le : 2013-01-01
EUDML-ID : urn:eudml:doc:284276
@article{bwmeta1.element.bwnjournal-article-doi-10_4064-cm131-1-11,
     author = {Timothy A. Schroeder},
     title = {l2-homology and planar graphs},
     journal = {Colloquium Mathematicae},
     volume = {131},
     year = {2013},
     pages = {129-139},
     zbl = {1275.05016},
     language = {en},
     url = {http://dml.mathdoc.fr/item/bwmeta1.element.bwnjournal-article-doi-10_4064-cm131-1-11}
}
Timothy A. Schroeder. ℓ²-homology and planar graphs. Colloquium Mathematicae, Tome 131 (2013) pp. 129-139. http://gdmltest.u-ga.fr/item/bwmeta1.element.bwnjournal-article-doi-10_4064-cm131-1-11/