Is this graph planar?

Question

I know almost nothing when it comes to graph theory.

I have this graph which i am told is not planar.

I know that for planar graphs no edge can cross another edge and that for planar graphs $v - e + r = 1$ where $v = |V|$ is the number of vertices, e = |E| is the number of edges and $r$ is the number of minimal enclosed regions.

My graph meets these criteria.

To show that it is not planar, if that is the case, should i try to find a graph that it is isomorphic to which is not planar?

Any ideas on how to do that?

This is my graph with an improved version on the right:

Answer 1

Yes, the above graph is planar, because it admits a plane drawing. A plane drawing is a drawing without edge-crossings much like yours above, and finding such a drawing is already a valid proof of planarity.

To show that some other graph is not planar, you could first check if it perhaps has too many edges (i.e. more than $3n-6$ if the graph has $n$ vertices) or, if this fails, you could look for a subdivision or a minor isomorphic to one of the graphs $K_{3,3}$ or $K_5$. Both latter statements are characteristic of non-planarity and hence the methods always work (at least in principle). You can look up details and definitions by googling Kuratowski's theorem.

Also, I'd be careful saying that $r$ is the number of minimally enclosed regions as this number would not quite be well-defined if the graph were drawn on the surface of a sphere (which is a perfectly fine equivalent definition of planarity) - it is safer to think of the infinite region as an extra region of the graph, in which case the polyhedral formula for connected planar graphs modifies to $v-e+r=2$.

Answer 2

As the definition of planar graph states that " a planar graph is a graph that can be embedded in the plane, i.e.,it can be drawn in such a way that no edges cross each other."

Your given graph is already drawn in such a way that no edges cross each other.

---

Alternative way : For a simple, connected, planar graph with $v$ vertices and $e$ edges, the following simple conditions hold:

Theorem $1.$ If $v ≥ 3$ then $e ≤ 3v − 6$;

Theorem $2.$ If $v ≥ 3$ and there are no cycles of length $3$, then $e ≤ 2v − 4$.

Given, graph has $e=13$ and $v=9$, therefore:

$\implies e ≤ 3v − 6$

$\implies 13 ≤ 3\times 9 − 6$

$\implies 13 ≤ 21$ is true, so graph is planar.

Note that these theorems provide necessary conditions for planarity that are not sufficient conditions, and therefore can only be used to prove a graph is not planar, not that it is planar.

---

Another way: Euler's formula states that if a finite, connected, planar graph is drawn in the plane without any edge intersections, and $v$ is the number of vertices, $e$ is the number of edges and $f$ is the number of faces (regions bounded by edges, including the outer, infinitely large region), then

$\implies f=e-n+(k+1)$

where $k$ is number of connected component.(for given graph $f=6$, five bounded region and one unbounded region and $k=1$, since connected graph).

Therefore,

$\implies 6=13-9+(1+1)$

$\implies 6=6$ is true, so graph is planar.