0
$\begingroup$

Is the following correct?

A graph is planar when the same graph can be drawn without any edge crossings.

The only way to show that a graph is planar is to draw a planar representation of it.

A graph is not planar when:

  1. $e \le 3v - 6$ is false ($v \ge 3$)
  2. $e \le 2v - 4$ is false (The graph has no cycle of length $3$ and $v \ge 3$)
  3. The graph is nonplanar iff it contains a subgraph homeomorphic to $K_{3,3}$ or $K_{5}$ (Kuratowski's Theorem)

However, if (1) and (2) are true then we cannot say that the graph is planar. For the third condition, we have to first find a subgraph then proceed to show through elementary subdivisions that the subgraph is a homeomorphism to $K_{3,3}$ or $K_{5}$

Is this understanding correct?

Thanks for your time!

$\endgroup$
2
  • $\begingroup$ By Euler's formula ($v-e+f=2$), couldn't we say that (2) supersedes (1) making (1) unnecessary? $\endgroup$ – Eli Sadoff Dec 7 '16 at 17:57
  • $\begingroup$ @EliSadoff Yes, I believe that (2) is found in a similar way to (1). However, there is an extra condition i.e. "no cycle of length 3" which helps show that $K_{3,3}$ is non-planar which (1) cannot do. $\endgroup$ – Jeel Shah Dec 7 '16 at 17:58
0
$\begingroup$

Yeah, everything you've written seems correct. I don't like your line, "The only way to show that a graph is planar is to draw a planar representation of it." Certainly that is the easiest way, but not the only way. You could show that a graph does not have a subgraph homeomorphic to $K_5$ or $K_{3,3}$ to show it is planar.

$\endgroup$

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.