Planar graphs and drawings in planar form practice questions | General Mathematics (Year 12, VCE Units 3 & 4, Graphs and networks, Graphs and networks)

Planar graphs and planar form

Planar form describes a particular drawing with no edge crossings away from vertices. Planarity describes the graph, which may have another crossing-free drawing

\text{planar form}\Rightarrow\text{crossing count}=0

Test the drawing A drawing is in planar form when no two edges cross away from a vertex \(\displaystyle \text{crossing count}=0\)
Separate drawing from graph A crossing in one drawing does not prove that the graph itself is non-planar \(\displaystyle \text{one crossing drawing}\not\Rightarrow G\text{ is non-planar}\)
Check alternating endpoints For straight chords on a circle, two edges cross when their four endpoints alternate around the circle \(\displaystyle A,C,B,D\Rightarrow AB\text{ crosses }CD\)
Keep the edge list Changing the positions of vertices can change crossings without changing the graph's connections \(\displaystyle E(G)=E(G')\)

Worked example

A graph has edges AB, BC, CD, DA and AC. Its vertices are placed around a circle in the order A, C, B, D. Determine whether the drawing is in planar form and whether the graph is planar

E(G)=\{AB,BC,CD,DA,AC\},\quad\text{order }A,C,B,D

\(\displaystyle A,C,B,D:\quad AB\text{ and }CD\text{ have alternating endpoints}\)The two chord endpoints alternate around the circle, so those edges cross
\(\displaystyle \text{crossing pairs}=1\ne0\)The displayed drawing is not in planar form
\(\displaystyle A,B,C,D:\quad\text{crossing pairs}=0\)The same edge list has a crossing-free drawing in a different circular order
\(\displaystyle \text{drawing not in planar form},\quad G\text{ is planar}\)The drawing fails the planar-form test, but the graph is planar

Common mistakes

Calling the graph non-planar

✕\(\displaystyle \text{one crossing drawing}\Rightarrow G\text{ is non-planar}\)✓\(\displaystyle \text{one crossing drawing}\Rightarrow\text{the drawing is not in planar form}\)

A graph can have a crossing drawing and still have another drawing with no crossings

Treating a changed layout as a new graph

✕\(\displaystyle E(G)\ne E(G')\text{ because the vertex positions changed}\)✓\(\displaystyle E(G)=E(G')\text{ when the same pairs of vertices remain joined}\)

A graph is determined by its connections, not by the positions used in a drawing

Requiring every drawing to be crossing-free

✕\(\displaystyle G\text{ planar}\Rightarrow\text{every drawing has zero crossings}\)✓\(\displaystyle G\text{ planar}\Rightarrow\text{at least one drawing has zero crossings}\)

Planarity requires the existence of a crossing-free drawing, not that every possible drawing is crossing-free

Difficulty levels

introIdentify a drawing in planar form from its edge crossings

standardDistinguish a crossing drawing from the planarity of the graph it represents

challengeSelect a crossing-free redraw that keeps the same graph connections

examSelect the complete set of drawings with no crossings away from vertices

Questions about this topic

What is the difference between planar and in planar form?+

A drawing is in planar form when its edges do not cross except at vertices. A graph is planar when at least one possible drawing of it is in planar form

How can you tell whether two straight chords cross on a circle?+

List the four endpoints in circular order. The chords cross when the endpoints of one chord separate the endpoints of the other, so the endpoints alternate

Can a drawing with a crossing represent a planar graph?+

Yes. The drawing is not in planar form, but changing the vertex order or redrawing the same connections may remove the crossing

Can I use a calculator?+

No. This topic is practised without a calculator

Which year level and chapter is this?+

Year 12, VCE Units 3 & 4, General Mathematics, chapter 13: Graphs and networks

In this chapter

Count the vertices, edges and loops of a graph Degrees, the degree sum, and even and odd vertices Graph types, subgraphs, connection models and method selection Connected graphs and bridges Identify isomorphic graphs Planar graphs and drawings in planar form Faces and Euler's formula Represent a network in a matrix Identify the network a connection matrix describes Classify a route: walk, trail, path, circuit or cycle Eulerian trails and circuits: existence and identification Hamiltonian paths and cycles Read a weighted graph The shortest path by inspection Dijkstra's algorithm for shortest distances and routes Trees and spanning trees Minimum spanning trees by Prim's and Kruskal's algorithms A full network investigation