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 , 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 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.
@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/