ℓ²-homology and planar graphs

Timothy A. Schroeder. "ℓ²-homology and planar graphs." Colloquium Mathematicae 131.1 (2013): 129-139. <http://eudml.org/doc/284276>.

@article{TimothyA2013,
abstract = {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 $K_\{3,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.},
author = {Timothy A. Schroeder},
journal = {Colloquium Mathematicae},
keywords = {planar graphs; 2-homology; Coxeter groups},
language = {eng},
number = {1},
pages = {129-139},
title = {ℓ²-homology and planar graphs},
url = {http://eudml.org/doc/284276},
volume = {131},
year = {2013},
}

TY - JOUR
AU - Timothy A. Schroeder
TI - ℓ²-homology and planar graphs
JO - Colloquium Mathematicae
PY - 2013
VL - 131
IS - 1
SP - 129
EP - 139
AB - 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 $K_{3,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.
LA - eng
KW - planar graphs; 2-homology; Coxeter groups
UR - http://eudml.org/doc/284276
ER -