Vol. 11, No. 3, 2018

Download this article
Download this article For screen
For printing
Recent Issues

Volume 17
Issue 4, 543–722
Issue 3, 363–541
Issue 2, 183–362
Issue 1, 1–182

Volume 16, 5 issues

Volume 15, 5 issues

Volume 14, 5 issues

Volume 13, 5 issues

Volume 12, 8 issues

Volume 11, 5 issues

Volume 10, 5 issues

Volume 9, 5 issues

Volume 8, 5 issues

Volume 7, 6 issues

Volume 6, 4 issues

Volume 5, 4 issues

Volume 4, 4 issues

Volume 3, 4 issues

Volume 2, 5 issues

Volume 1, 2 issues

The Journal
About the journal
Ethics and policies
Peer-review process
 
Submission guidelines
Submission form
Editorial board
Editors' interests
 
Subscriptions
 
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
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 Ge 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, Ge 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