Start off by playing the game sprouts.  (You could play this with real people!)

The picture on the right is a typical game of 3-spot sprouts taken from Martin Gardner's excellent book Mathematical Carnival, which is also available as part of an anthology of his work here.

A planar graph is a graph that can be drawn on a piece of paper without any of its edges crossing.  
All the graphs drawn when playing sprouts are planar.  

In the game of sprouts shown here, picture 1 is said to have 1 region (the outside space).  Picture 2 has 2 regions - inside the loop and the outside.  How many regions do the other pictures have?  
Count the regions in your games of sprouts; what do you notice?

Now compare the numbers of (connected) nodes, edges and regions in each picture.  
What do you notice?  

My thoughts on this investigation are here.

Click on the image to play an online version of a puzzle called Planarity.

I played this with students as nodes and skipping ropes as edges.  I played it with my year 8s and year 13s and they really enjoyed it - see the photo gallery below.  

Next lesson we are going to untangle some complete graphs, and try to untangle K5 and K3,3 which are non-planar :)

There is definitely scope for using this interactive approach for other D1 and D2 topics; something that springs to mind is using it for teaching matchings, and of course sorting algorithms. 

You could follow this up with the excellent CIMT resource on planar graphs.  

This idea was inspired by a task called 'Inseperables' (SMILE task 0492) which I also did with my year 13s, the pictures from which are below: 

Since writing this, I have purchased the excellent book People Maths Hidden Depths written by Alan Bloomfield and Bob Verdes, available as a download from the ATM.   It has some excellent ideas for similar activities; one that spring to mind here is 'knots', where the connections are made by people closing their eyes then forming links by holding hands.  When they open their eyes, the task is to unravel the knot!  I am not sure how this will work with my year 8s but it would definitely be interesting to find out!