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:
“Traditional scientific method has always been at the very best 20-20 hindsight. Its good for seeing where youve been. Its good for testing the truth of what you think you know, but it cant tell you where you ought to go.”
—Robert M. Pirsig (b. 1928)