On Boolean characterizations of planarity and planar embeddings of graphs (Q2276969)

The author introduces a new planarity characterization for graphs, involving the solution of a quadratic Boolean equation. He then discusses seven combinatorially distinct configurations, called planarity obstacles, which lead to a graph whose order and size are linear functions of those of the original graph. Testing for planarity and finding a planar imbedding of the original graph can be realized algorithmically from the second graph, in linear time. A decomposition of a non-planar graph into ``T-maximal'' planar subgraphs (where T is a spanning tree) is also provided.