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

Lovász, Lászlo, and Schrijver, Alexander. "On the null space of a Colin de Verdière matrix." Annales de l'institut Fourier 49.3 (1999): 1017-1026. <http://eudml.org/doc/75353>.

@article{Lovász1999,
abstract = {Let $G=(V,E)$ be a 3-connected planar graph, with $V=\lbrace 1,\ldots ,n\rbrace $. 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\ne j$, if $i$ and $j$ are adjacent then $m_\{i,j\}&lt; 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 $\lbrace a,b,c\rbrace $ be a basis of $\ker M$, and for $i\in V$ let $\phi (i):=(a_i,b_i,c_i)^T$; then $\phi (i)\ne 0$, and $\psi (i):=\phi (i)/\Vert \phi (i)\Vert $ embeds $V$ in $S^2$ such that connecting, for any two adjacent vertices $i,j$, the points $\psi (i)$ and $\psi (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 $\mu (G)$ introduced by Y. Colin de Verdière.},
author = {Lovász, Lászlo, Schrijver, Alexander},
journal = {Annales de l'institut Fourier},
keywords = {Colin de Verdière matrix; planar graph; outerplanar graph; null space; imbedding; matrix},
language = {eng},
number = {3},
pages = {1017-1026},
publisher = {Association des Annales de l'Institut Fourier},
title = {On the null space of a Colin de Verdière matrix},
url = {http://eudml.org/doc/75353},
volume = {49},
year = {1999},
}

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
PB - Association des Annales de l'Institut Fourier
VL - 49
IS - 3
SP - 1017
EP - 1026
AB - Let $G=(V,E)$ be a 3-connected planar graph, with $V=\lbrace 1,\ldots ,n\rbrace $. 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\ne j$, if $i$ and $j$ are adjacent then $m_{i,j}&lt; 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 $\lbrace a,b,c\rbrace $ be a basis of $\ker M$, and for $i\in V$ let $\phi (i):=(a_i,b_i,c_i)^T$; then $\phi (i)\ne 0$, and $\psi (i):=\phi (i)/\Vert \phi (i)\Vert $ embeds $V$ in $S^2$ such that connecting, for any two adjacent vertices $i,j$, the points $\psi (i)$ and $\psi (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 $\mu (G)$ introduced by Y. Colin de Verdière.
LA - eng
KW - Colin de Verdière matrix; planar graph; outerplanar graph; null space; imbedding; matrix
UR - http://eudml.org/doc/75353
ER -