Last Friday, my friend Jan Kratochvil spoke to the Edinburgh Mathematical Society at the University of Stirling. I decided to go and hear him.
The situation he talked about was typefied by this example. Suppose that you have a large network which you know can be drawn in the plane. (Planarity testing for graphs can be done in polynomial time.) But, for historical reasons, part of the network is already built in the plane; you are not allowed to knock it down and start again. This makes the task harder; is it possible to extend this embedding to the whole network? A related problem: if you have several graphs, sharing a common part, can you embed all the graphs so that the embeddings coincide on the common part?
As well as planar graphs, this question can be asked for various geometrically defined graphs such as interval graphs. Honza and his collaborators have uncovered a wealth of detail about these situations.
One “classical” result I didn’t know is the following. The question involves representing a graph as the intersection graph of a set of continuous functions on a closed real interval. (Think of the graphs – in the other sense – of the functions; now “intersect” has the expected meaning.) An old result of Golumbic characterises such graphs. If two functions do not intersect, then by the Intermediate Value Theorem, one lies entirely above or entirely below the other. Thus if a graph can be represented in this “fun” way, its complement is the comparability graph of a partial order. Golumbic showed that the converse is also true.
But the general questions of extendability and embedding several graphs can be asked for the “fun” class, and some very entertaining things arise.
I decided to go from St Andrews to Stirling by bus; although the bus service is not very frequent and takes two hours, it is much more convenient, since it stops very close to the University of Stirling. The outward journey was in daylight, and an interesting trip. After leaving Fife at the hamlet of Burnside (where road signs said “Burnside: Please Drive Carefully”), and passing through the curiously-named Drum, Crook of Devon, Rumbling Bridge (it did rumble, but only because the road surface was so rough), and Yetts o’Muckhart, the rest of the journey followed a nearly straight road under the shadow of the Ochil Hills (or would have been if the sun had been on the other side). These hills are a lava extrusion, but show a very dramatic scarp on the south side as a result of a fault line. Here is the last of the Ochil Hills, Dumyat, above the University of Stirling.
On Saturday, we decided to take a trip on Scotland’s newest railway, the Edinburgh to Tweedbank line. Quite the wrong time to make such a journey: the hours of daylight are short, and the trains into Edinburgh in the morning and out in the evening are crammed with shoppers (so much so that announcements at the stations warn of overcrowding on the trains).
The trip involved a slow and dreary journey through the Edinburgh sprawl, until the line turned south and entered the Moorfoot Hills, where it followed the Gala Water (lovely name, pretty stream) down to Galashiels, where it enters the Tweed. The disused railway line east of Galashiels was a footpath carrying the Southern Upland Way; walkers have been provided for, but have been sidelined by the newly restored tracks.
Nevertheless, we had time to walk along the banks of the Tweed (the station is not on the river, despite its name), climb to the pass in the Eildon Hills, and have a pub lunch, before returning. I was unable to get a decent photo of the three peaks which led the Romans to call the place Trimontium: they are best viewed from the other side. But here is a spectacular sunset that entertained us as we waited for the train home.