In-Class Algorithms — Network Planarity Party

~22 min total

Aim of the assignment:

In this exercise you will learn about network layout readability criteria, especially edge crossing minimization. You will work in teams to eliminate edge crossings from several node-link network visualizations. You will do this using Planarity Party, a puzzle game we created that will let you connect with your group members and work to solve the puzzle together.

Your goal is to solve as many puzzles as possible within 15 minutes.

Background information:

A planar graph is a graph that can be drawn with no edge crossings. However, actually drawing the graph quickly but with no edge crossings can be a challenging algorithmic task.

Instructions:

1. (2 min) Setup
   • We will open Zoom breakout rooms for you. Please join the room we've assigned you. You will be working in groups of 3–4.
   • Pick a leader for your group.
   • The leader should load Planarity Party, preferably in Firefox or Chrome: https://michaschwab.github.io/VisConnect/examples/planarity/
     • (Also at https://visconnect.us/02e285a64149618cfe8429a323f9c91a/, but the bottom gets clipped off.)
       
   • Click the link icon at the bottom-right corner to copy invite link for your group to the clipboard. It looks like this:
     
     
   • Paste and send this link to your group members using the Zoom chat and wait for them to join. You will be able to see how many people are connected by the number in the bottom (there may be teaching staff connected too). You will also be able to see the mouse cursor of all members as a small colored circle.
     
2. (15 min) Start solving puzzles!
   • Each can be solved by dragging around the nodes until there are no edge crossings. The number of crossings is shown at the top, along with the number of moves you all have made.
   • When all edge crossings are removed the nodes will turn yellow and you will be able to move to the next graph. A force-directed layout of the network will also appear at the bottom of the screen for comparison.
     
   • Every new network will be harder than the last one. See how far you can make it in 15 minutes!
3. (1 min) When the time is up, return to our Zoom classroom.

Wrap up:

1. (4 min) We will discuss the exercise as a class.
   

Troubleshooting:

Unfortunately, Planarity Party is a research demo and can be a bit finicky. If you have any problems:

• Please reach out to the teaching staff.
• Try starting from scratch with a new instance of Planarity Party.
  
• Try a different browser / private browsing window.
• Have a different student create the instance.