Topic 1: Angular Resolution For the two categories in this topic, our primary concern will be angular resolution. Note, a contestant may participate in either or both of these categories. They will be judged separately.
The angular resolution of any vertex in a drawing is the smallest angle formed by its adjacent edges. When the edges are drawn as curved arcs it is measured with regards to the tangent at that vertex. A vertex has perfect angular resolution if its angular resolution is 360/d where d is the degree of the vertex.
Rather than judge the angular resolution of each drawing precisely and thus require precise positions, the judges shall use a visual comparison with emphasis foremost on angular resolution particularly the worst-case deviation of the angular resolution from the perfect angular resolution value. However, other standard aesthetic criteria still remain. In particular, if the graph is planar (Category A), it must be drawn without crossings. If there are crossings (Category B) then the angular resolution at the crossings will also be taken into consideration. In addition, the graph should use a reasonably small grid area. The vertices do not have to be on an integer grid but the vertex resolution, the ratio between the distance of the closest two vertices and the farthest two vertices, should still remain relatively low. Both graphs are highly symmetric so any exploitation of that feature will also be taken into consideration.
Unlike the challenge, the scoring is still subjective, simply with a more focused consideration. Thus, a planar graph drawn with perfect angular resolution but having crossings and using exponential grid area would likely lose to one having less than perfect angular resolution but without crossings and in a quadratic grid space.
- Category A: straight-line planar
The first (undirected) graph is planar. The drawing should be drawn in the plane, without crossings, and using only straight-line edges. Whereas many bad examples of angular resolution use sequences of nested triangles, this graph contains only two nested triangles and their removal creates a collection of outerplanar graphs.
The data can be obtained here. - Category B: curved drawings
The second (undirected) graph is not planar. The drawing, again in the plane, can have as many crossings as necessary but the angles of the crossings will also be taken into consideration. In addition, the drawings can use curved arcs. There can be as many bends as needed but during judging both the number of bends and smoothness of the bends will be taken into consideration and weighed against the gain in overall angular resolution.
The 15-node, 45-edge graph in LCF notation is 1^15 4^15 6^15.
It can be downloaded here.
File format
The graphs are given in a simple adjacency list format. The first line contains the numbers, N and M, of vertices and edges respectively. The remaining N lines each represent a single vertex and its adjacencies. The first number on the line is the vertex number (0 to N-1). The remaining numbers correspond to vertices adjacent to the vertex. Thus, the line 2 1 3 6 means that node 2 is adjacent to nodes 1, 3, and 6.
