On the null space of a Colin de Verdière matrix

Lovász, Lászlo; Schrijver, Alexander

doi:10.5802/aif.1703

Lovász, Lászlo ; Schrijver, Alexander

Annales de l'Institut Fourier, Tome 49 (1999) no. 3, pp. 1017-1026.

Résumé
Abstract

Soit $G = (V, E)$ un graphe planaire 3-connexe, avec $V = {1, ..., n}$ . Soit $M = (m_{i, j})$ une matrice symétrique $n \times 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 $ker M$ de $M$ définit un plongement de $G$ dans $S^{2}$ de la façon suivante : soit ${a, b, c}$ une base de $ker M$ ; pour $i \in V$ , on pose $φ (i) : = (a_{i}, b_{i}, c_{i})^{T}$ ; alors $φ (i) \neq 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 \times n$ matrix with exactly one negative eigenvalue (of multiplicity 1), such that for $i, j$ with $i \neq j$ , 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 $ker M$ of $M$ gives an embedding of $G$ in $S^{2}$ as follows: let ${a, b, c}$ be a basis of $ker M$ , and for $i \in V$ let $φ (i) : = (a_{i}, b_{i}, c_{i})^{T}$ ; then $φ (i) \neq 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.

MR Zbl

DOI : 10.5802/aif.1703

@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},
     mrnumber = {2000h:05064},
     zbl = {0923.05038},
     language = {en},
     url = {https://www.numdam.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://www.numdam.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://www.numdam.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, Tome 49 (1999) no. 3, pp. 1017-1026. doi : 10.5802/aif.1703. https://www.numdam.org/articles/10.5802/aif.1703/

Bibliographie
Cité par

[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 | Zbl

[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 | Zbl

[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 | Zbl

[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 | Zbl

Babecki, Catherine; Shiroma, David Eigenpolytope Universality and Graphical Designs, SIAM Journal on Discrete Mathematics, Volume 38 (2024) no. 1, p. 947 | DOI:10.1137/22m1528768
DeVos, Matt; Rogers, Danielle; Wesolek, Alexandra On Minimizing the Energy of a Spherical Graph Representation, Graph Drawing and Network Visualization, Volume 14466 (2023), p. 218 | DOI:10.1007/978-3-031-49275-4_15
Kaluža, Vojtěch; Tancer, Martin Even Maps, the Colin de Verdière Number and Representations of Graphs, Combinatorica, Volume 42 (2022) no. S2, p. 1317 | DOI:10.1007/s00493-021-4443-7
Lin, Jephian C.-H.; Oblak, Polona; Šmigoc, Helena The strong spectral property for graphs, Linear Algebra and its Applications, Volume 598 (2020), p. 68 | DOI:10.1016/j.laa.2020.03.031
Lovász, László; Schrijver, Alexander Nullspace Embeddings for Outerplanar Graphs, A Journey Through Discrete Mathematics (2017), p. 571 | DOI:10.1007/978-3-319-44479-6_23
Aigerman, Noam; Kovalsky, Shahar Z.; Lipman, Yaron Spherical orbifold tutte embeddings, ACM Transactions on Graphics, Volume 36 (2017) no. 4, p. 1 | DOI:10.1145/3072959.3073615
Godsil, Chris; Roberson, David E.; Rooney, Brendan; Šámal, Robert; Varvitsiotis, Antonios Universal Completability, Least Eigenvalue Frameworks, and Vector Colorings, Discrete Computational Geometry, Volume 58 (2017) no. 2, p. 265 | DOI:10.1007/s00454-017-9899-2
Schrijver, Alexander; Sevenster, Bart The Strong Arnold Property for 4-connected flat graphs, Linear Algebra and its Applications, Volume 522 (2017), p. 153 | DOI:10.1016/j.laa.2017.02.002
László, István Topological coordinates for bar polyhex carbon structures, Theoretical Chemistry Accounts, Volume 134 (2015) no. 9 | DOI:10.1007/s00214-015-1708-5
Laurent, M.; Varvitsiotis, A. Positive semidefinite matrix completion, universal rigidity and the Strong Arnold Property, Linear Algebra and its Applications, Volume 452 (2014), p. 292 | DOI:10.1016/j.laa.2014.03.015
László, István; Graovac, Ante; Pisanski, Tomaž Drawing Diamond Structures with Eigenvectors, Diamond and Related Nanostructures, Volume 6 (2013), p. 299 | DOI:10.1007/978-94-007-6371-5_16
László, István; Graovac, Ante; Pisanski, Tomaž Nanostructures and Eigenvectors of Matrices, Topological Modelling of Nanostructures and Extended Systems, Volume 7 (2013), p. 287 | DOI:10.1007/978-94-007-6413-2_10
László, István Geometry of nanostructures and eigenvectors of matrices, physica status solidi (b), Volume 250 (2013) no. 12, p. 2732 | DOI:10.1002/pssb.201300091
Kawarabayashi, Ken-ichi; Kreutzer, Stephan; Mohar, Bojan Linkless and Flat Embeddings in 3-Space, Discrete Computational Geometry, Volume 47 (2012) no. 4, p. 731 | DOI:10.1007/s00454-012-9413-9
László, István; Graovac, Ante; Pisanski, Tomaž; Plavšić, Dejan Graph Drawing with Eigenvectors, Carbon Bonding and Structures, Volume 5 (2011), p. 95 | DOI:10.1007/978-94-007-1733-6_6
Zhang, H.; Van Kaick, O.; Dyer, R. Spectral Mesh Processing, Computer Graphics Forum, Volume 29 (2010) no. 6, p. 1865 | DOI:10.1111/j.1467-8659.2010.01655.x
Izmestiev, Ivan The Colin de Verdière number and graphs of polytopes, Israel Journal of Mathematics, Volume 178 (2010) no. 1, p. 427 | DOI:10.1007/s11856-010-0070-5
Kawarabayashi, Ken-ichi; Kreutzer, Stephan; Mohar, Bojan, Proceedings of the twenty-sixth annual symposium on Computational geometry (2010), p. 97 | DOI:10.1145/1810959.1810975
Gotsman, Craig; Toledo, Sivan On the Computation of Null Spaces of Sparse Rectangular Matrices, SIAM Journal on Matrix Analysis and Applications, Volume 30 (2008) no. 2, p. 445 | DOI:10.1137/050638369
Gonçalves, D. On Vertex Partitions and the Colin de Verdière Parameter, Electronic Notes in Discrete Mathematics, Volume 28 (2007), p. 543 | DOI:10.1016/j.endm.2007.01.075
Kawarabayashi, Ken-ichi; Mohar, Bojan Some Recent Progress and Applications in Graph Minor Theory, Graphs and Combinatorics, Volume 23 (2007) no. 1, p. 1 | DOI:10.1007/s00373-006-0684-x
Saba, S.; Yavneh, I.; Gotsman, C.; Sheffer, A., International Conference on Shape Modeling and Applications 2005 (SMI' 05) (2005), p. 256 | DOI:10.1109/smi.2005.32
László, István Topological coordinates for nanotubes, Carbon, Volume 42 (2004) no. 5-6, p. 983 | DOI:10.1016/j.carbon.2003.12.022
Gotsman, C., 2003 Shape Modeling International. (2003), p. 165 | DOI:10.1109/smi.2003.1199613
Gotsman, Craig; Gu, Xianfeng; Sheffer, Alla, ACM SIGGRAPH 2003 Papers (2003), p. 358 | DOI:10.1145/1201775.882276
Gotsman, Craig; Gu, Xianfeng; Sheffer, Alla Fundamentals of spherical parameterization for 3D meshes, ACM Transactions on Graphics, Volume 22 (2003) no. 3, p. 358 | DOI:10.1145/882262.882276
Godsil, Chris; Royle, Gordon The Laplacian of a Graph, Algebraic Graph Theory, Volume 207 (2001), p. 279 | DOI:10.1007/978-1-4613-0163-9_13
Lovász, László Steinitz Representations of Polyhedra and the Colin de Verdière Number, Journal of Combinatorial Theory, Series B, Volume 82 (2001) no. 2, p. 223 | DOI:10.1006/jctb.2000.2027

Cité par 28 documents. Sources : Crossref