From: Jim Ward Subject: Re: Planarity testing for Graphs Date: 2 Feb 2000 18:00:02 -0600 Newsgroups: sci.math.research,sci.math Summary: [missing] In sci.math Stephen Montgomery-Smith wrote: > I recall seeing an algorithm for testing a graph to see if > it was planar (i.e. can be drawn on the plane with no > edge crossings). This algorithm took linear time (so > for example did not use Kuratoski's theorem). > Could anyone tell me a good reference - both the original > papers, and also a good textbook. "Introduction to Graph Theory" by Douglas B. West (1996) explains a polynomial time algorithm. "Graph Algorithms and NP-Completeness" (1984) by Melhorn explains a (the?) linear time algorithm. He's also written a recent paper (Algorithmica, Vol. 16 #2, Aug. 1996) which probably references older papers. I've been searching the web unsuccessfully for C code that does planarity testing. If anyone knows of some C code anywhere, I would be grateful if they would post it. I have tried to wrestle the above algorithms into C, but the Devil is in the details. ============================================================================== From: gerry@mpce.mq.edu.au (Gerry Myerson) Subject: Re: Planarity testing for Graphs Date: 2 Feb 2000 18:00:08 -0600 Newsgroups: sci.math.research,sci.math In article <3898848C.9C44675A@math.missouri.edu>, Stephen Montgomery-Smith wrote: > I recall seeing an algorithm for testing a graph to see if > it was planar (i.e. can be drawn on the plane with no > edge crossings). This algorithm took linear time (so > for example did not use Kuratoski's theorem). > > Could anyone tell me a good reference - both the original > papers, and also a good textbook. One reference is J E Hopcroft & R E Tarjan, Efficient planarity testing, J Assoc Comput Mach 21 (1974) 549--568. The textbook of J A Bondy & U S R Murty, Graph Theory with Applications, North Holland 1976, has a good description of a not-quite-as-efficient algorithm due to G Demoucron, Y Malgrange, and R Pertuiset, Graphes planaires: reconnaissance et construction de representations planaires topologiques, Rev Francaise Recherche Operationelle 8 (1964) 33-47. My apologies for omitting various accents. Gerry Myerson (gerry@mpce.mq.edu.au) ============================================================================== From: Marcus Raitner Subject: Re: Planarity testing for Graphs Date: 3 Feb 2000 09:10:08 -0600 Newsgroups: sci.math.research,sci.math Stephen Montgomery-Smith writes: > I recall seeing an algorithm for testing a graph to see if > it was planar (i.e. can be drawn on the plane with no > edge crossings). This algorithm took linear time (so > for example did not use Kuratoski's theorem). > > Could anyone tell me a good reference - both the original > papers, and also a good textbook. > There exist two linear time planarity test algorithms. The one of Hopcroft & Tarjan was already mentioned in a previous posting. Hopcroft & Tarjan corrected and improved in their paper an algorithm proposed by Auslander & Parter: @Article{auslander61, author = {Auslander, L. and Parter, S.V.}, title = {On imbedding graphs in the plane}, journal = {J. Math. and Mech.}, year = 1961, volume = 10, number = 3, pages = {517--523} } The other was developed by Lempel, Even & Cederbaum, but didn't have linear complexity in their original paper: @InProceedings{lempel67, author = {Lempel, A. and Even, S. and Cederbaum, I.}, title = {An Algorithm for Planarity Testing of Graphs}, booktitle = {Theory of Graphs, International Symposium, Rome}, pages = {215--232}, year = 1967, editor = {Rosenstiehl, P.} } The linear running time became possible by employing a datastructure called PQ-Tree developed by Booth & Luecker: @Article{booth76, author = {Booth, K. S. and Lueker, G. S.}, title = {Testing for the Consecutive Ones Property, Interval Graphs, and Graph Planarity using PQ-Tree Algorithms}, journal = {Journal of Computers and System Sciences}, year = 1976, volume = 12, pages = {335--379} } A good text book describing both algorithms briefly is @InBook{even79, author = {Even, S.}, title = {Graph Algorithms}, chapter = {7--8}, publisher = {Computer Science Press}, year = 1979, pages = {148--191} } For both algorithms their exist extensions for either computing an embedding if the graph is planar or a witness if the graph isn't planar (Witness means a subgraph homeomorphic to either K5 or K3,3). Both extensions have linear time complexity. I have implemented this algorithm in our library GTL, which is available with source code at http://infosun.fmi.uni-passau.de/GTL/ Marcus Raitner -- -------------------------------------------------------------- Marcus Raitner Lst. Prof. Brandenburg raitner@fmi.uni-passau.de Uni Passau, D-94030 Passau ++49/851/509-3034, FAX: 3032 ============================================================================== From: Dima Pasechnik Subject: Re: Planarity testing for Graphs Date: 3 Feb 2000 09:10:03 -0600 Newsgroups: sci.math.research,sci.math Jim Ward wrote: [...] > I've been searching the web unsuccessfully for C code that does planarity > testing. If anyone knows of some C code anywhere, I would be grateful if > they would post it. I have tried to wrestle the above algorithms into C, > but the Devil is in the details. If you're equally happy with C++, this is a part of LEDA: http://www.mpi-sb.mpg.de/LEDA/MANUAL/plane_graph_alg.html Algorithms for Planar Graphs ( plane_graph_alg ) [...] bool PLANAR(graph& , bool embed=false) PLANAR takes as input a directed graph G(V, E) and performs a planarity test for it. G must not contain selfloops. If the second argument embed has value true and G is a planar graph it is transformed into a planar map (a combinatorial embedding such that the edges in all adjacency lists are in clockwise ordering). PLANAR returns true if G is planar and false otherwise. The algorithm ([41]) has running time O(| V| + | E|). [...] [41] J.E. Hopcroft, R.E. Tarjan: ``Efficient Planarity Testing''. Journal of the ACM, Vol. 21, 549-568, 1974 HTH, -- Dmitrii Pasechnik http://www.cs.uu.nl/staff/dima.html