1
$\begingroup$

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.

enter image description here

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

enter image description here

$\endgroup$
  • $\begingroup$ 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). $\endgroup$ – Morgan Rodgers May 8 '16 at 9:06
  • $\begingroup$ 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. $\endgroup$ – Patrick Stevens May 8 '16 at 9:19
2
$\begingroup$

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.

Planar graph

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.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Jeremy May 8 '16 at 9:56
  • $\begingroup$ I've answered properly now. $\endgroup$ – Patrick Stevens May 8 '16 at 10:05
  • $\begingroup$ "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. ​ ​ ​ ​ $\endgroup$ – user57159 May 8 '16 at 23:16
  • $\begingroup$ @RickyDemer Oh dear, my apologies. I even knew about the quasi-polynomial time paper. I'll fix it, thanks. $\endgroup$ – Patrick Stevens May 9 '16 at 6:46
  • 1
    $\begingroup$ 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. ​ ​ $\endgroup$ – user57159 May 9 '16 at 23: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.