Algebraic graph invariant $\mu(G)$ which links Four-Color-Theorem with Schrödinger operators: further topological characterizations of graphs?
Perhaps I can contribute to the history part the question, since I was quite close to the Institut Fourier at that time and was very interested in their work (I am a physicist). Grenoble now has several different research groups doing graph theory (like G-SCOP, Institut Fourier, GIPSA-lab, LIG) but I think L'Institut Fourier was the early one for graph theory.
Here are two original quotes from Yves Colin de Verdière about the time when $\mu(G)$ evolved; my translation. The quotes give a view about his collaboration with the graph theory team; and his view of graphs as singular Riemannian manifolds, in the context of his differential geometry work.
First quote from Yves Colin de Verdière 2004 [Theorem 5 is about graph minor monotonicity of $\mu$ and Theorem 6 is the characterization of planar graphs. Theorem 17 is from S. Cheng: Eigenfunctions and nodal sets. Comment. Math. Helv., 51:43-55, 1976]:
I discovered theorems 5 and 6, trying to understand Cheng's theorem (Theorem 17) and its possible extension to dimension 3. This theorem was stated in the context of partial differential equations and differential geometry. It took me many years and timely encounters to discover that graph theory was the natural framework for the study of these problems. I was fortunate to benefit in Grenoble from the availability of colleagues in graph theory, in particular François Jaeger (1947-1997), who helped me to discover this subject far away from my original background. It is one of the things I find fascinating in mathematics, these unexpected links between fields that are a priori very far away!
Second quote from Yves Colin de Verdière 1986:
Let $\Gamma_N$ be the complete graph with $N$ vertices ($N\geq4$): each pair of distinct vertices is joined by a single edge. $\Gamma_N$ is considered as a singular Riemannian manifold of dimension 1; if $\cal A$ is the set of $N(N-1)/2$ edges, a Riemannian metric on $\Gamma_N$ is entirely determined (up to isometry) by the length $l(a)$ of any edge $a$ of $\cal A$.
The original quotes are in French
First quote: in SUR LE SPECTRE DES OPÉRATEURS
DE TYPE SCHRÖDINGER SUR LES GRAPHES, Exposés à l’Ecole Polytechnique pour les
professeurs de Mathématiques Spéciales, Yves Colin de Verdière, 17 mai 2004:
J’ai découvert les théorèmes 5 et 6, en essayant de comprendre le théorème de Cheng (Théorème 17) et son éventuelle extension à la dimension 3. Ce théorème était énoncé dans le contexte des équations aux dérivées partielles et de la géométrie différentielle. Il m’a fallu de nombreuses années et des rencontres opportunes pour découvrir que la théorie des graphes était le cadre naturel pour l’étude de ces problèmes. J’ai eu la chance de bénéficier à Grenoble de la disponibilité des collègues de théorie des graphes, en particulier de François Jaeger (1947-1997), qui m’ont aidé à découvrir ce sujet loin de ma culture de base... C’est une des choses que je trouve fascinantes en mathématiques que ces liens imprévus entre des domaines a priori très lointains!
Second quote: in Sur la multiplicité de la première valeur propre non nulle du Laplacien, Yves Colin de Verdière, Comment. Math. Helv. 61, 254-270, 1986: Soit $\Gamma_N$ le graphe complet à $N$ sommets ($N\geq4$): chaque couple de sommets distincts est joint par une arête unique. On considère $\Gamma_N$ comme une variété riemannienne singulière de dimension 1; si $\cal A$ est l'énsemble des $N(N-1)/2$ arêtes, une métrique riemannienne sur $\Gamma_N$ est entièrement déterminée (à isométrie près) par la longueur l(a) de toute arête a de si.
Embeddability in any surface but the sphere (or plane) can probably not be characterized via the Colin de Verdière number.
Suppose that $K_n$ is the largest complete graph that embedds into a surface $S$. This shows that the best we can hope for is "$G$ embedds in $S$ $\Leftrightarrow$ $\mu(G)\le\mu(K_n)= n-1$".
The following is still a bit hand-wavy (maybe someone can help): I can imagine, that a disjoint union of sufficiently many $K_n$ can no longer be embedded into $S$ (except if $S$ is a sphere/plane). My intuition is that any additional $K_n$ must embedd in one of the regions given by the embedding of the previous $K_n$, and this region is probably "of a lesser genus" (if the genus is not already 0). For example, this is true for $S$ being the projective plane: $K_5$ embedds in $\Bbb R P^2$, but $K_5+K_5$ does not (see here). Also, a claim in this question seems to support this in the orientable case.
But we also have $\mu(K_n+\cdots +K_n)=\mu(K_n)=n-1$ (see [1]), contradicting the desired characterization.
[1] van der Holst, Lovász, Schrijver: "The Colin de Verdière graph parameter", Theorem 2.5