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

Pavelescu, Andrei; Pavelescu, Elena

doi:10.2140/agt.2024.24.555

Download this article
	For screen
	For printing

Recent Issues

The Journal

About the Journal

Editorial Board

Subscriptions

Submission Guidelines

Submission Page

Policies for Authors

Ethics Statement

ISSN 1472-2739 (online)

ISSN 1472-2747 (print)

Author Index

To Appear

Other MSP Journals

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

Andrei Pavelescu and Elena Pavelescu

Algebraic & Geometric Topology 24 (2024) 555–568

DOI: 10.2140/agt.2024.24.555

Abstract

A planar graph $G$ is said to be nonseparating if there exists an embedding of $G$ in $ℝ^{2}$ such that, for any cycle $𝒞 \subset 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 \geq 7$ vertices, the complement $c G$ is $(n - 7)$ –apex. This implies that the Colin de Verdière invariant of the complement $c G$ satisfies $μ (c G) \leq 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 G) \geq 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.

Keywords

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

Mathematical Subject Classification

Primary: 57M15

Secondary: 05C10

References

Publication

Received: 12 February 2022

Revised: 8 August 2022

Accepted: 18 October 2022

Published: 18 March 2024

Authors

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

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

Open Access made possible by participating institutions via Subscribe to Open.

Volume 24, issue 1 (2024)