Stop Minding Your P's and Q's: Implementing a Fast and Simple DFS-Based Planarity Testing and Embedding Algorithm

Boyer, John M. and Cortese, Pier Francesco and Patrignani, Maurizio and Di Battista, Giuseppe (2004) Stop Minding Your P's and Q's: Implementing a Fast and Simple DFS-Based Planarity Testing and Embedding Algorithm. In: Graph Drawing 11th International Symposium, GD 2003, September 21-24, 2003, Perugia, Italy , pp. 25-36 (Official URL: http://dx.doi.org/10.1007/978-3-540-24595-7_3).

Full text not available from this repository.

Abstract

In this paper we give a new description of the planarity testing and embedding algorithm presented by Boyer and Myrvold [2], providing, in our opinion, new insights on the combinatorial foundations of the algorithm. Especially, we give a detailed illustration of a fundamental phase of the algorithm, called walk-up, which was only succinctly illustrated in [2]. Also, we present an implementation of the algorithm and extensively test its efficiency against the most popular implementations of planarity testing algorithms. Further, as a side effect of the test activity, we propose a general overview of the state of the art (restricted to efficiency issues) of the planarity testing and embedding field.

Item Type:Conference Paper
Additional Information:10.1007/978-3-540-24595-7_3
Classifications:G Algorithms and Complexity > G.770 Planarity Testing
ID Code:424

Repository Staff Only: item control page

References

K. Booth and G. Lueker. Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms. J. Comput. Syst. Sci., 13, 1976.

J. Boyer and W. Myrvold. Stop minding your P's and Q's: A simplified O(n) planar embedding algorithm. In 10th Annual ACM-SIAM Symposium on Discrete Algorithms, pages 140-146, 1999.

J. Boyer and W. Myrvold. Stop minding your P's and Q's: Simplified planarity by edge addition. 2003. Submitted. Preprint at http://www.pacificcoast.net/~lightning/planarity.ps.

J. M. Boyer, P. Cortese, M. Patrignani, and G. Di Battista. Stop minding your P's and Q's: Implementing a fast and simple DFS-based planarity testing and embedding algorithm. Tech. Report RT-DIA-83-2003, Dept. of Computer Sci., Univ. di Roma Tre, 2003.

N. Chiba, T. Nishizeki, S. Abe, and T. Ozawa. A linear algorithm for embedding planar graphs using PQ-trees. J. Comput. Syst. Sci., 30(1):54-76, 1985.

H. de Fraysseix and P. Rosenstiehl. A characterization of planar graphs by Trémaux orders. Combinatorica, 5(2):127-135, 1985.

H. de Fraysseix and P. Ossona de Medez. P.I.G.A.L.E. - Public Implementation of a Graph Algorithm Library and Editor. SourceForge project page http://sourceforge.net/projects/pigale.

GDToolkit. An object-oriented library for handling and drawing graphs. Third University of Rome, http://www.dia.uniroma3.it/~gdt.

GTL. Graph template library. University of Passau - FMI - Theor. Comp. Science http://infosun.fmi.uni-passau.de/GTL/.

J. Hopcroft and R. E. Tarjan. Efficient planarity testing. J. ACM, 21(4), 1974.

W.-L. Hsu. An efficient implementation for the PC-Tree algorithm of Shih and Hsu's planarity test. Tech. Report, Inst. of Inf. Science, Academia Sinica, 2003.

A. Lempel, S. Even, and I. Cederbaum. An algorithm for planarity testing of graphs. In Theory of Graphs: Internat. Symposium (Rome 1966), pages 215-232, New York, 1967. Gordon and Breach.

K. Mehlhorn and P. Mutzel. On the embedding phase of the Hopcroft and Tarjan planarity testing algorithm. Algorithmica, 16:233-242, 1996.

K. Mehlhorn and S. Näher. LEDA: A Platform for Combinatorial and Geometric Computing. Cambridge University Press, New York, 1998.

W.-K. Shih and W.-L. Hsu. A simple test for planar graphs. In Int. Workshop on Discrete Math. and Algorithms, pages 110-112, 1993.

W.-K. Shih and W.-L. Hsu. A new planarity test. Theor. Comp. Sci., 223, 1999.