Nonplanar

Definition

A graph is nonplanar if it cannot be drawn on a plane without edges crossing. Nonplanar graphs cannot be embedded in the plane without edge intersections.

5 Must Know Facts For Your Next Test

1. A common example of a nonplanar graph is K3,3, which represents a bipartite graph with two sets of 3 vertices.
2. Another example is K5, the complete graph on five vertices.
3. Kuratowski's theorem states that a graph is nonplanar if and only if it contains a subgraph that is a subdivision of K5 or K3,3.
4. Nonplanar graphs are important in understanding limitations and possibilities within network design and circuit layouts.
5. The concept of planarity and nonplanarity helps in categorizing different types of graphs for deeper study.

Review Questions

• What are the characteristics that make a graph nonplanar?
• Name two classic examples of nonplanar graphs.
• According to Kuratowski's theorem, what must a graph contain to be considered nonplanar?

Related terms

Planar Graph: A graph that can be drawn on a plane without any edges crossing.

Kuratowski's Theorem: A characterization defining planar graphs based on the presence of subdivisions of K5 or K3,3.

Bipartite Graph: A type of graph whose vertices can be divided into two disjoint sets such that no two vertices within the same set are adjacent.