Connections in the Plane without Crossing

Connections in the Plane without Crossing

Topic Cluster

Graph Theory


Mohammad Zuheir Abu-Sbeih
Associate Professor of Mathematics
Department of Mathematics and Statistics
King Fahd University of Petroleum and Minerals (KFUPM)
Dharan, Saudi Arabia
*This video was sponsored by Saudi Aramco and produced by Sultan Bin Abdel Aziz Science & Technology Center

Lesson Feedback


This lesson presents interesting and challenging problems in Graph Theory, supporting the skills that students learned at school and stimulating their critical thinking. The topics will include: basic properties of graphs; complete graphs and complete bipartite graphs; planar and plane graphs; and Euler’s formula - the four-color theorem. These topics have many applications in electrical circuits, computer programs, and the scheduling of aircraft and trains. Here we shall discuss two applications - the three-utilities/three-houses problem and the avoiding crossing on the motherboard.  No prerequisites are required for this lesson, and it can be considered self-contained. It will last about 26 minutes, and the remaining time will be devoted to different in-class activities, such as connecting the three houses to the three stations, coloring a plane map with a minimum number of colors, discovering Euler’s formula (which relates the number of vertices, number of edges and the number of faces in a plane graph), and representing the motherboard of a calculator without crossing.  Supplies needed for these activities include papers, colors, wires, threads, ropes with different colors, cardboard, balloons, and a car tube. Find Teacher’s Guide and downloadable graphs in section “For Teachers”.

Instructor Biography

Dr. Abu-Sbeih is Professor of Mathematics at King Fahd University of Petroleum and Minerals. Currently he is the Undergraduate Coordinator in the Mathematics and Statistics Department. His interest is in the area of combinatorics and graph theory, especially in enumeration and embedding problems. He also has an interest in math education. He enjoys spreading the culture of mathematics in the society to benefit all. Read more about him here

Additional Online Resources

Wikipedia: Planar graph
This is a Wikipedia article about Planar Graphs.

Sourceforge: C++ algorithm
This site, Public Implementation of a Graph Algorithm Library and Editor, provides a graph editor and a C++ algorithm library essentially concerned with planar graphs.

Boost: Planar Graphs
This presentation on planar graphs is sponsored by BOOST C++ Libraries, a provider of free peer-reviewed portable C++ source libraries.

Three-Utilities Puzzle: 3 Utilities Puzzle
A discussion of the Three-Utilities Puzzle provided by the site, Cut the Knot.

NetLogo: Planarity
This is the puzzle game, “Planarity”, created by John Tantalo and presented here on NetLogo, a multi-agent programmable modeling environment.