A 2-connected $3$-connected graph $G$ is "Almost Planar" Locally Nonplanar if it has a a $2$-connected spanning subgraph $H$ and an embedding in the plane such that $H$ is planar in this embedding and all the crossing edges are cords of faces of $H$ (all crossings and crossing edges are contained inside the faces of $H$.)
Is there any literature on this class of graphs? Are they classified by any other name? What kind of graphs are in this class? Are there graphs which are not Almost Planar?

Any information on this will be appreciated.

  • 7
    $\begingroup$ So complete graph is almost planar? $\endgroup$ – Fedor Petrov Jan 30 '19 at 19:46
  • $\begingroup$ For that matter what about graphs with Hamiltonian circuits? $\endgroup$ – Mike Jan 30 '19 at 20:56
  • 4
    $\begingroup$ Isn't every graph $G$ almost planar by this definition? Just take an arbitrary spanning forest of $G$ as $H$, draw it without crossings, and draw all the other edges in the outer face of $H$. $\endgroup$ – Jan Kyncl Jan 31 '19 at 1:49
  • 2
    $\begingroup$ Is $H$ supposed to be a spanning subgraph? $\endgroup$ – Louis Esperet Jan 31 '19 at 16:36
  • 3
    $\begingroup$ Subdividing every edge of a non-planar graph will give a graph which is not almost planar because any 2-connected spanning subgraph will have to contain both edges incident to any subdivision vertex, i.e. there is no 2-connected spanning strict subgraph. $\endgroup$ – Florian Lehner Feb 1 '19 at 0:17

According to Kuratowski's theorem a planar graph is characterized by the absence of (subdivisions of) $K_5$ and $K_{3,3}$, where $K_5$ is the infamous pentagram and $K_{3,3}$ can be visualized as a hexagon with opposite vertices connected by edges and also resembles the smallest Möbius Ladder Graph.

My suggestion to construct extremal graph "almost planar" graphs would be to fill the faces of a Fullerene Graph and augment its pentagonal faces to $K_5$ and the hexagonal faces to $K_{3,3}$. I don't think that those graphs have been described already and thus most likely have no name attached yet; maybe "Kuratowski Fullerene" would be acceptable.
Illustration how to fill the faces of fullerene graphs

The illustration shows how to fill the faces of Fullerene Graphs to construct almost planar graphs.

  • 1
    $\begingroup$ Thanks for the contribution. This construction could be applied to any planar graph with girth greater than five. Fullerene might not be the appropriate term to use. I thought of quasi-planar but it is already taken. Locally non-planar graphs might be suitable. $\endgroup$ – hbm Feb 2 '19 at 2:04

OP: "Is there any literature on this class of graphs?"

The term "almost-planar graph" is already firmly in the literature:

Guoli Ding, Joshua Fallon, Emily Marshall. "On almost-planar graphs." arXiv abstract. Mar. 2016.

"A nonplanar graph $G$ is called almost-planar if for every edge $e$ of $G$, at least one of $G \setminus e$ and $G\,/\,e$ is planar."

"A graph $G$ is almost-planar if and only if $G$ is not $\{K_5, K_{3,3}\}$-free but for every edge $e$ of $G$, at least one of $G \setminus e$ and $G\,/\,e$ is $\{K_5, K_{3,3}\}$-free."

          Thm 1.1: The characterization of Gubser.

Gubser, Bradley S. "A characterization of almost-planar graphs." Combinatorics, Probability and Computing 5, no. 3 (1996): 227-245.

"We characterize the almost-planar graphs, those non-planar graphs for which $G \setminus e$ or $G\,/\,e$ is planar, for all edges $e$ of $G$."

  • $\begingroup$ thanks for your answer. I am leaning towards using the term Locally Nonplanar graphs instead. $\endgroup$ – hbm Feb 2 '19 at 2:08

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.