# Show the following graph is planar

I am trying to show that a graph is planar. Possibly the simplest method I have found is to show the graph can be drawn on a page (i.e. in the plane) without any edges crossing. So, can I assume that if I am given a graph that has edges crossing I can simple move the vertices around to obtain a version such that the edges are not crossing (if such an arrangement exists)?

It may be better to show an example of what I am thinking. Perhaps someone can confirm that what I have done is permutable. Refer to the figure below were I start with the left graph and end with the right graph.

Alternatively, it seems as though one can show a graph is planar if it can be embedded in a disk. I believe the following figure shows such an embedding in a disk

• You should make the numberings match, that is the best way to tell if it is permutable (i.e. you should have 1 and 3 being the vertices of degree 4 in your second picture to match the first). – Morgan Rodgers May 8 '16 at 9:06
• Agreed: it is really unhelpful to label the vertices in a different way after the permutation. In the left-hand drawing, $5$ and $6$ aren't connected, but in the right-hand drawing they are. – Patrick Stevens May 8 '16 at 9:19

Your numbering scheme is confusing. Determining whether two graphs are isomorphic is difficult for humans to do; one of the reasons we label vertices is to help the reader identify that two graphs are isomorphic at a glance. Your numberings are misleading in that regard, because the "isomorphism" sending vertex-$1$-on-the-left to vertex-$1$-on-the-right, through to vertex-$6$-on-the-left to vertex-$6$-on-the-right, is not a graph homomorphism.

The following diagram demonstrates the planar structure and it is easy to see that the two graphs are isomorphic.

I think in your disk embedding you have missed the $4 \to 6$ edge.

Alternative way: Kuratowski's theorem states that a graph is planar iff it contains no subdivision of $K_{3,3}$ and no subdivision of $K_5$.

Clearly the graph contains no subdivision of $K_{3,3}$, because it already has six vertices, and the only six-vertex subdivision of $K_{3,3}$ is $K_{3,3}$ itself. But your graph isn't $K_{3,3}$ because it contains a vertex of degree $4$.

Also it contains no subdivision of $K_5$ because that could only be obtained by adding a single vertex to an edge of $K_5$; the resulting graph would have at least three vertices of order $4$, but your graph only has one.

• I see you point. Well made. However, I would like to do this problem with only the tools I have so far, and Kuratowski's theorem is not one of them yet. See my above added edit. – Jeremy May 8 '16 at 9:56
• I've answered properly now. – Patrick Stevens May 8 '16 at 10:05
• "Determining whether two graphs are isomorphic is" not known to be NP-hard, and is unlikely to be NP-hard - It has a statistical zero-knowledge proof of knowledge, finding hard instances appears to be hard, and this paper claims to solve the problem in quasi-polynomial time. ​ ​ ​ ​ – user57159 May 8 '16 at 23:16
• @RickyDemer Oh dear, my apologies. I even knew about the quasi-polynomial time paper. I'll fix it, thanks. – Patrick Stevens May 9 '16 at 6:46
• You may have been thinking of subgraph isomorphism, which is in fact W[1]-hard, $\hspace{1.39 in}$ even when the small graph is edgeless or a clique. ​ ​ – user57159 May 9 '16 at 23:08