Sphere Representations, Stacked Polytopes, and the Colin de Verdière Number of a Graph

  • Lon Mitchell
  • Lynne Yengulalp
Keywords: Colin de Verdière invariant, Chordal graphs, Sphere representations, Stacked polytopes

Abstract

We prove that a $k$-tree can be viewed as a subgraph of a special type of $(k+1)$-tree that corresponds to a stacked polytope and that these "stacked'' $(k+1)$-trees admit representations by orthogonal spheres in $\mathbb{R}^{k+1}$. As a result, we derive lower bounds for Colin de Verdière's $\mu$ of complements of partial $k$-trees and prove that $\mu(G) + \mu(\overline{G}) \geq |G| - 2$ for all chordal $G$.
Published
2016-01-22
Article Number
P1.9