Planarity condition
A graph is called planar if it can be embedded in the plane without edge intersections.
A graph is non-planar if it contains a hidden version (subdivision) of the Kuratowski subgraphs K5 or K3,3.
Example: The graph on the right is non-planar. The highlighted red subgraph is the K5 graph. Yo may rearrange the vertices and edges however you like — you will never obtain an embedding without a crossing
Euler's formula
Euler's formula states that #V - #E + #F = 2 for any planar graph G=(V,E), where V denotes its vertices, E its edges, and F the faces spanned between said graph.
You can verify the relation between these components described by the formula by examining the two exemplaric graphs presented in the right pane of this step.
LR Planarity Test
In practice, graph planarity is usually determined by using efficient algorithms.
One such method—used in the interactive section—is the LR planarity test. It performs a depth-first search (DFS) and classifies edges into left and right branches in a way that checks whether a planar embedding is possible.
We won't go into the algorithmic details here — this is simply to show which method is used later on to test planarity.
Remark: Visualization derived form: Ulrik Brandes. The Left-Right Planarity Test. Department of Computer Information Science, University of Konstanz. Fig. 1 p. 5. 2012
Planarity embedding
Now we know how to check whether a graph is planar — but how do we actually draw it without edge crossings?
Graph theory tells us that every planar graph can be drawn as a straight-line planar embedding, making it ideal for computational visualization.
For this task, we use the Chrobak-Payne algorithm, which constructs a straight-line planar drawing for any planar graph without requiring additional assumptions.
Example: Watch the right panel to see how a graph is transformed into a straight-line planar drawing
Planarity testing & embedding editor
Enter graphs in matrix- or adjacency list form, or directly manipulate the graph in the right panel.
Remark: See the info panel by pressing on the top right info icon to show a list of available key combinations.