Fetching the paper…

Reading the bibliography…

2016

Six variations on a theme: almost planar graphs

Lipton, Max, Mackall, Eoin, Mattman, Thomas W. et al.

Original
PDF
Post on X

Understand

A graph is apex if it can be made planar by deleting a vertex, that is, $\exists v$ such that $G-v$ is planar.

We define the related notions of edge apex, $\exists e$ such that $G-e$ is planar, and contraction apex, $\exists e$ such that $G/e$ is planar, as well as the analogues with a universal quantifier: $\forall v$, $G-v$ planar; $\forall e$, $G-e$ planar; and $\forall e$, $G/e$ planar.
The Graph Minor Theorem of Robertson and Seymour ensures that each of these six gives rise to a finite set of obstruction graphs.
For the three definitions with universal quantifiers we determine this set.

Six variations on a theme: almost planar graphs · Around

Built on

K. Kuratowski. Sur le problème des courbes gauches en topologie. Fund. Math
1930
Earlier work this paper cites.
K. Wagner. Über eine Eigenschaft der ebenen Komplexe. Math. Ann
1937
Earlier work this paper cites.
K. Wagner. Fastplättbare Graphen. J. Combinatorial Theory
1967
Earlier work this paper cites.
B.S. Gubser. A characterization of almost-planar graphs. Combin. Probab. Comput
1996
Earlier work this paper cites.

Similar

W. Mader, 3 n − 5 3n-5 edges do force a subdivision of K 5 K_{5} . Combinatorica
1998
Cited alongside, same era.
B. Mohar and C. Thomassen. Graphs on surfaces. Johns Hopkins Studies in the Mathematical Sciences. Johns Hopkins University Press, Baltimore, MD, 2001
2001
Cited alongside, same era.
N. Robertson and P. Seymour. Graph minors. XX. Wagner’s conjecture. J. Combin. Theory Ser. B
2004
Cited alongside, same era.
R. Diestel. Graph theory. Fourth edition. Graduate Texts in Mathematics, 173
2010
Cited alongside, same era.
J. Barsotti and T.W. Mattman. Graphs on 21 edges that are not 2 2 –apex. Preprint
Cited in the paper.

Then

S. Cabello and B. Mohar. Adding one edge to planar graphs makes crossing number and 1-planarity hard. SIAM J. Comput
Original
2013
Later among the works it cites.
H. Ayala. MMNA graphs on eight vertices or fewer. (2014) CSU, Chico Master’s Thesis. Available at http://www.csuchico.edu/~tmattman
2014
Later among the works it cites.
B.D. McKay and A. Piperno. Practical Graph Isomorphism, II. J. Symbolic Computation
2014
Later among the works it cites.
M. Pierce. Searching for and Classifying the Finite Set of Minor-Minimal Non-Apex Graphs. (2014) CSU, Chico Honor’s Thesis. Available at http://www.csuchico.edu/~tmattman
2014
Later among the works it cites.

Beyond the bibliography

alphaXiv searches the wider corpus for related work and actual follow-ups.

Open on alphaXiv

alphaXiv is searching for related work…