On the null space of a Colin de Verdière matrix
Lovász, Lászlo ; Schrijver, Alexander
Annales de l'Institut Fourier, Tome 49 (1999), p. 1017-1026 / Harvested from Numdam

Soit G=(V,E) un graphe planaire 3-connexe, avec V={1,...,n}. Soit M=(m i,j ) une matrice symétrique n×n ayant exactement une valeur propre <0 (de multiplicité 1), telle que, pour toute arête {i,j}, m i,j <0 et, si {i,j} n’est pas une arête, m i,j =0, et supposons que le rang de M soit n-3. Alors le noyau kerM de M définit un plongement de G dans S 2 de la façon suivante : soit {a,b,c} une base de kerM ; pour iV, on pose φ(i):=(a i ,b i ,c i ) T  ; alors φ(i)0, et ψ(i):=φ(i)/φ(i) est un plongement de V dans S 2 . Si on connecte, pour toute paire de sommets adjacents i,j, les points ψ(i) et ψ(j) par une géodésique minimisante dans S 2 , on obtient un plongement de G dans S 2 .

Nous prouvons des résultats analogues pour les graphes extérieurs planaires et pour les chemins. Ces résultats s’appliquent aux matrices associées à l’invariant μ(G) introduit par Y. Colin de Verdière.

Let G=(V,E) be a 3-connected planar graph, with V={1,...,n}. Let M=(m i,j ) be a symmetric n×n matrix with exactly one negative eigenvalue (of multiplicity 1), such that for i,j with ij, if i and j are adjacent then m i,j <0 and if i and j are nonadjacent then m i,j =0, and such that M has rank n-3. Then the null space kerM of M gives an embedding of G in S 2 as follows: let {a,b,c} be a basis of kerM, and for iV let φ(i):=(a i ,b i ,c i ) T ; then φ(i)0, and ψ(i):=φ(i)/φ(i) embeds V in S 2 such that connecting, for any two adjacent vertices i,j, the points ψ(i) and ψ(j) by a shortest geodesic on S 2 , gives a proper embedding of G in S 2 .

We prove similar results for outerplanar graphs and paths. They apply to the matrices associated with the parameter μ(G) introduced by Y. Colin de Verdière.

@article{AIF_1999__49_3_1017_0,
     author = {Lov\'asz, L\'aszlo and Schrijver, Alexander},
     title = {On the null space of a Colin de Verdi\`ere matrix},
     journal = {Annales de l'Institut Fourier},
     volume = {49},
     year = {1999},
     pages = {1017-1026},
     doi = {10.5802/aif.1703},
     mrnumber = {2000h:05064},
     zbl = {0923.05038},
     language = {en},
     url = {http://dml.mathdoc.fr/item/AIF_1999__49_3_1017_0}
}
Lovász, Lászlo; Schrijver, Alexander. On the null space of a Colin de Verdière matrix. Annales de l'Institut Fourier, Tome 49 (1999) pp. 1017-1026. doi : 10.5802/aif.1703. http://gdmltest.u-ga.fr/item/AIF_1999__49_3_1017_0/

[1] Y. Colin De Verdière, Sur un nouvel invariant des graphes et un critère de planarité, Journal of Combinatorial Theory, Series B, 50 (1990), 11-21 [English translation: On a new graph invariant and a criterion for planarity, in: Graph Structure Theory (N. Robertson, P. Seymour, eds.), Contemporary Mathematics, American Mathematical Society, Providence, Rhode Island, 1993, 137-147]. | MR 91m:05068 | Zbl 0742.05061

[2] H. Van Der Holst, A short proof of the planarity characterization of Colin de Verdière, Journal of Combinatorial Theory, Series B, 65 (1995), 269-272. | MR 96g:05050 | Zbl 0841.05025

[3] H. Van Der Holst, Topological and Spectral Graph Characterizations, Ph.D. Thesis, University of Amsterdam, 1996.

[4] H. Van Der Holst, L. Lovász, A. Schrijver, On the invariance of Colin de Verdière's graph parameter under clique sums, Linear Algebra and its Applications, 226 (1995), 509-517. | MR 97e:05113 | Zbl 0834.05036

[5] L. Lovász, A. Schrijver, A Borsuk theorem for antipodal links and a spectral characterization of linklessly embeddable graphs, Proceedings of the American Mathematical Society, 126 (1998), 1275-1285. | MR 98j:05059 | Zbl 0886.05055