[CC01] Graph colouring games.

The aim is to colour the vertices of a graph so that no two adjacent vertices

have the same colour. An example of such a colouring is given here.

The plan is to use as few distinct colours as possible and,

if possible use each colour the same number of times.

Although many heuristic algorithms exist for this problem, finding a best solution

(minimum number of colours) is difficult, especially when the graph is large.

The project would be to write an interactive program allowing input of (quite large) graphs to a GUI, probably as input from file as this is not primarily a graph drawing project.

The GUI should be arranged in such a way that the user can easily try out colourings the graph; hopefully with a small number of colours. The program could then score the user a

against the best selection it could find, or suggest improvements; or alternatively

the user could try to find an improvement on the solution offered by the program.

To improve on this basic problem you could make your adversary your computer

which plays alternative moves with you and tries to make you to use

more colours than you need. You would need to devise good strategies to help the computer make life difficult for the human player.

Here is a simple example. For cubical graph (given here) two colours are enough.

If you colour the bottom left vertex blue, and the computer then colours the bottom right

vertex blue you will need at least 3 colours.

[CC02] Improving a transport network.

 A typical transport network (here) can be improved by adding new

links (here).  This is an expensive process and careful planning is needed.  

Usually the number of passengers who travel between each pair of

stations is known (origin-destination data), and this is one use for Oyster cards.

In this way the effect of improvements can be measured in details.

A price is attached to travel time, and also to the number of interchanges.

This is balanced against the cost of link construction.

The project would be to take an existing network, and suggest new links, or measure the congestion

arising from removing links.  

[CC03] The friends European holiday schedule

The problem is described below.

In essence it is a constrained version of the TSP (traveling salesperson problem) and

captures many of the difficulties of scheduling large fleets of delivery vehicles

A group of friends have a week to travel round Europe.

They want to visit as many places as possible between them.

The number of places which can be visited in a week is

limited by the travel time between them and the time spent there

sightseeing, plus time lost eating sleeping etc.

The friends make individual schedules with the aim that each sees as

much as possible, and that between them the total number of places visited is as large as possible.

Added to this there may be constraints, such as everybody wants to visit as

many countries as possible. Also there may be personal themes such as visiting

famous museums; which means that opening times have to be taken into account.

Thus each friend may give each city an importance weighting.

Because they are friends, each person would like to meet up pairwise with as

many others as possible at some stage or other during their travels.

On the other hand everybody would like to see some different things so that they can talk about it.

The project would be to produce a s/w package to produce feasible schedules,

quite possibly with an interactive interface to allow changes/improvements,

and a graphical output of the schedules embedded in the map of Europe.

Needless to say the algorithmic side is also important.

[CC04] Join up the dots to make a city map.

Photographs posted on Flickr contain metadata giving geographic

coordinates, topic, time photo was taken etc. This was used in a research paper to

decide the most popular location/building in the capital cities of the world.

The coordinates of photos taken by people belonging to a

particular interest group in Flickr are shown here.

No doubt you recognise where this is from the dots, but the question is how to turn this into

something useful. For example:

to aggregate dots to produce markers for popular location (Trafalgar Square, Houses of Parliament),

To extract information for tourist use (locations of most popular landmarks),

to simplify the data to sketch in some outline roads, bridges, popular spaces and so on,

or even just find the boundaries of the land masses.

The London meta-data would be available to you as part of the project.

[CC05] Visual interface for generalized Euler tours and problems in

wiring and stitching patterns.

The Euler tour problem is how to traverse all edges of a graph exactly

once and get back to where you started, without using any edge twice.

Continuous wiring electrical circuits, or stitching designs on a flat surface

can be viewed as an adapted Euler tour problem.

An example: The  letters (TIN) can be viewed as a 7 edge, 10 vertex

graph consisting of 3 components:

 T: 4 vertices, 3 edges [there is a vertex at the T-junction]

 I: 2 vertices, 1 edge

 N: 4 vertices, 3 edges

In terms of an Euler tour, the graph needs additional edges

inserting to join up the letters to make a figure which can be

drawn without taking the pen off the paper.

If you regard the T, I, N as electrical components (neon lights for example),

the additional wiring (or glass tube) needs to go on the back of the board,

or on the front of the board avoiding the letters.

The wiring needs to be as short as

possible to minimize assembly costs, and must not cross.

The problem comes from the time of flatbed plotters to draw architectural diagrams. The plotter lifts the pens and moves (the wiring) and lowers them to draw the building details. The figures are very complex and finding the minimum amount of lifting and moving is important.

[CC06] Interactively creating tile designs.

Many tile designs, for example this one from the Alhambra in Granada, Spain 

seem to be based on a grid of ruled  lines

(horizontal, vertical, diagonal sloping right and left at 45 degrees),

with some systematic rule for line removal

The project aims to find an algorithmic method to draw such patterns and to generalize them. One major problem is to decide which line segments should go over/under which at each intersection. Another feature could be to input the pattern and to automatically dissect

it into parts which can be assembled into panels to show the components of the pattern.

These could then be analysed etc.