Question 1 (5 marks)

1.   Explain the hv-tree drawing method with O(n) drawing area (n is the number of vertices in the tree) and constant aspect ratio.

2.   Construct a drawing of the tree below using the method and analyse the width W and height H of the drawing. Show your working process and explain how you compute your answer.

Question 2 (5 marks)

Given the coordinates of the vertices (V1 to V6), compute the (x,y)-coordinates of the vertices (V7 to V10) using Tutte’s Barycenter algorithm.

Show your working process and explain how you compute your answer.

Question 3 (5 marks)

Compute a layering of the following graph using the Coffman-Graham algorithm. Show your working process and explain how you compute your answer:

1.    Compute a labelling for each vertex.

2.   Compute a layering with width 3 and draw the resulting layering.

Question 4 (5 marks)

For the graph below with a fixed top layer (vertices V1 to V15) and a free bottom layer (vertices U1 to U8):

1.   Compute the vertex ordering of the free layer using the Barycenter algorithm.  Show your working process and explain how you compute your answer.

2.   Compute the vertex ordering of the free layer using the Median algorithm.   Show your working process and explain how you compute your answer.

3.   Compare the quality and runtime of the two methods.

Question 5 (3 marks)

Select good visualisation methods for the following data and explain the methods.

List of scores of students at a school:

Frank: {Math: 80, English: 80, Chemistry: 85, Physics: 85, Economics: 80}    Greg: {Math: 50, English: 55, Chemistry: 60, Physics: 60, Economics: 60}      Hannah: {Math: 75, English: 80, Chemistry: 80, Physics: 80, Economics: 75} Ian: {Math: 55, English: 50, Chemistry: 55, Physics: 55, Economics: 60}         Julie: {Math: 50, English: 55, Chemistry: 55, Physics: 50, Economics: 60}      Kenneth: {Math: 70, English: 75, Chemistry: 80, Physics: 70, Economics: 80}

Question 6 (4 marks)

1.   Select two different methods to visualise the following data and explain the methods, including the pros and cons.

V: entities and E: relationships

January: V1 = {A, B, C, D}, E1 = {(A,B), (A,C), (A,D)}

February: V2 = {A, B, C, D, E, F}, E2 = {(A,B), (A,C), (A,D),(B,C),(C,E),(C,F)} March: V3 = {A, B, C, D, F}, E3 = {(A,B), (A,C),(B,C),(B,D),(C,D),(C,F)}

April: V4 = {A, B, C, D, F, G}, E3 = {(A,B), (A,C),(B,C),(B,D),(B,G),(C,D),(C,F),(F,G)} May: V4 = {A, B, C, D, G}, E3 = {(A,B), (A,C),(A,G),(B,C),(B,D),(B,G),(C,D)}

2.   Write down the criteria for evaluating those methods.