StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
text
Body
copied!<p>Regarding planarity...</p> <p>The well known e <= 3v - 6 <a href="http://en.wikipedia.org/wiki/Planar_graph" rel="noreferrer">criteria by Euller</a> mentioned here says that if a graph is planar, then that condition must hold. However, <strong>not</strong> all graphs in which that condition holds are necessarily planar. That is why you actually need a <a href="http://en.wikipedia.org/wiki/Planarity_testing" rel="noreferrer">planarity test algorithm</a>.</p> <p>A thing to notice is that planarity testing algorithms are not easy to implement. There's a very old one which is based on subgraphs finding and removal. I can't remember the original authors right now, but the problem with their algorithm is that it has O(n³) complexity.</p> <p>The first planarity test algorithm considered to be efficient - O(n) in the case - is due to Hopcroft and Tarjan. This was already mentioned here in the post by Yin Zhu. You can find the original paper <a href="http://portal.acm.org/citation.cfm?id=321852" rel="noreferrer">here</a>. </p> <p>This time, the problem with the algorithm was that many people found it too hard to understand and even to implement. So there are papers with the intention of just clarifying points of the original paper. For instance, the <a href="http://bkocay.cs.umanitoba.ca/G&G/articles/Planarity.pdf" rel="noreferrer">Kocay paper</a>.</p> <p>The Hopcraft-Tarjan paper is classic and if you want to try to implement it, the best reference I have is <a href="http://citeseer.ist.psu.edu/old/717789.html" rel="noreferrer">this other paper</a>, which presents the theory together with a C++ implementation. That was written by the people who implemented the algorithm in the <a href="http://www.algorithmic-solutions.com/" rel="noreferrer">LEDA library</a>.</p> <p>Years later after the Hopcroft-Tarjan paper (which was in 1974), others O(n) algorithms were published. I don't know much about them, but some used PC/PQ trees. There is one, however, which I read and found very interesting. It's due to Boyer and Myrvold and it's from 2004. You can find it <a href="http://www.cs.brown.edu/sites/jgaa/accepted/2004/BoyerMyrvold2004.8.3.pdf" rel="noreferrer">here</a>. Besides the algorithm itself, of course, a good thing about this paper is that it provides a rigorous historical reference about planarity test algorithms.</p> <p>Very recently, I discovered a <a href="http://www.sciencedirect.com/science?_ob=ArticleURL&_udi=B75GV-4T5BWKX-12&_user=10&_rdoc=1&_fmt=&_orig=search&_sort=d&_docanchor=&view=c&_searchStrId=1123969666&_rerunOrigin=google&_acct=C000050221&_version=1&_urlVersion=0&_userid=10&md5=c6cbd6708bce2d15e8918c6cf6a1d537" rel="noreferrer">another paper</a> from 2008 in which Tarjan is one of the authors. Haven't checked it yet.</p> <p>Well, if you got tired just by reading this post, I assume you don't want to implement your own algorithm. :) In this case, I can recommend some C++ libraries.</p> <ul> <li><a href="http://www.boost.org/doc/libs/1_41_0/libs/graph/doc/boyer_myrvold.html" rel="noreferrer">Boost</a>.</li> <li><a href="http://www.dia.uniroma3.it/~gdt/gdt4/index.php" rel="noreferrer">GDToolkit</a>.</li> <li><a href="http://www.algorithmic-solutions.com/" rel="noreferrer">LEDA</a>.</li> <li><a href="http://www.ogdf.net/doku.php" rel="noreferrer">OGDF</a>.</li> <li><a href="http://gtad.sourceforge.net/" rel="noreferrer">GTAD</a> - This is my own graph library (which, unfortunately, I haven't been able to work on it lately). There's an implementation of the Hopcroft-Tarjan algorithm, which I wrote based on that paper I mentioned. Since the paper already provides real code, things are a lot easier.</li> </ul>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload