Constructions stemming from non-separating planar graphs and their Colin de Verdière invariant

Abstract

A planar graph $G$ is said to be non-separating if there exists an embedding of $G$ in ${\mathbb{R}}^2$ such that for any cycle $\mathcal{C}\subset G$, all vertices of $G\setminus \mathcal{C}$ are within the same connected component of ${\mathbb{R}}^2\setminus \mathcal{C}$. Dehkordi and Farr classified the non-separating planar graphs as either outerplanar graphs, subgraphs of wheel graphs, or subgraphs of elongated triangular prisms. We use maximal non-separating planar graphs to construct examples of maximal linkless graphs and maximal knotless graphs. We show that for a maximal non-separating planar graph $G$ with $n\ge 7$ vertices, the complement $cG$ is $(n-7)-$apex. This implies that the Colin de Verdière invariant of the complement $cG$ satisfies $\mu (cG)\le n-4$. We show this to be an equality. As a consequence, the conjecture of Kotlov, Lovàsz, and Vempala that for a simple graph $G$, $\mu (G)+\mu (cG)\ge n-2$ is true for 2-apex graphs $G$ for which $G-\{u,v\}$ is planar non-separating. It also follows that complements of non-separating planar graphs of order at least nine are intrinsically linked. We prove that the complements of non-separating planar graphs $G$ of order at least ten are intrinsically knotted.

14 pages, 12 figures

References in corpus (2)

• New bounds on maximal linkless graphs
• Maximal knotless graphs