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 , 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
URI: http://gdea.informatik.uni-koeln.de/id/eprint/424

Actions (login required)

View Item View Item