Graph
Dennis Shasha
Omniheurist Course
Computer Science
Description
You are to design the largest planar graph you can
that has diameter 5 and degree 5.
To compute the diameter of a graph, consider the shortest
path from any node to any other node of the graph.
The diameter is the longest shortest path.
The degree of a graph is the maximum number of neighbors any node
in the graph can have.
Architecture and Random Spec
-
The architecture team must evaluate the solutions proposed.
The architecture team should specify the interface for solutions,
where the solutions should include the following information:
a set of node numbers and positions as well as a specification
of the edges in terms of node numbers.
-
The Random Strategy team should specify the largest tree satisfying
these constraints.
All other teams should be able to do better.