<p>I am going to describe an algorithm. I am not sure it qualifies as "easy" and some of the proofs are not so easy. </p>

<p>First we break the graph into 3-connected components, as mentioned by Chandra Chekuri.</p>

<ol>
<li>Break the graph into connected components.</li>
<li>Break each connected component into 2-connected components. This can be done in polynomial time checking for each vertex $v$ of each 2-connected component $G_i$ whether $G_i-v$ is connected. </li>
<li>Break each 2-connected component into 3-connected components. This can be done in polynomial time checking for two distinct vertices $v,u$ of each 2-connected component $G_i$ whether $G_i-\{ v,u \}$ is connected. </li>
</ol>

<p>We have reduced the problem to checking whether a 3-connected component of the graph is planar. Let $G$ denote a 3-connected component.</p>

<ol>
<li>Take any cycle $C$ of $G$. </li>
<li>Pin the vertices of $C$ as vertices of a convex polygon. Put each of the other vertices in the barycenter of its neighbors. This leads to a system of linear equations telling the coordinates of each vertex. Let $D$ be the resulting drawing; it may have crossings. </li>
<li>If $D$ has no crossings, we are finished.</li>
<li>Take the vertices $U$ in any connected component of $G-V(C)$. The restriction of $D$ to the induced subgraph $G[U\cup V(C)]$ should be planar. Otherwise, $G$ is not planar. Take any face $F$ in the drawing $D$ restricted to the induced subgraph $G[U\cup V(C)]$, and let $C'$ be the cycle defining $F$. If $G$ is to be planar, then $C'$ must be a facial cycle. (When $C$ is a Hamiltonian cycle, then $C'$ should be constructed using an edge.)</li>
<li>Repeat step 2 with C' instead of C. If the resulting drawing is planar, then $G$ is planar. Else $G$ is not planar.</li>
</ol>

<p>Remarks: </p>

<ul>
<li>Arguing that Tutte's spring embedding gives a planar embedding is not straightforward. I liked the presentation in the book of Edelsbrunner and Harer, Computational Topology, but it is only for triangulations. Colin de Verdiere discusses the spring embedding in <a href="http://www.di.ens.fr/~colin/cours/algo-graphs-surfaces.pdf" rel="nofollow">http://www.di.ens.fr/~colin/cours/algo-graphs-surfaces.pdf</a> , section 1.4. A general reference is Linial, Lovász, Wigderson: Rubber bands, convex embeddings and graph connectivity. Combinatorica 8(1): 91-102 (1988).</li>
<li>Solving a linear system of equations in a polyomial number of arithmetic operations is easy via Gaussian elimination. Solving it using a polyonomial number of bits is not that easy.</li>
</ul>

CC BY-SA 3.0
2014-06-27T14:33:42.017Z
I edited the answer to avoid using bridges and the overlap graph.
someone
CC BY-SA 3.0
2014-06-27T17:22:34.073Z
Suppose every 3-connected component can be embedded. Then what can we deduce about the original graph? Using that 3-connected graphs have (at most) one embedding, probably we can finish from here, but this step must be also done.
domotorp
CC BY-SA 3.0
2014-06-27T17:43:25.703Z
At the end, in step 4, what is a face in a non-planar drawing? I guess this can be still defined in a natural way. And at the very end, "Else G is not planar" does indeed seem quite non-trivial.
domotorp
CC BY-SA 3.0
2014-06-27T17:49:24.560Z
The restriction of $D$ to $G[U\cup V(C)]$ should be planar. Otherwise $G$ is not planar.
someone
CC BY-SA 3.0
2014-06-27T17:51:19.667Z
In this we agree, but I don't see how this helps.
domotorp
CC BY-SA 3.0
2014-06-27T17:52:34.180Z
There is some standard reduction to 3-connected graphs. If $G=G_1\cup G_2$, $G_1$ and $G_2$ are connected and $G_1\cap G_2=\{ u,v\}$ (so $\{u,v\}$ is a 2-node cut and each side is connected), then $G$ is planar iff $G_1+uv$ and $G_2+uv$ are planar.
someone
CC BY-SA 3.0
2014-06-27T17:57:52.870Z
Let us [continue this discussion in chat](http://chat.stackexchange.com/rooms/15385/discussion-between-someone-and-domotorp). Trying to see how it works...
someone
CC BY-SA 3.0
2014-06-27T09:05:23.853Z
2014-06-28T06:18:15.923Z
2014-06-28T06:18:15.923Z
someone
<p>The algorithm of Boyer and Myrvold is considered among the state of art of planarity testing algorithms</p>

<p><a href="http://jgaa.info/accepted/2004/BoyerMyrvold2004.8.3.pdf" rel="nofollow">On the Cutting Edge:
Simplified O(n) Planarity by Edge Addition</a> by Boyer and Myrvold.</p>

<p>This <a href="http://cs.brown.edu/~rt/gdhandbook/chapters/planarity.pdf" rel="nofollow">book chapter</a> surveys many planarity testing algorithms and hopefully you find simple enough algorithm.</p>

CC BY-SA 3.0
2014-06-24T16:13:22.147Z
I am not interested in the cutting edge of planarity algorithms, I want something easy to explain. I could not find anything simpler than the Demoucron, Malgrange and Pertuiset (DMP) algorithm in the book either.
domotorp
CC BY-SA 3.0
2014-06-23T22:16:29.993Z
2014-06-23T22:31:54.773Z
2014-06-23T22:31:54.773Z
Mohammad Al-Turkistany
<p>What about Hopcroft and Tarjan's 1974 algorithm <a href="http://dl.acm.org/citation.cfm?id=321852" rel="nofollow">{1}</a>?</p>

<hr>

<p>{1} Hopcroft, John, and Robert Tarjan. "Efficient planarity testing." Journal of the ACM (JACM) 21.4 (1974): 549-568.</p>

CC BY-SA 3.0
2014-06-23T05:26:46.987Z
It is a fast and not a simple algorithm.
domotorp
CC BY-SA 3.0
2014-06-23T04:21:01.543Z
2014-06-23T04:21:01.543Z
Ari Trachtenberg
<p>Two algorithms, both in LogSpace</p>

<ol>
<li>Eric Allender and Meena Mahajan - The Complexity of Planarity Testing</li>
<li>Samir Datta and Gautam Prakriya - Planarity Testing Revisited</li>
</ol>

<p>The second is much simpler than the first.</p>

CC BY-SA 3.0
2014-06-24T16:14:56.007Z
Not simple at all.
domotorp
CC BY-SA 3.0
2014-06-23T20:14:44.243Z
2014-06-23T20:14:44.243Z
Anonymous
<p>There are several algorithms that decide in polynomial time whether a graph can be drawn in the plane or not, even many with a linear running time. However, I could not find a very simple algorithm that one could easily and fast explain in class and would show that PLANARITY is in P. Do you know any?</p>
<p>If necessary, you can use Kuratowski's or Fary's theorem but no deep stuff, like the graph minor theorem.
Also note that I do not care about the running time, I just want something polynomial.</p>
<p>Below are the so far 3 best algorithms, showing a simplicity/no-deep-theory-needed trade-off.</p>
<blockquote>
<p>Algorithm 1: Using that we can check whether a graph contains a <span class="math-container">$K_5$</span> or a <span class="math-container">$K_{3,3}$</span> as a minor in polynomial time, we get a very simple algorithm using deep theory. (Note that this theory already uses graph embeddings, as pointed by Saeed, so this is not a real algorithmic approach, just something simple to tell students who already knew/accepted the graph minor theorem.)</p>
<p>Algorithm 2 [based on someone's answer]: It is easy to see that it is enough to deal with 3-connected graphs. For these, find a face and then apply Tutte's spring theorem.</p>
<p>Algorithm 3 [recommended by Juho]: Demoucron, Malgrange and Pertuiset (DMP) algorithm. Draw a cycle, components of remaining graph are called fragments, we embed them in a suitable way (meanwhile creating new fragments). This approach uses no other theorems.</p>
</blockquote>

CC BY-SA 3.0
2014-06-22T10:57:02.760Z
Consider examining the Sage algorithm/references. Some references from the comments: "John M. Boyer. "Simplified O(n) Algorithms for Planar Graph Embedding,
  Kuratowski Subgraph Isolation, and Related Problems". Ph.D. Dissertation,
  University of Victoria, 2001"
joro
CC BY-SA 3.0
2014-06-22T16:22:11.733Z
I think many agree the simplest polynomial time algorithm is the Demoucron, Malgrange and Pertuiset (DMP) algorithm. It is an algorithm textbooks typically cover (see e.g. Gibbons 1985 or Bondy & Murty 1976). Is it enough to just decide planarity, or should the algorithm also output a planar embedding? IIRC the SODA'99 paper of Boyer and Myrvold @joro probably refers to leaves out details, especially regarding the time complexity.
Juho
CC BY-SA 3.0
2014-06-22T17:34:17.693Z
@Juho: Indeed the algorithm is not too complicated but I really hope for some simpler criteria using which we don't have to ``dirty'' our hands and go into details of the drawing.
domotorp
CC BY-SA 3.0
2014-06-22T18:16:57.120Z
If you want just the decision problem IS PLANAR, isn't [two forbidden minors](https://en.wikipedia.org/wiki/Wagner%27s_theorem) whose existence can [be checked in polynomial time](http://rjlipton.wordpress.com/2010/04/05/graph-isomorphism-and-graph-minors/) enough?
joro
CC BY-SA 3.0
2014-06-22T18:41:30.080Z
@joro: Yes, of course that would be a simple solution but I would prefer to avoid using such a strong theorem.
domotorp
CC BY-SA 3.0
2014-06-24T11:52:00.387Z
Algorithm that I mentioned was basically Auslander-Parter algorithm. The problem in my algorithm was the part 7 when I said we can bipartition graph of components. We can in the original algorithm but in the algorithm that I said we need more precise definitions of components and it was out of my keen to explain it in detail. The recursive part was clearly true (if we can do step 7 then we are done), where you doubt about its correctness. I didn't update my answer because I saw it will be around two pages and I cannot abbreviate it more and it's not good to call it simple.
Saeed
CC BY-SA 3.0
2014-06-24T16:16:45.757Z
@Saeed: Thank you very much for finding out the name of the algorithm and I am sorry it turned out to be more complicated than it first seemed.
domotorp
CC BY-SA 3.0
2014-06-26T16:36:03.097Z
If I were to teach something like this, I would perhaps go with Tutte's spring embedding for triangulations: Try each triangle as the outer face and solve the linear system of equations. One problem is that one has to assume that the linear system can be solved in polynomial time. I liked the presentation in the book of Edelsbrunner and Harer, Computational Topology.
someone
CC BY-SA 3.0
2014-06-26T16:43:03.240Z
If you have done flows, you can also reduce it to the 3-connected case using a polynomial number of flow problems. One could then use Tutte's embedding for each 3-connected component, but I do not know how to find a facial cycle fast...
someone
CC BY-SA 3.0
2014-06-26T17:23:51.087Z
@someone: I am interested in how you would do this, so I would appreciate it if you could convert these comments into a more detailed answer.
domotorp
CC BY-SA 3.0
2014-06-26T20:37:54.740Z
Reducing to 3-connected case is a conceptually simple and should be explained in any case. If we are not too interested in efficiency reducing to 3-connected case can be easily done. Check all 2-node cuts.
Chandra Chekuri
CC BY-SA 3.0
2014-06-27T03:08:15.287Z
@Chandra: Check what for them? I don't think this is so simple.
domotorp
CC BY-SA 3.0
2014-06-28T11:38:44.100Z
What's your first algorithm reference? If it's graph minor theorem, that is already based on embedding a graph on surfaces, so we cannot expect to get any algorithm (it's a loop).
Saeed
<graph-algorithms><co.combinatorics><planar-graphs>
What is simplest polynomial algorithm for PLANARITY?
domotorp
# What is simplest polynomial algorithm for PLANARITY?

(Asked by: username_0 on 2014-06-22)

There are several algorithms that decide in polynomial time whether a graph can be drawn in the plane or not, even many with a linear running time. However, I could not find a very simple algorithm that one could easily and fast explain in class and would show that PLANARITY is in P. Do you know any?

If necessary, you can use Kuratowski's or Fary's theorem but no deep stuff, like the graph minor theorem.
Also note that I do not care about the running time, I just want something polynomial.

Below are the so far 3 best algorithms, showing a simplicity/no-deep-theory-needed trade-off.

> Algorithm 1: Using that we can check whether a graph contains a $K\_5$ or a $K\_{3,3}$ as a minor in polynomial time, we get a very simple algorithm using deep theory. (Note that this theory already uses graph embeddings, as pointed by Saeed, so this is not a real algorithmic approach, just something simple to tell students who already knew/accepted the graph minor theorem.)
>
> Algorithm 2 [based on someone's answer]: It is easy to see that it is enough to deal with 3-connected graphs. For these, find a face and then apply Tutte's spring theorem.
>
> Algorithm 3 [recommended by Juho]: Demoucron, Malgrange and Pertuiset (DMP) algorithm. Draw a cycle, components of remaining graph are called fragments, we embed them in a suitable way (meanwhile creating new fragments). This approach uses no other theorems.

**Tags:** graph-algorithms, co.combinatorics, planar-graphs
> **Comments:**
> **username_1**: Consider examining the Sage algorithm/references. Some references from the comments: "John M. Boyer. "Simplified O(n) Algorithms for Planar Graph Embedding,   Kuratowski Subgraph Isolation, and Related Problems". Ph.D. Dissertation,   University of Victoria, 2001"  
> **username_2**: I think many agree the simplest polynomial time algorithm is the Demoucron, Malgrange and Pertuiset (DMP) algorithm. It is an algorithm textbooks typically cover (see e.g. Gibbons 1985 or Bondy & Murty 1976). Is it enough to just decide planarity, or should the algorithm also output a planar embedding? IIRC the SODA'99 paper of Boyer and Myrvold @joro probably refers to leaves out details, especially regarding the time complexity.  
> **username_0**: @Juho: Indeed the algorithm is not too complicated but I really hope for some simpler criteria using which we don't have to ``dirty'' our hands and go into details of the drawing.  
> **username_1**: If you want just the decision problem IS PLANAR, isn't [two forbidden minors](https://en.wikipedia.org/wiki/Wagner%27s_theorem) whose existence can [be checked in polynomial time](http://rjlipton.wordpress.com/2010/04/05/graph-isomorphism-and-graph-minors/) enough?  
> **username_0**: @joro: Yes, of course that would be a simple solution but I would prefer to avoid using such a strong theorem.  
> **username_3**: Algorithm that I mentioned was basically Auslander-Parter algorithm. The problem in my algorithm was the part 7 when I said we can bipartition graph of components. We can in the original algorithm but in the algorithm that I said we need more precise definitions of components and it was out of my keen to explain it in detail. The recursive part was clearly true (if we can do step 7 then we are done), where you doubt about its correctness. I didn't update my answer because I saw it will be around two pages and I cannot abbreviate it more and it's not good to call it simple.  
> **username_0**: @Saeed: Thank you very much for finding out the name of the algorithm and I am sorry it turned out to be more complicated than it first seemed.  
> **username_4**: If I were to teach something like this, I would perhaps go with Tutte's spring embedding for triangulations: Try each triangle as the outer face and solve the linear system of equations. One problem is that one has to assume that the linear system can be solved in polynomial time. I liked the presentation in the book of Edelsbrunner and Harer, Computational Topology.  
> **username_4**: If you have done flows, you can also reduce it to the 3-connected case using a polynomial number of flow problems. One could then use Tutte's embedding for each 3-connected component, but I do not know how to find a facial cycle fast...  
> **username_0**: @someone: I am interested in how you would do this, so I would appreciate it if you could convert these comments into a more detailed answer.  
> **username_5**: Reducing to 3-connected case is a conceptually simple and should be explained in any case. If we are not too interested in efficiency reducing to 3-connected case can be easily done. Check all 2-node cuts.  
> **username_0**: @Chandra: Check what for them? I don't think this is so simple.  
> **username_3**: What's your first algorithm reference? If it's graph minor theorem, that is already based on embedding a graph on surfaces, so we cannot expect to get any algorithm (it's a loop).  

---

## 4 answers

### Answer by username_4 on 2014-06-27. Score: 7

I am going to describe an algorithm. I am not sure it qualifies as "easy" and some of the proofs are not so easy.

First we break the graph into 3-connected components, as mentioned by Chandra Chekuri.

1. Break the graph into connected components.
2. Break each connected component into 2-connected components. This can be done in polynomial time checking for each vertex $v$ of each 2-connected component $G\_i$ whether $G\_i-v$ is connected.
3. Break each 2-connected component into 3-connected components. This can be done in polynomial time checking for two distinct vertices $v,u$ of each 2-connected component $G\_i$ whether $G\_i-\{ v,u \}$ is connected.

We have reduced the problem to checking whether a 3-connected component of the graph is planar. Let $G$ denote a 3-connected component.

1. Take any cycle $C$ of $G$.
2. Pin the vertices of $C$ as vertices of a convex polygon. Put each of the other vertices in the barycenter of its neighbors. This leads to a system of linear equations telling the coordinates of each vertex. Let $D$ be the resulting drawing; it may have crossings.
3. If $D$ has no crossings, we are finished.
4. Take the vertices $U$ in any connected component of $G-V(C)$. The restriction of $D$ to the induced subgraph $G[U\cup V(C)]$ should be planar. Otherwise, $G$ is not planar. Take any face $F$ in the drawing $D$ restricted to the induced subgraph $G[U\cup V(C)]$, and let $C'$ be the cycle defining $F$. If $G$ is to be planar, then $C'$ must be a facial cycle. (When $C$ is a Hamiltonian cycle, then $C'$ should be constructed using an edge.)
5. Repeat step 2 with C' instead of C. If the resulting drawing is planar, then $G$ is planar. Else $G$ is not planar.

Remarks:

* Arguing that Tutte's spring embedding gives a planar embedding is not straightforward. I liked the presentation in the book of Edelsbrunner and Harer, Computational Topology, but it is only for triangulations. Colin de Verdiere discusses the spring embedding in <http://www.di.ens.fr/~colin/cours/algo-graphs-surfaces.pdf> , section 1.4. A general reference is Linial, Lovász, Wigderson: Rubber bands, convex embeddings and graph connectivity. Combinatorica 8(1): 91-102 (1988).
* Solving a linear system of equations in a polyomial number of arithmetic operations is easy via Gaussian elimination. Solving it using a polyonomial number of bits is not that easy.

> **Comments:**
> **username_4**: I edited the answer to avoid using bridges and the overlap graph.  
> **username_0**: Suppose every 3-connected component can be embedded. Then what can we deduce about the original graph? Using that 3-connected graphs have (at most) one embedding, probably we can finish from here, but this step must be also done.  
> **username_0**: At the end, in step 4, what is a face in a non-planar drawing? I guess this can be still defined in a natural way. And at the very end, "Else G is not planar" does indeed seem quite non-trivial.  
> **username_4**: The restriction of $D$ to $G[U\cup V(C)]$ should be planar. Otherwise $G$ is not planar.  
> **username_0**: In this we agree, but I don't see how this helps.  
> **username_4**: There is some standard reduction to 3-connected graphs. If $G=G_1\cup G_2$, $G_1$ and $G_2$ are connected and $G_1\cap G_2=\{ u,v\}$ (so $\{u,v\}$ is a 2-node cut and each side is connected), then $G$ is planar iff $G_1+uv$ and $G_2+uv$ are planar.  
> **username_4**: Let us [continue this discussion in chat](http://chat.stackexchange.com/rooms/15385/discussion-between-someone-and-domotorp). Trying to see how it works...  

---

### Answer by username_6 on 2014-06-23. Score: 3

The algorithm of Boyer and Myrvold is considered among the state of art of planarity testing algorithms

[On the Cutting Edge:
Simplified O(n) Planarity by Edge Addition](http://jgaa.info/accepted/2004/BoyerMyrvold2004.8.3.pdf) by Boyer and Myrvold.

This [book chapter](http://cs.brown.edu/~rt/gdhandbook/chapters/planarity.pdf) surveys many planarity testing algorithms and hopefully you find simple enough algorithm.

> **Comments:**
> **username_0**: I am not interested in the cutting edge of planarity algorithms, I want something easy to explain. I could not find anything simpler than the Demoucron, Malgrange and Pertuiset (DMP) algorithm in the book either.  

---

### Answer by username_7 on 2014-06-23. Score: 1

What about Hopcroft and Tarjan's 1974 algorithm [{1}](http://dl.acm.org/citation.cfm?id=321852)?

---

{1} Hopcroft, John, and Robert Tarjan. "Efficient planarity testing." Journal of the ACM (JACM) 21.4 (1974): 549-568.

> **Comments:**
> **username_0**: It is a fast and not a simple algorithm.  

---

### Answer by username_8 on 2014-06-23. Score: 1

Two algorithms, both in LogSpace

1. Eric Allender and Meena Mahajan - The Complexity of Planarity Testing
2. Samir Datta and Gautam Prakriya - Planarity Testing Revisited

The second is much simpler than the first.

> **Comments:**
> **username_0**: Not simple at all.  

---

