Let be a 3-connected planar graph, with . Let be a symmetric matrix with exactly one negative eigenvalue (of multiplicity 1), such that for with , if and are adjacent then and if and are nonadjacent then , and such that has rank . Then the null space of gives an embedding of in as follows: let be a basis of , and for let ; then , and embeds in such that connecting, for any two adjacent vertices , the points and by a shortest geodesic on , gives a proper embedding of in .
We prove similar results for outerplanar graphs and paths. They apply to the matrices associated with the parameter introduced by Y. Colin de Verdière.
Soit un graphe planaire 3-connexe, avec . Soit une matrice symétrique ayant exactement une valeur propre (de multiplicité 1), telle que, pour toute arête , et, si n’est pas une arête, , et supposons que le rang de soit . Alors le noyau de définit un plongement de dans de la façon suivante : soit une base de ; pour , on pose ; alors , et est un plongement de dans . Si on connecte, pour toute paire de sommets adjacents , les points et par une géodésique minimisante dans , on obtient un plongement de dans .
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 introduit par 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}, pages = {1017--1026}, publisher = {Association des Annales de l{\textquoteright}institut Fourier}, volume = {49}, number = {3}, year = {1999}, doi = {10.5802/aif.1703}, zbl = {0923.05038}, mrnumber = {2000h:05064}, language = {en}, url = {https://aif.centre-mersenne.org/articles/10.5802/aif.1703/} }
TY - JOUR AU - Lovász, Lászlo AU - Schrijver, Alexander TI - On the null space of a Colin de Verdière matrix JO - Annales de l'Institut Fourier PY - 1999 SP - 1017 EP - 1026 VL - 49 IS - 3 PB - Association des Annales de l’institut Fourier UR - https://aif.centre-mersenne.org/articles/10.5802/aif.1703/ DO - 10.5802/aif.1703 LA - en ID - AIF_1999__49_3_1017_0 ER -
%0 Journal Article %A Lovász, Lászlo %A Schrijver, Alexander %T On the null space of a Colin de Verdière matrix %J Annales de l'Institut Fourier %D 1999 %P 1017-1026 %V 49 %N 3 %I Association des Annales de l’institut Fourier %U https://aif.centre-mersenne.org/articles/10.5802/aif.1703/ %R 10.5802/aif.1703 %G en %F 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, Volume 49 (1999) no. 3, pp. 1017-1026. doi : 10.5802/aif.1703. https://aif.centre-mersenne.org/articles/10.5802/aif.1703/
[1] 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 | Zbl
,[2] A short proof of the planarity characterization of Colin de Verdière, Journal of Combinatorial Theory, Series B, 65 (1995), 269-272. | MR | Zbl
,[3] Topological and Spectral Graph Characterizations, Ph.D. Thesis, University of Amsterdam, 1996.
,[4] On the invariance of Colin de Verdière's graph parameter under clique sums, Linear Algebra and its Applications, 226 (1995), 509-517. | MR | Zbl
, , ,[5] 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 | Zbl
, ,Cited by Sources: