
576 CHAPTER 18. GDTOOLKIT
Embedded planar graphs are modeled by the class plan undi graph, which enriches the
basic topological structure of an undi graph with the description of a set of faces. Following
the philosophy of the library, a plan undi graph object can be created using a construc-
tor that takes as a constant parameter an undi graph object. This constructor applies a
planarity testing algorithm and, if the graph is not planar, a planarization algorithm that
replaces crossings with “dummy” nodes, called crossing nodes.
The planarity testing algorithm implemented in GDToolkit is the one described by Boyer
et al. [BCPD04]; it has been shown ...