In graph theory, the planarity testing problem is the algorithmic problem of testing whether a given graph is a planar graph (that is, whether it can be drawn in the plane without edge intersections). This is a well-studied problem in computer science for which many practical algorithms have emerged, many taking advantage of novel data structures. Most of these methods operate in O(n) time (linear time), where n is the number of edges (or vertices) in the graph, which is asymptotically optimal. Rather than just being a single Boolean value, the output of a planarity testing algorithm may be a planar graph embedding, if the graph is planar, or an obstacle to planarity such as a Kuratowski subgraph if it is not.
Read more about Planarity Testing: Planarity Criteria
Famous quotes containing the word testing:
“Bourbon’s the only drink. You can take all that champagne stuff and pour it down the English Channel. Well, why wait 80 years before you can drink the stuff? Great vineyards, huge barrels aging forever, poor little old monks running around testing it, just so some woman in Tulsa, Oklahoma can say it tickles her nose.”
—John Michael Hayes (b.1919)