Edge Addition Planarity Suite and Generalized Graph Library

A graph is a mathematical structure comprising a set 𝑉 of vertices and a set 𝐸 of edges, with each edge 𝑒 corresponding to a pair of vertices called the endpoints of 𝑒.A graph is planar if its vertices can be placed in distinct locations on a plane surface and its edges can be drawn on the plane without the edges intersecting, except at their common vertex endpoints.For a planar graph, a planarity algorithm typically outputs a combinatorial data structure that validation code can use to certify the planarity of the input graph.A planar graph drawing is typically produced by a separate algorithm.On the other hand, if an input graph is not planar, then a planarity algorithm typically outputs a minimal subgraph of the input graph that obstructs planarity.Validation code can use a minimal planarity-obstructing subgraph to certify the non-planarity of an input graph.Moreover, a minimal subgraph obstructing planarity can be used to help decide how to amend an input graph to planarize it.