The Colin de Verdière number and sphere representations of a graph
type: Item
instance of: scholarly article
title: The Colin de Verdière number and sphere representations of a graph
zbMATH Open document ID: 0910.05056
DOI: 10.1007/BF01195002
author: Andrew Kotlow
author: Santosh S. Vempala
author: László Lovász
published in: Combinatorica
publication date: 1999-03-14T00:00:00Z
review text: 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.
Mathematics Subject Classification ID: 05C75
Mathematics Subject Classification ID: 05C10
zbMATH DE Number: 1261164
zbMATH Keywords: planar graphs
zbMATH Keywords: graph invariants
zbMATH Keywords: outerplanar
zbMATH Keywords: subdivision
zbMATH Keywords: automorphism group
reviewed by: Péter Komjáth
MaRDI profile type: Publication
cites work: Sur un nouvel invariant des graphes et un critère de planarité. (On a new graph invariant and a planarity criterion)
cites work: Q4273839
cites work: A short proof of the planarity characterization of Colin de Verdière
cites work: Sachs' linkless embedding conjecture
cites work: Embeddings of graphs in Euclidean spaces
cites work: Geometrical embeddings of graphs
cites work: Coin graphs, polyhedra, and conformal mapping
cites work: On Hadwiger's number---A problem of the Nordhaus-Gaddum type
cites work: Infinitesimally Rigid Polyhedra. I. Statics of Frameworks
Recommended article: A short proof of the planarity characterization of Colin de Verdière
Recommended article: Multiplicités des valeurs propres et transformations étoile-triangle des graphes
Recommended article: A reduction procedure for the Colin de Verdière number of a graph
Recommended article: The extremal function and Colin de Verdière graph parameter
Recommended article: Q4021376
Recommended article: On the Colin de Verdière number of graphs
Recommended article: On Vertex Partitions and the Colin de Verdière Parameter
Recommended article: Q4400781
Recommended article: On the Colin de Verdière numbers of Cartesian graph products
Recommended article: Q3760574
description: scientific article; zbMATH DE number 1261164