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. -
JOHN MICHAEL, B., PIER FRANCESCO, C., Patrignani, M., DI BATTISTA, G. (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, Perugia, Italy, September 2003, Revised Papers (pp. 25-36). BERLIN : Springer [10.1007/978-3-540-24595-7_3].
Stop Minding Your P's and Q's: Implementing a Fast and Simple DFS-based Planarity Testing and Embedding Algorithm
PATRIGNANI, Maurizio;DI BATTISTA, Giuseppe
2004-01-01
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. -I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
