Alternating Planar Graphs
Alternating Planar Graphs
There are over 40 problems and solutions presented here relating to alternating planar graphs (where roads connect towns). You can create and redesign these graphs as you wish.
These graphs have the property that adjacent vertices never have the same degree (i.e. the number of roads connecting to two connected towns is different for each town), and adjacent faces never have the same number of vertices (i.e. different areas have different numbers of towns on their perimeter).
The problems and solutions given are the best known of this type.
Also, this Demonstration lets you easily create your own road-town graphs (maybe you can come up with new or better solutions). Explore!