32
$\begingroup$

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.

Improve this question
$\endgroup$
13
  • 1
    $\begingroup$ 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. $\endgroup$
    – Juho
    Jun 22, 2014 at 16:22
  • 2
    $\begingroup$ If you want just the decision problem IS PLANAR, isn't two forbidden minors whose existence can be checked in polynomial time enough? $\endgroup$
    – joro
    Jun 22, 2014 at 18:16
  • 2
    $\begingroup$ @joro: Yes, of course that would be a simple solution but I would prefer to avoid using such a strong theorem. $\endgroup$
    – domotorp
    Jun 22, 2014 at 18:41
  • 1
    $\begingroup$ 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. $\endgroup$
    – Saeed
    Jun 24, 2014 at 11:52
  • 3
    $\begingroup$ 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. $\endgroup$
    – Chandra Chekuri
    Jun 26, 2014 at 20:37

4 Answers 4

Reset to default
7
$\begingroup$

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.
Improve this answer
$\endgroup$
7
  • $\begingroup$ I edited the answer to avoid using bridges and the overlap graph. $\endgroup$
    – someone
    Jun 27, 2014 at 14:33
  • $\begingroup$ 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. $\endgroup$
    – domotorp
    Jun 27, 2014 at 17:22
  • $\begingroup$ 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. $\endgroup$
    – domotorp
    Jun 27, 2014 at 17:43
  • $\begingroup$ The restriction of $D$ to $G[U\cup V(C)]$ should be planar. Otherwise $G$ is not planar. $\endgroup$
    – someone
    Jun 27, 2014 at 17:49
  • $\begingroup$ In this we agree, but I don't see how this helps. $\endgroup$
    – domotorp
    Jun 27, 2014 at 17:51
3
$\begingroup$

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 by Boyer and Myrvold.

This book chapter surveys many planarity testing algorithms and hopefully you find simple enough algorithm.

Improve this answer
$\endgroup$
1
  • $\begingroup$ 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. $\endgroup$
    – domotorp
    Jun 24, 2014 at 16:13
1
$\begingroup$

What about Hopcroft and Tarjan's 1974 algorithm {1}?

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

Improve this answer
$\endgroup$
1
  • $\begingroup$ It is a fast and not a simple algorithm. $\endgroup$
    – domotorp
    Jun 23, 2014 at 5:26
1
$\begingroup$

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.

Improve this answer
$\endgroup$
1
  • $\begingroup$ Not simple at all. $\endgroup$
    – domotorp
    Jun 24, 2014 at 16:14

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.