Seispalabras: Mind the map

La historia del mapa del metro de Londres es bastante conocida entre los que trabajan o alguna vez hemos trabajado en Teoría de Grafos, o más concretamente, en Inmerión de Grafos (Graph Drawing). ¿Por qué? Pues básicamente, porque nos permite explicar de forma sencilla y casi anecdótica la importancia de la representación de un grafo.

De forma coloquial y sencilla, un grafo no es más que un conjunto de elementos, a los que llamaremos vértices, que se unen entre ellos, por parejas, no necesariamente todos, definiendo lo que llamamos aristas del grafo. Para muestra, un grafo:

Los vértices serán los elementos del conjunto {1, 2, 3, 4} y las aristas {(1,2),(1,3), (1,4), (2,3), (2,4), (3,4)} (vamos, lo que son cuatro puntos, todos unidos con todos).

Ése es el grafo. De hecho, es un grafo conocido como K₄ y una posible representación (dibujo) del mismo sería ésta (Figura 1)

Figura 1

O sea, que para que nos entendamos, una representación es un dibujo del grafo. Pero ésa no es la única posible representación de K₄ también podríamos dar otra, como se puede ver en la Figura 2

Figura 2

Y si te preguntas para qué buscar otra representación distinta, pues, por ejemplo, porque la de la Figura 2 no tiene cruces entre sus aristas, es una representación plana como decimos los de Grafos. Y las representaciones planas son mejores cuando se diseñan, por ejemplo, circuitos.

Ahora, a ver, si tenemos K₅ (5 vértices, todos unidos con todos) ¿es posible dar otra representación distinta sin cruces entre sus aristas? O como decimos en Teoría de Grafos, ¿es posible dar una inmersión plana de K₅? Os dejo unos minutos para que lo intentéis.

Una inmersión de K₅

Venga, no os agobiéis, no es posible. De hecho es uno de los teoremas más famosos de la Teoría de Grafos, el Teorema de Kuratowski

Hasta aquí espero haberos convencidos de la importancia del dibujo de un grafo. Para un mismo conjunto de vértices y una misma lista de conexiones entre ellos, puede haber trazados con o sin cruces entre las líneas. Pero vamos a ver otro ejemplo antes de hablar del mapa del metro de Londres.

En la siguiente ilustración, tenemos 4 grafos.

Si nos fijamos bien, en el grafo I₁, se ve fácilmente que este grafo es Hamiltoniano, hay un camino que pasa por todos los vértices y vuelve al de origen, sin repetir vértices. El grafo I₂es fácil ver que es un grafo regular, es decir, de todos los vértices sale el mismo número de aristas. En cuanto al grafo I_3, se puede intuir que es un grafo plano, que se puede dibujar sin cruces entre aristas. Y, por último, si miramos el grafo I4, se ve claramente que es bipartito, es decir, se pueden colorear los vértices usando sólo 2 colores, de forma que nunca se conecten vértices del mismo color.

Pues bien, los 4 son el mismo grafo, son 4 dibujos distintos del mismo grafo.

En definitiva, depende del dibujo que hagamos de nuestro grafo, de la representación que elijamos, podemos destacar, y por lo tanto aprovechar, una característica u otra del grafo. Por lo tanto, parece que merece la pena detenerse un poco a la hora de dibujar un grafo,

Nos vamos a Londres. ¡Venga!

Londres, Febrero de 2001

Los primeros mapas del metro de Londres eran geográficos, básicamente, consistían en dibujar sobre un plano de la ciudad los recorridos de las distintas líneas.

Mapa del metro de Londres en 1908

Fue Harry Beck, ingeniero electrónico empleado en el metro de Londres, el primero que se percató de que al usuario no le interesaba conocer el recorrido del metro bajo tierra, sino simplemente, conocer la posición relativa de las líneas y estaciones para realizar los trasbordos que necesitase.

Harry Beck

Se le ocurrió entonces, en 1931, que en realidad, más que un diseño geográfico, lo que resultaría útil sería un diseño topológico, con menos curvas y direcciones en las líneas, y, de broma, hizo su primer diseño basado en los utilizados en circuitos eléctricos. Aún un poco reticentes, lanzaron la idea de Beck entre los usuarios y fue aceptada con entusiasmo por los usuarios del metro.

Primer mapa de Beck de 1933

Y hasta hoy, esa idea topológica del mapa de Beck, es la más utilizada en el mundo para este tipo de planos, incluso hasta en nuestro metro de Sevilla, aunque aquí, sinceramente, aún podríamos permitirnos el geográfico.

Metro de Sevilla

Éste es otro ejemplo más de la importancia del dibujo de un grafo, puesto que podemos entender las estaciones como vértices y las líneas como aristas. De hecho, Beck, a lo largo de su trayectoria, introdujo diversos cambios a su diseño original en pos de conseguir mayor claridad en el plano.

En 1936, entre otros cambios, eliminó curvas y sólo permitió ángulos de 45º y 90º

Mapa de 1936

En 1940, le pidieron, entre otros detalles, que incorporase ángulos de 60º también, idea que se desechó por enturbiar la claridad del plano.

Mapa en 1941

Se puede consultar aquí la evolución de los mapas de del metro de Londres y observar qué tipo de modificaciones iban apareciendo siempre para mejorar la usabilidad de los mismos.

Plano de 2011

Pero si leemos esa evolución, nos damos cuenta de que no sólo se trata de dar un trazado topológicamente correcto y sencillo para el usuario, sino que se topan con otro problema: las etiquetas. Deben tener suficiente tamaño para que se puedan leer, pero lo justo para que no se "amontonen" en el mapa y para que el tamaño del plano del metro no sea del tamaño de una catálogo de Worten.

Y ese problema, el problema del etiquetado de mapas, map labeling problem, no acerca un poco a algo que me gusta bastante, la Geometría Computacional.

Lo que me llamó la atención la primera que oí hablar de este tipo de problemas, como muchos de los abordados por la Geometría Computacional, es la sencillez de su planteamiento y la increíble dificultad de dar una buena solución.

¿De qué se trata? Pues de que tenemos que poner etiquetas en un mapa a: puntos, líneas (curvas o poligonales) y regiones. Hay que hacerlo de forma legible, sin ambigüedades y sin solapamiento de las etiquetas.

Etiquetas para puntos

Hay que cumplir además ciertas reglas, más o menos, aceptadas por todos.

En el etiquetado de puntos, por ejemplo: se prefiere que la etiqueta esté a la derecha (no a la izquierda), que esté arriba (no por debajo)...

En el etiquetado de líneas poligonales o curvas, las etiquetas deben conservar una distancia mínima, no debe intersectar a la línea etiquetada, con poca curvatura, pocos puntos de inflexión, lo más horizontal posible...

En el etiquetado de regiones, no debe cruzar la frontera de la región, debe quedar claro cuál es la región completa etiquetada, que no entre en conflicto con etiquetas de puntos o líneas...etc.

Pues bien, dada la complejidad y el hecho de que los problemas de etiquetado de mapas no se reducen sólo al ámbito de transportes públicos, éstos han dado lugar a muchísmos trabajos de investigación y a una larga lista de algoritmos de aproximación para tratar de resolverlos.

Desgraciadamente, no existen buenos algoritmos que resuelvan el problema computacional, es por ello que aún hoy en día, el etiquetado de los mapas se hacen a mano. Un experto puede poner entre 20 y 30 etiquetas en un mapa por hora.

Así que en contra de lo que algunos piensan, no es tan fácil colocar etiquetas.... lo dejamos por aquí. Eso sí, colorearlos, sabemos que sólo con cuatro colores.

Si te interesa el tema, te recomiendo un paseo por esta página de Alex Wolff o echarle, por ejemplo un vistazo a este otro trabajo.