$\ell ^{2}$-homology and planar graphs

Timothy A. Schroeder¹

¹ Department of Mathematics and Statistics Murray State University Murray, KY 42071, U.S.A.

Colloquium Mathematicum, Tome 131 (2013) no. 1, pp. 129-139

Résumé

In his 1930 paper, Kuratowski proves that a finite graph $\varGamma $ is planar if and only if it does not contain a subgraph that is homeomorphic to $K_5$, the complete graph on five vertices, or $K_{3,3}$, the complete bipartite graph on six vertices. This result is also attributed to Pontryagin. In this paper we present an $\ell ^2$-homological method for detecting non-planar graphs. More specifically, we view a graph $\varGamma $ as the nerve of a related Coxeter system and construct the associated Davis complex, $\varSigma _\varGamma $. We then use a result of the author regarding the (reduced) $\ell ^2$-homology of Coxeter groups to prove that if $\varGamma $ is planar, then the orbihedral Euler characteristic of $\varSigma _\varGamma /W_\varGamma $ 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\leq 3V-6$ or $E\leq 2V-4$ for triangle-free graphs), but it is stronger in that it detects non-planar graphs in instances the classical inequalities do not.

Détail

DOI : 10.4064/cm131-1-11

Keywords: his paper kuratowski proves finite graph vargamma planar only does contain subgraph homeomorphic complete graph five vertices complete bipartite graph six vertices result attributed pontryagin paper present ell homological method detecting non planar graphs specifically view graph vargamma nerve related coxeter system construct associated davis complex varsigma vargamma result author regarding reduced ell homology coxeter groups prove vargamma planar orbihedral euler characteristic varsigma vargamma vargamma non positive method only implies subcases classical inequalities relating number vertices edges planar graph leq v leq v triangle free graphs stronger detects non planar graphs instances classical inequalities