The Colin de Verdière number and sphere representations of a graph (Q1280274)

This paper investigates \(\mu(G)\), the Colin de Verdière number of \(G\) [see J. Comb. Theory, Ser. B 50, No. 1, 11-21 (1990; Zbl 0742.05061)]. The results which nicely complement those of Colin de Verdière's are as follows (\(n\) is the number of nodes, no two being twins). Those graphs with \(\mu(G)\geq n-3\) are described. \(\mu(G)\geq n-3\) (resp. \(n-4\)) implies that \(\overline{G}\) is outerplanar (resp. planar). If \(\overline{G}\) is the union of paths, is outerplanar, or is planar, then \(\mu(G)\geq n-3\), \(n-4\), or \(n-5\), respectively. Every graph has a subdivision \(G\) with \(\mu(\overline{G})\geq n-5\). If \(G\) is a maximal planar graph then \(\mu(\overline{G})\geq n-4\) iff no circuit of length 3 or 4 separates \(G\) into two parts with at least 2 nodes in each and \(G\) is different from 5 specific graphs. If \(G\) is planar with an edge-transitive automorphism group different from the octahedron group then \(\mu(\overline{G})\geq n-4\). \(G\) is planar iff \(\mu(\overline{H})\geq n-4\) where \(H\) is obtained from \(G\) by subdividing every edge by a node. The main tool in the proofs is an equivalent definition of \(\mu(G)\) using vector labelings.