5
$\begingroup$

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.

Improve this question
$\endgroup$
11
  • 7
    $\begingroup$ So complete graph is almost planar? $\endgroup$
    – Fedor Petrov
    Commented Jan 30, 2019 at 19:46
  • $\begingroup$ For that matter what about graphs with Hamiltonian circuits? $\endgroup$
    – Mike
    Commented Jan 30, 2019 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
    Commented Jan 31, 2019 at 1:49
  • 2
    $\begingroup$ Is $H$ supposed to be a spanning subgraph? $\endgroup$
    – Louis Esperet
    Commented Jan 31, 2019 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
    Commented Feb 1, 2019 at 0:17

2 Answers 2

Reset to default
2
$\begingroup$

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.

Improve this answer
$\endgroup$
1
  • 2
    $\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
    Commented Feb 2, 2019 at 2:04
2
$\begingroup$

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."

          Thm1.1
          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$."

Improve this answer
$\endgroup$
1
  • $\begingroup$ thanks for your answer. I am leaning towards using the term Locally Nonplanar graphs instead. $\endgroup$
    – hbm
    Commented Feb 2, 2019 at 2:08

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .