I'm currently looking into real-world networks which can be well approximated by interval graphs. It seems natural to suspect that networks that have constraints forcing them to be approximately physically linear could be well approximated by interval graphs.

For example, the highway system of the south island of New Zealand forms a network where geographical constraints force the network to have a natural linearity.

South island New Zealand

However, if I were to use this network, it looks like I would need to key in each of the highway intersections by hand.

In another attempt, I tried using the C. elegans neural network, thinking the physical linearity of the worm would force the network to be linear. Unfortunately, this research was thwarted by long head-to-tail neurons with large numbers of synapses (see my cogsci.SE question).

Question: Where can I access a real-world network which has an approximately linear structure (possibly due to some physical constraints)?

The network should be in a format that should be computer-readable.

  • What are your criteria for "approximately linear"? I am afraid you have the algorithm to determine that (how approximate to linear it is) and you are looking for a network that you could test your algorithm on. So your question is more about finding a network which representation is released as machine-readable and your goal is to use its linear property.
    – Vince
    May 21, 2013 at 22:06
  • I don't really have a formal criteria for approximately linear (which is why I tried to explain with examples). I suppose I do have an algorithm to test. But I'm not planning on using the network's linearity; the idea is to recover the linearity from the network structure alone. May 21, 2013 at 22:14
  • Yeah, I don't really see how applying your algorithm to almost linear network will be interesting (comparison would be) but anyway, Trans-Canada Highways also are pretty linear.
    – Vince
    May 21, 2013 at 22:19

1 Answer 1


The road system of New Zealand is obtainable in a computer readable form from OpenStreetMap. There are APIs available to query for just the objects you want, in this case the roads, see http://overpass-turbo.eu/s/cG for an example.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.