The first polynomial-time test for this property was written by Shih and Hsu in 1999, but it is still outperformed by the 1974 algorithm of Hopcroft and Tarjans in many cases.
The first polynomial-time test for this property was written by Shih and Hsu in 1999, but it is still outperformed by the 1974 algorithm of Hopcroft and Tarjans in many cases. A famous instructive example regarding this, the Petersen star, does not possess it because removing an outer vertex creates an object homeomorphic to K-three-three. Kuratowski's theorem given the necessary and sufficient conditions for it to hold for a graph and every graph with this property is four-colorable by the four-color theorem. FTP, name this property of graphs that may be unambiguously embedded on a surface, or drawn without crossing a line or lifting the drawing implement.
The first polynomial-time test for this property was written by Shih and Hsu in 1999, but it is still outperformed by the 1974 algorithm of Hopcroft and Tarjans in many cases.
planarity