Vol. 11, No. 3, 2018

 Recent Issues
 The Journal About the Journal Editorial Board Subscriptions Editors’ Interests Scientific Advantages Submission Guidelines Submission Form Ethics Statement Editorial Login ISSN: 1944-4184 (e-only) ISSN: 1944-4176 (print) Author Index Coming Soon 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
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
Primary: 05C10
Secondary: 57M15