[R--gR] Graphs and Metro's

[Castelo, Robert]

hi,

since i live in Barcelona and use its metro network i'll answer this :)

the area of research for this is called "graph drawing" and a good link
to get acquainted with it is

http://www.cs.brown.edu/people/rt/gd.html

a friend of mine who works in automated cartography has recommended me
this link and has told me that the first two links, a book and a
pdf-tutorial, are quite good as a starting point.

he also pointed out to me that it's very different to draw with straight
segments than with curves as the number of edge crossings can be very
different. minimizing crossings is NP-hard however if the number of
crossings is small the following reference (and references therein) can
be useful:

Computing Crossing Numbers in Quadratic Time  .
  Journal of Computer and System Sciences, 68(2):285-302, 2004.
  Conference version appeared in Proceedings of the 32nd ACM Symposium
  on Theory of Computing (STOC'01), pp.231-236, 2001.
  http://www.informatik.hu-berlin.de/~grohe/pub/cross.ps


i hope this helps,
robert.

On Wed, 2004-10-20 at 01:26, Søren Højsgaard wrote:
> Dear all,
> Yesterday, I looked at a map of the metro in Barcelona, and I came to think about whether we could learn something from such maps when producing graphs for graphical models. (With many variables, a graphical model tends to look "messy").
> 
> Edges in metro-maps are often not straight lines - they tend to be composed of line segments forming 0, 45 and 90 degrees angles relative to some coordinate system - and that really makes the maps easier to look at. Have anyone looked at this idea? (It is not a particularly original idea so I guess the answer is "yes"!) 
> 
> It should be reasonably straight forward to formulate a heuristic for creating such edges: 1) The length of an edge should be small under the constraints that, 2) there is a "low price" on horisontal and vertical line segments and 3) a "high price" on 45-degree, 135 degree and so on lines. The actual shape of an edge under such requirements is not unique, for example the lines 
> o--       o-
>    \        \        .......
>     --o       ---o
> will have the same "price" - so some heuristic is needed to choose one from another. 
> 
> Comments, ideas, references??
> 
> Best regards
> Søren
> 
> ============================================================================================= 
> Søren Højsgaard,  MSc, PhD (Statistics),        Phone: +45 8999 1703 
> Head of Biometry Research Unit,                 Fax:     +45 8999 1300 
> Danish Institute of Agricultural Sciences       E-mail: sorenh at agrsci.dk 
> Research Centre Foulum, DK-8830 Tjele, Denmark  Homepage : http://www.jbs.agrsci.dk/~sorenh/ 
> 
> .... Time flies like an arrow, fruit flies like a banana ....
> 
> 	[[alternative HTML version deleted]]
> 
> _______________________________________________
> R-sig-gR mailing list
> R-sig-gR at stat.math.ethz.ch
> https://stat.ethz.ch/mailman/listinfo/r-sig-gr