In-class algorithms—Planarity

Due F 2022-03-11, 11:59pm EST 2pts 16 min

Please ask any questions about this assignment in class, or later today on Canvas in the Discussion: In-class algorithms—Planarity discussion.

You are welcome to work with other students on this assignment.

Table of Contents

• Change Log
• Aim of the assignment
• Background info
• Instructions
• Submission instructions
• Grading rubric
• Troubleshooting

Change Log

• N/A

Aim of the assignment

In this exercise you will learn about network layout readability criteria, especially edge crossing minimization. You will work to eliminate edge crossings from several node-link network visualizations. You will do this using Planarity Party, a puzzle game we created.

Background info

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. The conventional heuristic layouts, and the limitations of using straight lines for edges, often introduces edge crossings in visualizations of planar graphs.

Instructions

1. We will automatically assign you to Zoom breakout rooms so you can discuss your impressions with your classmates during the activity.

2. Once you’ve joined your room, open Planarity Party in your browser.

   Note: You will get a message saying VisConnect Loading: Connection Failed. Don’t worry about that—the server we would use to make this a collaborative activity is currently down so you will be doing it solo.

3. Start solving puzzles!
   1. 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.
   2. 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. Note any differences between the automatic layout and your own.
   3. Every new network will be harder than the last one. See how far you can make it in 15 minutes!
4. When the time is up and the breakout rooms are closing, take a PNG screenshot of the last level you made it to. You will submit this for the assignment.

Submission instructions

Submit the single image or PDF to the assignment In-class algorithms—Planarity in GradeScope.

Grading rubric

This is a satisfactory grading assignment. If you followed the instructions you receive full marks and if not you receive a 0. Your submission is satisfactory if you have made meaningful progress in the game.

Troubleshooting

Unfortunately, Planarity Party 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.