Constructions stemming from nonseparating planar graphs and their Colin de Verdière invariant
Andrei Pavelescu, Elena Pavelescu · Algebraic & Geometric Topology · 2024
A planar graph G is said to be nonseparating if there exists an embedding of G in R 2 such that, for any cycle Ꮿ G, all vertices of G n Ꮿ are within the same connected component of R 2 n Ꮿ. Dehkordi and Farr classified the nonseparating planar graphs as either outerplanar graphs, subgraphs of wheel graphs, or subgraphs of elongated triangular prisms.We use maximal nonseparating planar graphs to construct examples of maximal linkless graphs and maximal knotless graphs.We show that, for a maximal nonseparating planar graph G with n 7 vertices, the complement cG is .n7/-apex.This implies that the Colin de Verdière invariant of the complement cG satisfies .cG/Ä 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, .G/ C .cG/ n 2 is true for 2-apex graphs G for which G fu; vg is planar nonseparating.It also follows that complements of nonseparating planar graphs of order at least nine are intrinsically linked.We prove that the complements of nonseparating planar graphs G of order at least ten are intrinsically knotted.