Geodesic
$\ell ^{2}$-homology and planar graphs
Timothy A. Schroeder1
1 Department of Mathematics and Statistics Murray State University Murray, KY 42071, U.S.A.
Colloquium Mathematicum, Tome 131 (2013) no. 1, pp. 129-139.

Voir la notice de l'article provenant de la source Institute of Mathematics Polish Academy of Sciences

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.
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

Timothy A. Schroeder 1

1 Department of Mathematics and Statistics Murray State University Murray, KY 42071, U.S.A. 
@article{10_4064_cm131_1_11,
     author = {Timothy A. Schroeder},
     title = {$\ell ^{2}$-homology and planar graphs},
     journal = {Colloquium Mathematicum},
     pages = {129--139},
     publisher = {mathdoc},
     volume = {131},
     number = {1},
     year = {2013},
     doi = {10.4064/cm131-1-11},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.4064/cm131-1-11/}
}
TY  - JOUR
AU  - Timothy A. Schroeder
TI  - $\ell ^{2}$-homology and planar graphs
JO  - Colloquium Mathematicum
PY  - 2013
SP  - 129
EP  - 139
VL  - 131
IS  - 1
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/articles/10.4064/cm131-1-11/
DO  - 10.4064/cm131-1-11
LA  - en
ID  - 10_4064_cm131_1_11
ER  - 
%0 Journal Article
%A Timothy A. Schroeder
%T $\ell ^{2}$-homology and planar graphs
%J Colloquium Mathematicum
%D 2013
%P 129-139
%V 131
%N 1
%I mathdoc
%U http://geodesic.mathdoc.fr/articles/10.4064/cm131-1-11/
%R 10.4064/cm131-1-11
%G en
%F 10_4064_cm131_1_11
Timothy A. Schroeder. $\ell ^{2}$-homology and planar graphs. Colloquium Mathematicum, Tome 131 (2013) no. 1, pp. 129-139. doi : 10.4064/cm131-1-11. http://geodesic.mathdoc.fr/articles/10.4064/cm131-1-11/

Cité par Sources :