I fear the universe may have a leak as I am becoming more aware of the age old saying that theres not enough time in the day. It's finally starting to hit me that 2 years are over and I have just over 11 months left; so its time to get rocking I guess.
I am still on the literature side of things this week (and for the past few weeks - hence the lack of updates), making my way in to Dynamic Graph Data Structures, a lengthy subject on its own. Having found what to aim for in drawings (aesthetics wise), decided on what drawing algorithm to use (FDP - Spring Embedder) and what viewing technique will be best (Animation), I am now looking at how previous authors control the flow of data and the complexity of operations associated with dynamic graphs.
Although I have a lot more to read, there is no definitive system for dealing with multilevel graphs - specifically updating the locations of vertices in coarser representations. In our static graph drawing work, we used a brute force post-order search of the approximation tree to update vertex positions, using the mean of its children - computationally expensive but also used in other work such as the Octree. This requires FDP be applied to all levels of the graph before the updates can be made - something which would be extremely inefficient if applied to dynamic graphs).
Further reading will hopefully identify a more useful method, or at least give me some ideas how to overcome this (NB: Veldhuizens work isn't clear on this subject but I've yet to read it in this context). That's all for this week folks, I will update again shortly - hopefully getting back into the swing of updating this. See you next time.
Wednesday, 26 September 2012
Friday, 7 September 2012
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!
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!
Subscribe to:
Posts (Atom)