Dynamic Literature: Mental Map

Over the past week I've been working on writing up much of the literature for my Thesis draft as part of my RDA2 form (MPhil to PhD transfer). Now that the deadline has passed I can give my blog an update.

NB: Blogspot needs a feature which allows users to put all blogs into a single editable and printable file. Just a thought for any dev's which may be reading.

Aesthetics of a dynamic graph are very hard to define, and even measure due to constant changes in the structure. Therefore, the concept of a Mental Map has been created, relating to the readers familiarity with the layout (and the graph). Much of the literature is infatuated with the Mental Map, and it is widely believed that any changes to it will affect the readers understanding of the graph, and it is of the upmost importance to avoid any big changes which could confuse the user and remove their mental map. In essence, it has become a measured aesthetic of dynamic graphs across many publications.

Unfortunately, measuring the Mental Map is still difficult, and many authors suggest different ways of doing so - measuring movement over time, edge crossings over time and others, most being computationally expensive and not ideal for my work.

Although my work will inevitable cater to the Mental Map concept, the works of Purchase (whom has previously worked with measuring and identifying the most important aesthetics of static graphs) has suggested (with strong proof) that attempting to attain good Mental Map stability is not as useful as first thought. There are comparisons against different algorithms, different visualisation styles with different parameters being measured, and all results point to a weak improvement to readabilitywhen achieveing this mental map (usually by restricting movement).

Unfortunately, there is almost no literature for Mental Maps of huge graphs, only smaller graphs with less than a 1000 vertices (most support fewer than 100). Admittedly there may be research I have not yet found, but it is unlikely I will find any as Purchase's publications foil the concept, and dynamic graph drawing for huge graphs is an almost untouched area (par a few individuals - Veldhuizen and Frishman, possibly Hu but I have yet to check).

So what to do? Identifying the Mental Map is perhaps the most difficult part. With larger graphs, I treat drawings as rigid objects which can be rotated and translated, suggesting my Mental Map looks at the global structure. Some would suggest the Mental Map only applies to smaller localised structures where users would like to view connectivity between vertices. For uhge graphs, I offer two approaches - for global structure, identify the mental map of a coarser interpretation of a graph, and for local structure, use only sections/partitions of the graph which can be identified through the MGF/edge contraction tree.

I have yet to finish reading more of the literature - much of my reading has focused on smaller graph techniques and so I need to investigate techniques for larger graphs (if any can be found). Hopefully I can find an alternate approach to compare against (or even better, find my suggestions aready implemented). I will update if I find anything, have a good weekend!