A poor man's realization of Demoucron-Malgrange-Pertuiset algorithm [Articol]

Abstract

An implementation of the Demoucron-Malgrange-Pertuiset (DMP) algorithm is proposed, based on specifying the notion of a segment (fragment, bridge) and developing an algorithm for calculating and updating the segments after each iteration using a depth-first search strategy (DFS). The algorithm also works for nonplanar undirected graphs by finally constructing a planar subgraph and displaying the list of segments that cannot be embedded, so as they generate edge intersections when drawing.