In this paper we give a new description of the planarity testing and embedding algorithm presented by Boyer and Myrvold , 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 . 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.
Weitere Kapitel dieses Buchs durch Wischen aufrufen
- Stop Minding Your P’s and Q’s: Implementing a Fast and Simple DFS-Based Planarity Testing and Embedding Algorithm
John M. Boyer
Pier Francesco Cortese
Giuseppe Di Battista
- Springer Berlin Heidelberg
Neuer Inhalt/© ITandMEDIA