# Planarity

Do you have questions or comments about this model? Ask them here! (You'll first need to log in.)

## WHAT IS IT?

This is a puzzle game where you try to untangle a graph. (A graph is a collection of nodes connected by lines.) Try to reposition the nodes so that no two lines cross. The more nodes, the harder it gets!

## HOW IT WORKS

The game knows how to generate solvable graphs, and it also knows how to detect whether any lines intersect. The details are in the Code tab.

## HOW TO USE IT

Use the STARTING-LEVEL slider to choose the initial difficulty level. If you're a beginner, start at 1. Press SETUP to set up a new board, then press GO to play. Once the GO button is pressed, you can use your mouse to drag the nodes around.

Every level is solvable. One you find a solution, you will automatically be taken to the next level.

## THINGS TO NOTICE

The game only gives you solvable graphs. How might the game be able to guarantee this? (One answer is in the Code tab.)

Can you draw an example of an unsolvable graph on a piece of paper? How many nodes are in the smallest unsolvable graph?

On early levels, you can usually untangle the nodes without too much thought. On later levels, you'll probably need to develop some conscious strategies. What strategies do you find most effective? When your friends play, do they use the same strategies you do?

## THINGS TO TRY

See how high a level you can solve.

Try to solve each level in the fewest number of moves. (The tick counter shows you how many moves you've made.)

## EXTENDING THE MODEL

Are there any other ways of generating solvable graphs besides the SETUP-LEVEL? Does it matter what method is used? The more links you can make, the harder the level will be, but if you make too many links, the level might not be solvable at all!

Wherever two links intersect, add a small, brightly colored turtle to mark the intersection. (You'll need two breeds of turtle, one for the nodes, one for the markers. Intersecting Links Example has code for locating the intersection points.)

Make it possible to select multiple nodes and move them together.

## NETLOGO FEATURES

The nodes are turtles; the lines connecting them are links. The code does not make use of patches (other than to make a plain white background).

NetLogo does not have a primitive which detects whether two links intersect. To do the detection, the code uses the `subtract-headings`

primitive and some math.

## RELATED MODELS

Intersecting Links Example -- has sample code for finding the point where two links intersect (unlike this model, which only determines whether that point exists or not)

## CREDITS AND REFERENCES

Thanks to Josh Unterman and Seth Tisue for their work on this model and to Jim Lyons for coding advice.

Original version created by John Tantalo, from an original concept by Mary Radcliffe. Tantalo's site is here: http://www.planarity.net/.

Solvable graphs are called "planar graphs" by mathematicians. See http://en.wikipedia.org/wiki/Planar_graph.

## HOW TO CITE

If you mention this model in a publication, we ask that you include these citations for the model itself and for the NetLogo software:

- Wilensky, U. (2007). NetLogo Planarity model. http://ccl.northwestern.edu/netlogo/models/Planarity. Center for Connected Learning and Computer-Based Modeling, Northwestern Institute on Complex Systems, Northwestern University, Evanston, IL.
- Wilensky, U. (1999). NetLogo. http://ccl.northwestern.edu/netlogo/. Center for Connected Learning and Computer-Based Modeling, Northwestern Institute on Complex Systems, Northwestern University, Evanston, IL.

## COPYRIGHT AND LICENSE

Copyright 2007 Uri Wilensky.

This work is licensed under the Creative Commons Attribution-NonCommercial-ShareAlike 3.0 License. To view a copy of this license, visit http://creativecommons.org/licenses/by-nc-sa/3.0/ or send a letter to Creative Commons, 559 Nathan Abbott Way, Stanford, California 94305, USA.

Commercial licenses are also available. To inquire about commercial licenses, please contact Uri Wilensky at uri@northwestern.edu.

## Comments and Questions

globals [ level ;; determines how many nodes you have to untangle; ;; the formula is below ] to setup clear-all set-default-shape turtles "circle" ask patches [ set pcolor white ] ;; plain white background set level starting-level setup-level end to setup-level reset-ticks ;; use tick counter as a move counter clear-turtles ;; when the turtles die, the links connecting them die too ;; create nodes and position them randomly create-turtles 4 + level [ set color blue setxy random-xcor random-ycor ] ;; Now we need to make some links. We have to be careful that ;; the resulting graph has a solution. Probably there are lots ;; of ways this could be done, but this was the simplest way we ;; could think of. ;; First make a bunch of links at random. while [count links < count turtles] [ ask one-of turtles [ ask one-of other turtles [ attempt-link ] ] ] ;; Then fill in all remaining allowable links. ask turtles [ ask other turtles [ attempt-link ] ] ;; Now we have a graph which we know is solvable, ;; because the current layout is a solution. ;; Time to scramble the nodes around! while [solved?] [ scramble ] display end to attempt-link ;; link procedure ;; note that if the link already exists, nothing happens create-link-with myself [ if any-intersections? [ die ] ] end to scramble ;; The turtles agentset is always in random order, ;; so this makes a random layout. layout-circle turtles (world-width / 2 - 1) end ;; This procedure lets us find the next turtle, ;; or the turtle two over, and so on. to-report turtle-plus [n] ;; turtle procedure report turtle ((who + n) mod count turtles) end to go if mouse-down? [ ;; find the closest node let grabbed min-one-of turtles [distancexy mouse-xcor mouse-ycor] ;; loop until the mouse button is released while [mouse-down?] [ ask grabbed [ setxy mouse-xcor mouse-ycor ] display ] ;; use tick counter as a move counter tick ;; check if the level is solved if solved? [ user-message "You rock. Now try this..." set level level + 1 setup-level ] ] end to-report solved? report all? links [not any-intersections?] end to-report any-intersections? ;; link procedure report any? other links with [crossed? self myself] end to-report crossed? [link-a link-b] ;; store nodes in variables for easy access let a1 [end1] of link-a let a2 [end2] of link-a let b1 [end1] of link-b let b2 [end2] of link-b let nodes (turtle-set a1 a2 b1 b2) ;; if the links share a node, they don't cross if 4 > count nodes [ report false ] ;; but if two nodes are on top of each other, we will say ;; the links do cross (so you can't cheat that way) if 4 > length remove-duplicates [list xcor ycor] of nodes [ report true ] ;; if the ends of link-a are on opposite sides of link-b, ;; and the ends of link-b are on opposite sides of link-a, ;; then the links cross report [subtract-headings towards a2 towards b1 < 0 xor subtract-headings towards a2 towards b2 < 0] of a1 and [subtract-headings towards b2 towards a1 < 0 xor subtract-headings towards b2 towards a2 < 0] of b1 end ; Copyright 2007 Uri Wilensky. ; See Info tab for full copyright and license.

There are 10 versions of this model.

## Attached files

File | Type | Description | Last updated | |
---|---|---|---|---|

Planarity.png | preview | Preview | about 10 years ago, by Reuven M. Lerner | Download |

This model does not have any ancestors.

This model does not have any descendants.