Six variations on a theme: almost planar graphs

Lipton, Max; Mackall, Eoin; Mattman, Thomas W.; Pierce, Mike; Robinson, Samantha; Thomas, Jeremy; Weinschelbaum, Ilan

doi:10.2140/involve.2018.11.413

Download this article
	For screen
	For printing

Recent Issues

The Journal

About the journal

Ethics and policies

Peer-review process

Submission guidelines

ISSN 1944-4184 (online)

ISSN 1944-4176 (print)

Author index

To appear

Other MSP journals

Six variations on a theme: almost planar graphs

Max Lipton, Eoin Mackall, Thomas W. Mattman, Mike Pierce, Samantha Robinson, Jeremy Thomas and Ilan Weinschelbaum

Vol. 11 (2018), No. 3, 413–448

DOI: 10.2140/involve.2018.11.413

Abstract

A graph is apex if it can be made planar by deleting a vertex, that is, there exists $v$ such that $G - v$ is planar. We also define several related notions; a graph is edge apex if there exists $e$ such that $G - e$ is planar, and contraction apex if there exists $e$ such that $G ∕ e$ is planar. Additionally we define the analogues with a universal quantifier: for all $v$ , $G - v$ is planar; for all $e$ , $G - e$ is planar; and for all $e$ , $G ∕ e$ is planar. The graph minor theorem of Robertson and Seymour ensures that each of these six notions gives rise to a finite set of obstruction graphs. For the three definitions with universal quantifiers we determine this set. For the remaining properties, apex, edge apex, and contraction apex, we show there are at least 36, 55, and 82 obstruction graphs respectively. We give two similar approaches to almost nonplanar (there exists $e$ such that $G + e$ is nonplanar, and for all $e$ , $G + e$ is nonplanar) and determine the corresponding minor minimal graphs.

Keywords

apex graphs, planar graphs, forbidden minors, obstruction set

Mathematical Subject Classification 2010

Primary: 05C10

Secondary: 57M15

Milestones

Received: 28 February 2015

Revised: 9 August 2016

Accepted: 22 May 2017

Published: 20 October 2017

Communicated by Joel Foisy

Authors

Max Lipton
Department of Mathematics Cornell University Ithaca, NY United States

Eoin Mackall
Department of Mathematics and Statistics California State University Chico, CA United States

Thomas W. Mattman
Department of Mathematics and Statistics California State University Chico, CA United States

Mike Pierce
Department of Mathematics and Statistics California State University Chico, CA United States

Samantha Robinson
Etna High School Etna, CA United States

Jeremy Thomas
Department of Mathematics and Statistics California State University Chico, CA United States

Ilan Weinschelbaum
Department of Mathematics and Computer Science Wesleyan University Middletown, CT United States

Vol. 11, No. 3, 2018