Constructions stemming from nonseparating planar graphs and their Colin de Verdière invariant

Pavelescu, Andrei¹ ; Pavelescu, Elena¹

¹ Department of Mathematics and Statistics, University of South Alabama, Mobile, AL, United States

Algebraic and Geometric Topology, Tome 24 (2024) no. 1, pp. 555-568

Résumé

A planar graph G is said to be nonseparating if there exists an embedding of G in ℝ2 such that, for any cycle 𝒞⊂ G, all vertices of G ∖𝒞 are within the same connected component of ℝ2 ∖𝒞. 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 (n−7)–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) + μ(cG) ≥ n − 2 is true for 2–apex graphs G for which G −{u,v} 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.

Détail

DOI : 10.2140/agt.2024.24.555

Keywords: nonseparating planar graph, Colin de Verdière invariant, intrinsically linked graph, intrinsically knotted graph