The Scheming Gardener

1. Remove the useless strings
   1. add any node with only one string coming from it to the "useless" queue
   2. as you pop a useless node and remove its string, if it creates a new useless node, add that to the queue
   • This is effectively a topological sort
2. Convert the physical graph to a planar graph...this is the hardest part of the problem
   1. Find edges that are on the perimeter
      1. Take some point on the perimeter, say minimum X point and take the lowest angle above the X axis
      2. For every subsequent point, take the edge that makes the most gentle left hand turn
   2. Start finding regions
      1. starting at the same X point, and taking the same first edge
      2. now at the subsequent points, take the tightest left hand turn
      3. when you get back to where you started, you have a plot.
      4. remove any edges that are in the outside edges list
      5. add the remaining edges to the outside edges list
      6. mark those same remaining edges as "boundaries" of this plot
   3. Find more regions
   • when you find subsequent regions, you must check if the edges of that region are "boundaries" of some other region, in which case you create an edge in your new graph between the two plots
   • any region that contained any edge which was in the ORIGINAL boundary should be marked as such
   1. Repeat until all plots have been processed
3. add all the plots which contained an edge in the original boundary to a list
4. BFS to find the plot furthest away