发现在线性时间极大平面图。

A planar graph is a graph that can be drawn on the plane without any crossing. A planarity test is a decision algorithm that determine whether a graph is planar. A certificate to a graph being planar is its planar embedding. On the other hand, a graph is non-planar if and only if it contains a Kuratowski subgraph. There are many algorithm which can do the planarity testing in linear time, some of them are based on a data structure named PQ-tree. Shih and Hsu developed a linear time algorithm which based on PC-tree, a generalization of PQ-tree. Their algorithm can be modified that it can output a maximal planar subgraph if the input graph is non-planar. Note: You may need the Microsoft Visual C++ 2010 Redistributable Package in order to execute this program. The project is still under construction. We may add other planarity-related feature in the near future. See https://code.google.com/p/planarity-algorithms/

source
main.cpp
mps.cpp
mps.h
mps_test.cpp
node.cpp
mps_testing.exe
readme.txt