MIT Massachusetts Institute of Technology

Connections in the Plane without Crossing

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

 

 

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”.

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 at http://faculty.kfupm.edu.sa/math/abusbeih/

This is a Wikipedia article about Planar Graphs.
http://en.wikipedia.org/wiki/Planar_graph

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.
http://pigale.sourceforge.net/

This presentation on planar graphs is sponsored by BOOST C++ Libraries, a provider of free peer-reviewed portable C++ source libraries.
http://www.boost.org/doc/libs/1_40_0/libs/graph/doc/planar_graphs.html

A discussion of the Three-Utilities Puzzle provided by the site, Cut the Knot.
http://www.cut-the-knot.org/do_you_know/3Utilities.shtml

This is the puzzle game, “Planarity”, created by John Tantalo and presented here on NetLogo, a multi-agent programmable modeling environment.
http://ccl.northwestern.edu/netlogo/models/Planarity

It will be available soon.

emurray
February 12, 2012 at 8:27 am

It will be available soon.

Where is script?

Anonymous
February 12, 2012 at 2:34 am

Where is script?

Add A Comment
By submitting this form, you accept the Mollom privacy policy.

This Lesson is in the following clusters: Graph Theory

It will be available soon.

emurray
February 12, 2012 at 8:27 am

It will be available soon.

Where is script?

Anonymous
February 12, 2012 at 2:34 am

Where is script?