JabRef References output

Author	Title	Year	Journal/Proceedings	Reftype	DOI/URL
Huang, W.	Using eye tracking to investigate graph layout effects [Abstract] [BibTeX]	2007	APVis '07: Proceedings of the 2007 Asia-Pacific Symposium on Information Visualisation, pp. 97-100	inproceedings	DOI URL
Abstract: Graphs are typically visualized as node-link diagrams. Although there is a fair amount of research focusing on crossing minimization to improve readability, little attention has been paid on how to handle crossings when they are an essential part of the final visualizations. This requires us to understand how people read graphs and how crossings affect reading performance. As an initial step to this end, a preliminary eye tracking experiment was conducted. The specific purpose of this experiment was to test the effects of crossing angles and geometric-path tendency on eye movements and performance. Sixteen subjects performed both path search and node locating tasks with six drawings. The results showed that small angles can slow down and trigger extra eye movements, causing delays for path search tasks, whereas crossings have little impact on node locating tasks. Geometric-path tendency indicates that a path between two nodes can become harder to follow when many branches of the path go toward the target node. The insights obtained are discussed with a view to further confirmation in future work.
BibTeX: @inproceedings{Huang07Usingeyetracking, author = {Weidong Huang}, title = {Using eye tracking to investigate graph layout effects}, booktitle = {APVis '07: Proceedings of the 2007 Asia-Pacific Symposium on Information Visualisation}, year = {2007}, pages = {97--100}, url = {http://ieeexplore.ieee.org/xpls/abs_all.jsp?arnumber=4126225}, doi = {http://dx.doi.org/10.1109/APVIS.2007.329282} }
Huang, W. & Eades, P.	How People Read Graphs [Abstract] [BibTeX]	2005	APVis '05: Proceedings of the 2005 Asia-Pacific Symposium on Information Visualisation, pp. 51-58	inproceedings	URL
Abstract: The graph layout problem has long been a major concern for effectiveness of conveying information. To propose user-centred aesthetic criteria for a "good" layout, it is important to have knowledge on how people read graphs; how a particular graph layout characteristic can affect people's reading performance. On the other hand, despite the increasingly wide use of graphs in everyday life, yet we know surprisingly little about how people actually read graphs. The present eye tracking study in this paper is an attempt to perform an initial investigation into this issue and provide data that can help build the basic understanding of how people read graphs.
BibTeX: @inproceedings{Huang05HowPeopleRead, author = {Weidong Huang and Peter Eades}, title = {How People Read Graphs}, booktitle = {APVis '05: Proceedings of the 2005 Asia-Pacific Symposium on Information Visualisation}, year = {2005}, pages = {51--58}, url = {http://portal.acm.org/citation.cfm?id=1082324} }
Huang, W., Hong, S. & Eades, P.	Effects of Crossing Angles [Abstract] [BibTeX]	2008	PacificVIS '08: Proceedings of the 2008 IEEE Pacific Visualization Symposium, pp. 41-46	inproceedings	DOI URL
Abstract: In visualizing graphs as node-link diagrams, it is commonly accepted and employed as a general rule that the number of link crossings should be minimized whenever possible. However, little attention has been paid to how to handle the remaining crossings in the visualization. The study presented in this paper examines the effects of crossing angles on performance of path tracing tasks. It was found that the effect varied with the size of crossing angles. In particular, task response time decreased as the crossing angle increased. However, the rate of the decrease tended to level off when the angle was close to 90 degrees. One of the implications of this study in graph visualization is that just minimizing the crossing number is not sufficient to reduce the negative impact to the minimum. The angles of remaining crossings should be maximized as well.
BibTeX: @inproceedings{Huang08EffectsofCrossing, author = {Weidong Huang and Seok-Hee Hong and Peter Eades}, title = {Effects of Crossing Angles}, booktitle = {PacificVIS '08: Proceedings of the 2008 IEEE Pacific Visualization Symposium}, year = {2008}, pages = {41--46}, url = {http://ieeexplore.ieee.org/search/wrapper.jsp?arnumber=4475457}, doi = {http://dx.doi.org/10.1109/PACIFICVIS.2008.4475457} }
Huang, W., Hong, S. & Eades, P.	Predicting graph reading performance: a cognitive approach [Abstract] [BibTeX]	2006	APVis '06: Proceedings of the 2006 Asia-Pacific Symposium on Information Visualisation, pp. 207-216	inproceedings	DOI URL
Abstract: Performance and preference measures are commonly used in the assessment of visualization techniques. This is important and useful in understanding differences in effectiveness between different treatments. However, these measures do not answer how and why the differences are caused. And sometimes, performance measures alone may not be sensitive enough to detect differences. In this paper, we introduce a cognitive approach for visualization effectiveness and efficiency assessment. A model of user performance, mental effort and cognitive load (memory demand) is proposed and further mental effort and visualization efficiency measures are incorporated into our analysis. It is argued that 1) combining cognitive measures with traditional methods provides us new insights and practical guidance in visualization assessment. 2) analyzing human cognitive process not only helps to understand how viewers interact with visualizations, but also helps to predict user performance in initial stage. 3) keeping cognitive load induced by a visualization low allows more memory resources to be available for high level complex cognitive activities. A case study conducted supports our arguments.
BibTeX: @inproceedings{Huang06Predictinggraphreading, author = {Weidong Huang and Seok-Hee Hong and Peter Eades}, title = {Predicting graph reading performance: a cognitive approach}, booktitle = {APVis '06: Proceedings of the 2006 Asia-Pacific Symposium on Information Visualisation}, year = {2006}, pages = {207--216}, url = {http://portal.acm.org/citation.cfm?doid=1151903.1151933}, doi = {http://doi.acm.org/10.1145/1151903.1151933} }
Zheng, L., Song, L. & Eades, P.	Crossing Minimization Problems of Drawing Bipartite Graphs in Two Clusters [Abstract] [BibTeX]	2005	APVis '05: Proceedings of the 2005 Asia-Pacific Symposium on Information Visualisation, pp. 33-37	inproceedings	URL
Abstract: The crossing minimization problem is a classic and very important problem in graph drawing (Pach, Tòth 1997); the results directly affect the effectiveness of the layout, especially for very large scale graphs. But in many cases crossings cannot be avoided. In this paper we present two models for bipartite graph drawing, aiming to reduce crossings that cannot be avoided in the traditional bilayer drawings. We characterize crossing minimization problems in these models, and prove that they are N P-complete.
BibTeX: @inproceedings{Zheng05CrossingMinimizationProblems, author = {Lanbo Zheng and Le Song and Peter Eades}, title = {Crossing Minimization Problems of Drawing Bipartite Graphs in Two Clusters}, booktitle = {APVis '05: Proceedings of the 2005 Asia-Pacific Symposium on Information Visualisation}, year = {2005}, pages = {33--37}, url = {http://portal.acm.org/citation.cfm?id=1082321} }
Jia, Y., Hoberock, J., Garland, M. & Hart, J.C.	On the Visualization of Social and other Scale-Free Networks [Abstract] [BibTeX]	2008	IEEE Transactions on Visualization and Computer Graphics Vol. 14(6), pp. 1333-1339	article	DOI URL
Abstract: This paper proposes novel methods for visualizing specifically the large power-law graphs that arise in sociology and the sciences. In such cases a large portion of edges can be shown to be less important and removed while preserving component connectedness and other features (e.g. cliques) to more clearly reveal the network's underlying connection pathways. This simplification approach deterministically filters (instead of clustering) the graph to retain important node and edge semantics, and works both automatically and interactively. The improved graph filtering and layout is combined with a novel computer graphics anisotropic shading of the dense crisscrossing array of edges to yield a full social network and scale-free graph visualization system. Both quantitative analysis and visual results demonstrate the effectiveness of this approach.
BibTeX: @article{Jia08VisualizationofSocial, author = {Yuntao Jia and Jared Hoberock and Michael Garland and John C. Hart}, title = {On the Visualization of Social and other Scale-Free Networks}, journal = {IEEE Transactions on Visualization and Computer Graphics}, year = {2008}, volume = {14}, number = {6}, pages = {1333--1339}, url = {http://ieeexplore.ieee.org/xpls/abs_all.jsp?arnumber=4658141}, doi = {http://dx.doi.org/10.1109/TVCG.2008.151} }
Li, W., Eades, P. & Nikolov, N.S.	Using Spring Algorithms to Remove Node Overlapping [Abstract] [BibTeX]	2005	APVis '05: Proceedings of the 2005 Asia-Pacific Symposium on Information Visualisation, pp. 131-140	inproceedings	URL
Abstract: Cluttered drawings of graphs cannot effectively convey the information of graphs. Two issues might cause node overlapping when one draws a picture of a graph. The first issue occurs when applying a layout algorithm for an abstract graph to a practical application in which nodes are labeled. The second is the changing of a node’s size in a dynamic drawing system. This paper presents two algorithms, DNLS and ODNLS, for removing the two kinds of overlapping. The algorithms are based on the well-known spring embedder model. The outputs of the algorithms provide the features of spring algorithms. Experiments are carried out to compare DNLS and ODNLS to the Force Scan(FS) algorithm and its variants. The results demonstrate the advantages of DNLS and ODNLS in terms of some aesthetic criteria.
BibTeX: @inproceedings{Li05UsingSpringAlgorithms, author = {Wanchun Li and Peter Eades and Nikola S. Nikolov}, title = {Using Spring Algorithms to Remove Node Overlapping}, booktitle = {APVis '05: Proceedings of the 2005 Asia-Pacific Symposium on Information Visualisation}, year = {2005}, pages = {131--140}, url = {http://portal.acm.org/citation.cfm?id=1082315.1082334} }
Ware, C., Purchase, H.C., Colpoys, L. & McGill, M.	Cognitive measurements of graph aesthetics [Abstract] [BibTeX]	2002	Information Visualization Vol. 1(2), pp. 103-110	article	DOI URL
Abstract: A large class of diagrams can be informally characterized as node-link diagrams. Typically nodes represent entities, and links represent relationships between them. The discipline of graph drawing is concerned with methods for drawing abstract versions of such diagrams. At the foundation of the discipline are a set of graph aesthetics (rules for graph layout) that, it is assumed, will produce graphs that can be clearly understood. Examples of aesthetics include minimizing edge crossings and minimizing the sum of the lengths of the edges. However, with a few notable exceptions, these aesthetics are taken as axiomatic, and have not been empirically tested. We argue that human pattern perception can tell us much that is relevant to the study of graph aesthetics including providing a more detailed understanding of aesthetics and suggesting new ones. In particular, we find the importance of good continuity (ie keeping multi-edge paths as straight as possible) has been neglected. We introduce a methodology for evaluating the cognitive cost of graph aesthetics and we apply it to the task of finding the shortest paths in spring layout graphs. The results suggest that after the length of the path the two most important factors are continuity and edge crossings, and we provide cognitive cost estimates for these parameters. Another important factor is the number of branches emanating from nodes on the path.
BibTeX: @article{Ware02Cognitivemeasurementsof, author = {Colin Ware and Helen C. Purchase and Linda Colpoys and Matthew McGill}, title = {Cognitive measurements of graph aesthetics}, journal = {Information Visualization}, year = {2002}, volume = {1}, number = {2}, pages = {103--110}, url = {http://www.palgrave-journals.com/ivs/journal/v1/n2/abs/9500013a.html}, doi = {http://dx.doi.org/10.1057/palgrave.ivs.9500013} }
Eades, P. & Sugiyama, K.	How to draw a directed graph [Abstract] [BibTeX]	1990	Journal of Information Processing Vol. 13(4), pp. 424-437	article	URL
Abstract: Several recent tools for visualizing software and information engineering problems have used directed graphs as a basic model. This has generated considerable interest in algorithms for drawing directed graphs that are easy to understand and remember. This paper discusses a practical and general method for making drawings according to specific aestbetic criteria. Some recent algorithms for drawing directed graphs are instances of this general method. The aesthetic criteria can be viewed as goals of optimization problems. Each step of the general method aims to meet one of the criteria by solving these optimization problems. We survey the current state of knowledge of each of the optimization problems and indicate unsolved problems.
BibTeX: @article{Eades90Howtodraw, author = {Peter Eades and Kozo Sugiyama}, title = {How to draw a directed graph}, journal = {Journal of Information Processing}, publisher = {Information Processing Society of Japan}, year = {1990}, volume = {13}, number = {4}, pages = {424--437}, url = {http://ci.nii.ac.jp/naid/110002673538/} }
Battista, G.D., Eades, P., Tamassia, R. & Tollis, I.G.	Algorithms for Drawing Graphs: an Annotated Bibliography [Abstract] [BibTeX]	1994	Computational Geometry Vol. 4, pp. 235-282	article	DOI URL
Abstract: Several data presentation problems involve drawing graphs so that they are easy to read and understand. Examples include circuit schematics and software engineering diagrams. In this paper we present a bibliographic survey on algorithms whose goal is to produce aesthetically pleasing drawings of graphs. Research on this topic is spread over the broad spectrum of Computer Science. This bibliography constitutes an attempt to encompass both theoretical and application oriented papers from disparate areas.
BibTeX: @article{Battista94AlgorithmsDrawingGraphs_, author = {Giuseppe Di Battista and Peter Eades and Roberto Tamassia and Ioannis G. Tollis}, title = {Algorithms for Drawing Graphs: an Annotated Bibliography}, journal = {Computational Geometry}, publisher = {Elsevier Science Publishers B. V.}, year = {1994}, volume = {4}, pages = {235--282}, url = {http://www.sciencedirect.com/science?_ob=ArticleURL&_udi=B6TYS-45DB276-7&_user=10&_rdoc=1&_fmt=&_orig=search&_sort=d&view=c&_acct=C000050221&_version=1&_urlVersion=0&_userid=10&md5=418b42d766d486291837f6ff07c674da}, doi = {http://dx.doi.org/10.1016/0925-7721(94)00014-X} }
Herman, I., Society, I.C., Melançon, G. & Marshall, M.S.	Graph visualization and navigation in information visualization: A survey [Abstract] [BibTeX]	2000	IEEE Transactions on Visualization and Computer Graphics Vol. 6, pp. 24-43	article	URL
Abstract: Abstract—This is a survey on graph visualization and navigation techniques, as used in information visualization. Graphs appear in numerous applications such as web browsing, state–transition diagrams, and data structures. The ability to visualize and to navigate in these potentially large, abstract graphs is often a crucial part of an application. Information visualization has specific requirements, which means that this survey approaches the results of traditional graph drawing from a different perspective. Index Terms—Information visualization, graph visualization, graph drawing, navigation, focus+context, fish–eye, clustering.
BibTeX: @article{Herman00Graphvisualizationand, author = {Ivan Herman and Ieee Cs Society and Guy Melançon and M. Scott Marshall}, title = {Graph visualization and navigation in information visualization: A survey}, journal = {IEEE Transactions on Visualization and Computer Graphics}, year = {2000}, volume = {6}, pages = {24--43}, url = {http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.28.8892} }
Mutzel, P.	An alternative method to crossing minimization on hierarchical graphs [Abstract] [BibTeX]	1997	Vol. 1190/1997SIAM Journal on Optimization, pp. 318-333	inproceedings	DOI URL
Abstract: A common method for drawing directed graphs is, as a first step, to partition the vertices into a set of k levels and then, as a second step, to permute the vertices within the levels such that the number of crossings is minimized. We suggest an alternative method for the second step, namely, removing the minimal number of edges such that the resulting graph is k-level planar. For the final diagram the removed edges are reinserted into a k-level planar drawing. Hence, instead of considering the k-level crossing minimization problem, we suggest solving the k-level planarization problem. In this paper we address the case k=2. First, we give a motivation for our approach. Then, we address the problem of extracting a 2-level planar subgraph of maximum weight in a given 2-level graph. This problem is NP-hard. Based on a characterization of 2-level planar graphs, we give an integer linear programming formulation for the 2-level planarization problem. Moreover, we define and investigate the polytope $$2LPS$$ (G) associated with the set of all 2-level planar subgraphs of a given 2-level graph G. We will see that this polytope has full dimension and that the inequalities occuring in the integer linear description are facet-defining for $$2LPS$$ (G). The inequalities in the integer linear programming formulation can be separated in polynomial time, hence they can be used efficiently in a cutting plane method for solving practical instances of the 2-level planarization problem. Furthermore, we derive new inequalities that substantially improve the quality of the obtained solution. We report on first computational results.
BibTeX: @inproceedings{Mutzel97alternativemethodto, author = {Petra Mutzel}, title = {An alternative method to crossing minimization on hierarchical graphs}, booktitle = {SIAM Journal on Optimization}, publisher = {Springer}, year = {1997}, volume = {1190/1997}, pages = {318--333}, url = {http://www.springerlink.com/content/x101t1061n777222}, doi = {http://dx.doi.org/10.1007/3-540-62495-3_57} }
Huang, W., Hong, S. & Eades, P.	Layout effects on sociogram perception [Abstract] [BibTeX]	2006	Vol. 3843/2006GD '05: Proceedings of 13th International Symposium on Graph Drawing, pp. 262-273	inproceedings	DOI URL
Abstract: This paper describes a within-subjects experiment in which we compare the relative effectiveness of five sociogram drawing conventions in communicating underlying network substance, based on user task performance and usability preference, in order to examine effects of different spatial layout formats on human sociogram perception. We also explore the impact of edge crossings, a widely accepted readability aesthetic. Subjective data were gathered based on the methodology of Purchase et al. [14]. Objective data were collected through an online system. We found that both edge crossings and conventions pose significant effects on user preference and task performance of finding groups, but either has little impact on the perception of actor status. On the other hand, the node positioning and angular resolution might be more important in perceiving actor status. In visualizing social networks, it is important to note that the techniques that are highly preferred by users do not necessarily lead to best task performance.
BibTeX: @inproceedings{Huang05Layouteffectssociogram, author = {Weidong Huang and Seok-Hee Hong and Peter Eades}, title = {Layout effects on sociogram perception}, booktitle = {GD '05: Proceedings of 13th International Symposium on Graph Drawing}, publisher = {Springer}, year = {2006}, volume = {3843/2006}, pages = {262--273}, url = {http://www.springerlink.com/content/7x22r2344wv86881}, doi = {http://dx.doi.org/10.1007/11618058_24} }
Huang, W.	An Eye Tracking Study into the Effects of Graph Layout [Abstract] [BibTeX]	2006		techreport	URL
Abstract: Graphs are typically visualized as node-link diagrams. Although there is a fair amount of research focusing on crossing minimization to improve readability, little attention has been paid on how to handle crossings when they are an essential part of the final visualizations. This requires us to understand how people read graphs and how crossings affect reading performance. As an initial step to this end, a preliminary eye tracking experiment was conducted. The specific purpose of this experiment was to test the effects of crossing angles and geometric-path tendency on eye movements and performance. Sixteen subjects performed both path search and node locating tasks with six drawings. The results showed that small angles can slow down and trigger extra eye movements, causing delays for path search tasks, whereas crossings have little impact on node locating tasks. Geometric-path tendency indicates that a path between two nodes can become harder to follow when many branches of the path go toward the target node. The insights obtained are discussed with a view to further confirmation in future work.
BibTeX: @techreport{Huang06EyeTrackingStudy, author = {Weidong Huang}, title = {An Eye Tracking Study into the Effects of Graph Layout}, year = {2006}, url = {http://www.cs.usyd.edu.au/~whua5569/} }
Huang, W., Hong, S. & Eades, P.	Layout Effects: Comparison of Sociogram Drawing Conventions [Abstract] [BibTeX]	2005	(575)	techreport	URL
Abstract: This report describes a within-subjects experiment in which we compare the relative effectiveness of five sociogram drawing conventions in communicating underlying network substance, based on user task performance and usability preference, in order to examine effects of different spatial layout formats on human sociogram perception. We also explore the impact of edge crossings, a widely accepted readability aesthetic. Subjective data were gathered based on the methodology of Purchase et al. [2002]. Objective data were collected through an online system. We found that both edge crossings and drawing conventions pose significant affects on user preference and task performance of finding groups, but either has little impact on the perception of actor status. On the other hand, the node positioning and angular resolution might be more important in perceiving actor status. In visualising social networks, it is important to note that the techniques that are highly preferred by users do not necessarily lead to best task performance.
BibTeX: @techreport{Huang05LayoutEffects_Comparison, author = {Weidong Huang and Seok-Hee Hong and Peter Eades}, title = {Layout Effects: Comparison of Sociogram Drawing Conventions}, year = {2005}, number = {575}, url = {http://www.cs.usyd.edu.au/~whua5569/} }
Huang, W.	Beyond Time and Error: A Cognitive Approach to the Evaluation of Graph Visualizations [Abstract] [BibTeX]	2007	School: University of Sydney	phdthesis	URL
Abstract: In evaluating graph visualizations, time and error measures are widely used to understand the effectiveness of a particular visualization method. However, such measures do not tell us how and why the visualization is effective or ineffective. In addition, knowledge gained from these measures is useful only for a specific visualization method or task. This knowl- edge is unlikely to be generally useful when the method or task is varied. There is a lack of general theory and guidelines for graph visualization. New evaluation methodologies are urgently needed so that we can gain more fundamental knowledge and deeper insight from empirical work. In this thesis, we evaluate graph visualizations from a cognitive perspective, measuring more than just time and error. Three evaluations are presented with each using a differ- ent method to measure a cognitive aspect of human task performance. The methods used include purpose-designed questionnaires and interviews, eye tracking and cognitive load measures. The main purpose of the evaluations is to demonstrate the usefulness of the cog- nitive approach, in helping us to gain deeper insight beyond what time and error measures offer. That is, how and why, in addition to what. The thesis makes some important contributions. The contributions fall into two areas: evaluation methodology and domain knowledge. Our methodological contribution is that we apply the cognitive approach in evaluating graph visualizations. A large set of empirical results and observations are produced as a result of the approach. Contributions in improv- ing our domain knowledge are diverse. These findings include, but are not limited to, the relative effectiveness of sociogram drawing conventions, the effects of link crossings on sociogram perception, human sociogram perception conventions, sociogram drawing rules, the underlying mechanism of how link crossings affect performance, the effects of crossing angles and geodesic-path tendency, the visualization principles for information processing in working memory, the construct of cognitive load, the model of performance, mental effort and cognitive load, and the new measures of cognitive load and visualization efficiency.
BibTeX: @phdthesis{Huang07BeyondTimeanda, author = {Weidong Huang}, title = {Beyond Time and Error: A Cognitive Approach to the Evaluation of Graph Visualizations}, school = {University of Sydney}, year = {2007}, url = {http://www.cs.usyd.edu.au/~whua5569/} }
Battista, G.D., Eades, P., Tamassia, R. & Tollis, I.G.	Graph Drawing: Algorithms for the Visualization of Graphs [BibTeX]	1998		book	URL
BibTeX: @book{Battista98GraphDrawing_Algorithms, author = {Giuseppe Di Battista and Peter Eades and Roberto Tamassia and Ioannis G. Tollis}, title = {Graph Drawing: Algorithms for the Visualization of Graphs}, publisher = {Prentice Hall}, year = {1998}, url = {http://www.cs.brown.edu/~rt/gdbook.html} }
Körner, C. & Albert, D.	Speed of comprehension of visualized ordered sets. [Abstract] [BibTeX]	2002	Journal of Experimental Psychology: Applied Vol. 8(1), pp. 57-71	article	DOI URL
Abstract: The authors investigated the effects of visual properties of hierarchical graphs on speed of comprehension: planarity (crossing of lines), slopes (orientation of lines), and levels (adjustment of dots). In each of 4 experiments, 30 participants responded to interpretive questions that required comparisons among the elements of the graph. Knowledge provided to participants differed across Experiments 1a, 1b, and 1c; question demands varied in Experiment 2. Analysis of response latencies showed that crossing of lines is the most influential variable independent of orientation, dot adjustment, and question demands. Speed of comprehension decreased with increasing question demands. When question demands were high, orientation of lines also had an effect on speed of comprehension. Preliminary conclusions for the presentation of hierarchical graphs are drawn.
BibTeX: @article{Koerner02Speedofcomprehension, author = {Christof Körner and Dietrich Albert}, title = {Speed of comprehension of visualized ordered sets.}, journal = {Journal of Experimental Psychology: Applied}, year = {2002}, volume = {8}, number = {1}, pages = {57--71}, url = {http://psycnet.apa.org/?fa=main.doiLanding&doi=10.1037/1076-898X.8.1.57}, doi = {http://dx.doi.org/10.1037/1076-898X.8.1.57} }
Huang, W., Eades, P. & Hong, S.	Beyond time and error: a cognitive approach to the evaluation of graph drawings [Abstract] [BibTeX]	2008	BELIV '08: Proceedings of the 2008 conference on BEyond time and errors: novel evaLuation methods for Information Visualization, pp. 1-8School: University of Sydney, Australia	inproceedings	DOI URL
Abstract: Time and error are commonly used to measure the effectiveness of graph drawings. However, such measures are limited in providing more fundamental knowledge that is useful for general visualization design. We therefore apply a cognitive approach in evaluations. This approach evaluates graph drawings from a cognitive perspective, measuring more than just time and error. Three user studies are conducted to demonstrate the usefulness of this approach.
BibTeX: @inproceedings{Huang08Beyondtimeand, author = {Weidong Huang and Peter Eades and Seok-Hee Hong}, title = {Beyond time and error: a cognitive approach to the evaluation of graph drawings}, booktitle = {BELIV '08: Proceedings of the 2008 conference on BEyond time and errors: novel evaLuation methods for Information Visualization}, publisher = {ACM}, school = {University of Sydney, Australia}, year = {2008}, pages = {1--8}, url = {http://portal.acm.org/citation.cfm?doid=1377966.1377970}, doi = {http://dx.doi.org/10.1145/1377966.1377970} }
Archambault, D., Auber, D. & Munzner, T.	Smashing Peacocks Further: Drawing Quasi-Trees from Biconnected Components [Abstract] [BibTeX]	2006	IEEE Transactions on Visualization and Computer Graphics Vol. 12(5), pp. 813-820	article	DOI URL
Abstract: We extend the popular force-directed approach to network (or graph) layout to allow separation constraints, which enforce a minimum horizontal or vertical separation between selected pairs of nodes. This simple class of linear constraints is expressive enough to satisfy a wide variety of application-specific layout requirements, including: layout of directed graphs to better show flow; layout with non-overlapping node labels; and layout of graphs with grouped nodes (called clusters). In the stress majorization force-directed layout process, separation constraints can be treated as a quadratic programming problem. We give an incremental algorithm based on gradient projection for efficiently solving this problem. The algorithm is considerably faster than using generic constraint optimization techniques and is comparable in speed to unconstrained stress majorization. We demonstrate the utility of our technique with sample data from a number of practical applications including gene-activation networks, terrorist networks and visualization of high-dimensional data
BibTeX: @article{Archambault06SmashingPeacocksFurther_, author = {Daniel Archambault and David Auber and Tamara Munzner}, title = {Smashing Peacocks Further: Drawing Quasi-Trees from Biconnected Components}, journal = {IEEE Transactions on Visualization and Computer Graphics}, publisher = {IEEE Educational Activities Department}, year = {2006}, volume = {12}, number = {5}, pages = {813--820}, url = {http://ieeexplore.ieee.org/search/wrapper.jsp?arnumber=4015434}, doi = {http://dx.doi.org/10.1109/TVCG.2006.177} }
Purchase, H.C.	Metrics for Graph Drawing Aesthetics [Abstract] [BibTeX]	2002	Journal of Visual Languages & Computing Vol. 13, pp. 501-516	article	DOI URL
Abstract: Graph layout algorithms typically conform to one or more aesthetic criteria (e.g. minimizing the number of bends, maximizing orthogonality). Determining the extent to which a graph drawing conforms to an aesthetic criterion tends to be done informally, and varies between different algorithms. This paper presents formal metrics for measuring the aesthetic presence in a graph drawing for seven common aesthetic criteria, applicable to any graph drawing of any size. The metrics are useful for determining the aesthetic quality of a given graph drawing, or for defining a cost function for genetic algorithms or simulated annealing programs. The metrics are continuous, so that aesthetic quality is not stated as a binary conformance decision (i.e. the drawing either conforms to the aesthetic or not), but can be stated as the extent of aesthetic conformance using a number between 0 and 1. The paper presents the seven metric formulae. The application of these metrics is demonstrated through the aesthetic analysis of example graph drawings produced by common layout algorithms.
BibTeX: @article{Purchase02MetricsGraphDrawing, author = {Helen C. Purchase}, title = {Metrics for Graph Drawing Aesthetics}, journal = {Journal of Visual Languages & Computing}, year = {2002}, volume = {13}, pages = {501--516}, url = {http://www.ingentaconnect.com/content/ap/vl/2002/00000013/00000005/art00232}, doi = {http://dx.doi.org/10.1006/jvlc.2002.0232} }
Purchase, H.C., Carrington, D.A. & Allder, J.	Experimenting with Aesthetics-Based Graph Layout [Abstract] [BibTeX]	2000	Vol. 1889/2000Diagrams '00: Proceedings of the 1st International Conference on Theory and Application of Diagrams, pp. 498-501	inproceedings	DOI URL
Abstract: Many automatic graph layout algorithms have been implemented to display relational data in a graphical (usually node-arc) manner. The success of these algorithms is typically measured by their computational efficiency and the extent to which they conform to aesthetic criteria (for example, minimising the number of crossings, maximising symmetry). Little research has been performed on the usability aspects of such algorithms: do they produce graph drawings that make the embodied information easy to use and understand? Is the computational effort expended on conforming to the assumed aesthetic criteria justifiable with espect to better usability? This paper reports on usability studies to investigate automatic graph layout algorithms with respect to human use.
BibTeX: @inproceedings{Purchase00ExperimentingwithAesthetics-Based, author = {Helen C. Purchase and David A. Carrington and Jo-Anne Allder}, title = {Experimenting with Aesthetics-Based Graph Layout}, booktitle = {Diagrams '00: Proceedings of the 1st International Conference on Theory and Application of Diagrams}, publisher = {Springer}, year = {2000}, volume = {1889/2000}, pages = {498--501}, url = {http://www.springerlink.com/content/ftvxj0urthul1tty}, doi = {http://dx.doi.org/10.1007/3-540-44590-0_46} }
van Ham, F. & Rogowitz, B.E.	Perceptual Organization in User-Generated Graph Layouts [Abstract] [BibTeX]	2008	IEEE Transactions on Visualization and Computer Graphics Vol. 14(6), pp. 1333-1339	article	DOI URL
Abstract: Many graph layout algorithms optimize visual characteristics to achieve useful representations. Implicitly, their goal is to create visual representations that are more intuitive to human observers. In this paper, we asked users to explicitly manipulate nodes in a network diagram to create layouts that they felt best captured the relationships in the data. This allowed us to measure organizational behavior directly, allowing us to evaluate the perceptual importance of particular visual features, such as edge crossings and edge-lengths uniformity. We also manipulated the interior structure of the node relationships by designing data sets that contained clusters, that is, sets of nodes that are strongly interconnected. By varying the degree to which these clusters were 'masked'; by extraneous edges we were able to measure observers'; sensitivity to the existence of clusters and how they revealed them in the network diagram. Based on these measurements we found that observers are able to recover cluster structure, that the distance between clusters is inversely related to the strength of the clustering, and that users exhibit the tendency to use edges to visually delineate perceptual groups. These results demonstrate the role of perceptual organization in representing graph data and provide concrete recommendations for graph layout algorithms.
BibTeX: @article{Ham08PerceptualOrganizationin, author = {Frank van Ham and Bernice E. Rogowitz}, title = {Perceptual Organization in User-Generated Graph Layouts}, journal = {IEEE Transactions on Visualization and Computer Graphics}, year = {2008}, volume = {14}, number = {6}, pages = {1333--1339}, url = {http://ieeexplore.ieee.org/xpls/abs_all.jsp?arnumber=4658147}, doi = {http://dx.doi.org/10.1109/TVCG.2008.155} }
Dwyer, T., Marriott, K., Shreiber, F., Stuckey, P.J., Woodward, M. & Wybrow, M.	Exploration of Networks using Overview+Detail with Constraint-based Cooperative Layout [Abstract] [BibTeX]	2008	IEEE Transactions on Visualization and Computer Graphics Vol. 14(6), pp. 1293-1300	article	DOI URL
Abstract: A standard approach to large network visualization is to provide an overview of the network and a detailed view of a small component of the graph centred around a focal node. The user explores the network by changing the focal node in the detailed view or by changing the level of detail of a node or cluster. For scalability, fast force-based layout algorithms are used for the overview and the detailed view. However, using the same layout algorithm in both views is problematic since layout for the detailed view has different requirements to that in the overview. Here we present a model in which constrained graph layout algorithms are used for layout in the detailed view. This means the detailed view has high-quality layout including sophisticated edge routing and is customisable by the user who can add placement constraints on the layout. Scalability is still ensured since the slower layout techniques are only applied to the small subgraph shown in the detailed view. The main technical innovations are techniques to ensure that the overview and detailed view remain synchronized, and modifying constrained graph layout algorithms to support smooth, stable layout. The key innovation supporting stability are new dynamic graph layout algorithms that preserve the topology or structure of the network when the user changes the focus node or the level of detail by in situ semantic zooming. We have built a prototype tool and demonstrate its use in two application domains, UML class diagrams and biological networks.
BibTeX: @article{Dwyer08ExplorationofNetworks, author = {Tim Dwyer and Kim Marriott and Falk Shreiber and Peter J. Stuckey and Michael Woodward and Michael Wybrow}, title = {Exploration of Networks using Overview+Detail with Constraint-based Cooperative Layout}, journal = {IEEE Transactions on Visualization and Computer Graphics}, year = {2008}, volume = {14}, number = {6}, pages = {1293--1300}, url = {http://ieeexplore.ieee.org/xpls/abs_all.jsp?arnumber=4658142}, doi = {http://dx.doi.org/10.1109/TVCG.2008.130} }
Luboschik, M., Schumann, H. & Cords, H.	Particle-Based Labeling: Fast Point-Feature Labeling without Obscuring Other Visual Features [Abstract] [BibTeX]	2008	IEEE Transactions on Visualization and Computer Graphics Vol. 14(6), pp. 1237-1244	article	DOI URL
Abstract: n many information visualization techniques, labels are an essential part to communicate the visualized data. To preserve the expressiveness of the visual representation, a placed label should neither occlude other labels nor visual representatives (e.g., icons, lines) that communicate crucial information. Optimal, non-overlapping labeling is an NP-hard problem. Thus, only a few approaches achieve a fast non-overlapping labeling in highly interactive scenarios like information visualization. These approaches generally target the point-feature label placement (PFLP) problem, solving only label-label conflicts. This paper presents a new, fast, solid and flexible 2D labeling approach for the PFLP problem that additionally respects other visual elements and the visual extent of labeled features. The results (number of placed labels, processing time) of our particle-based method compare favorably to those of existing techniques. Although the esthetic quality of non-real-time approaches may not be achieved with our method, it complies with practical demands and thus supports the interactive exploration of information spaces. In contrast to the known adjacent techniques, the flexibility of our technique enables labeling of dense point clouds by the use of nonoccluding distant labels. Our approach is independent of the underlying visualization technique, which enables us to demonstrate the application of our labeling method within different information visualization scenarios.
BibTeX: @article{Luboschik08Particle-BasedLabeling_Fast, author = {Martin Luboschik and Heidrun Schumann and Hilko Cords}, title = {Particle-Based Labeling: Fast Point-Feature Labeling without Obscuring Other Visual Features}, journal = {IEEE Transactions on Visualization and Computer Graphics}, year = {2008}, volume = {14}, number = {6}, pages = {1237--1244}, url = {http://ieeexplore.ieee.org/xpls/abs_all.jsp?arnumber=4658135}, doi = {http://dx.doi.org/10.1109/TVCG.2008.152} }
Purchase, H.C.	Which Aesthetic has the Greatest Effect on Human Understanding? [Abstract] [BibTeX]	1997	Vol. 1353/1997GD '97: Proceedings of the 5th International Symposium on Graph Drawing, pp. 248-261	inproceedings	DOI URL
Abstract: In the creation of graph drawing algorithms and systems, designers claim that by producing layouts that optimise certain aesthetic qualities, the graphs are easier to understand. Such aesthetics include maximise symmetry, minimise edge crosses and minimise bends. A previous study aimed to validate these claims with respect to three aesthetics, using paper-based experiments [11]. The study reported here is superior in many ways: five aesthetics are considered, attempts are made to place a priority order on the relative importance of the aesthetics, the experiments are run on-line, and the ease of understanding the drawings is measured in time, as well as in the number of errors. In addition, greater consideration is given to the possible effect of confounding factors in the graph drawings. The results indicate that reducing the number of edge crosses is by far the most important aesthetic, while minimising the number of bends and maximising symmetry have a lesser effect. The effects of maximising the minimum angle between edges leaving a node and of fixing edges and nodes to an orthogonal grid are not statistically significant. This work is important since it helps to demonstrate to algorithm and system designers the aesthetic qualities most important for aiding human understanding, the most appropriate compromises to make when there is a conflict in aesthetics, and consequently, how to build more effective systems.
BibTeX: @inproceedings{Purchase97WhichAesthetichas, author = {Helen C. Purchase}, title = {Which Aesthetic has the Greatest Effect on Human Understanding?}, booktitle = {GD '97: Proceedings of the 5th International Symposium on Graph Drawing}, publisher = {Springer}, year = {1997}, volume = {1353/1997}, pages = {248--261}, url = {http://www.springerlink.com/content/39m598l76588240l}, doi = {http://dx.doi.org/10.1007/3-540-63938-1_67} }
McGrath, C., Blythe, J. & Krackhardt, D.	Seeing Groups in Graph Layout [Abstract] [BibTeX]	1996	Connections Vol. 19(2), pp. 22-29	article	URL
Abstract: Intro: Social networkers frequently make use of drawings to communicate information and ideas about networks. However, the impact of the layout of a network on the conclusions that a viewer is likely to draw has so far received very little scrutiny. In this paper, we extend work begun in (Blythe et al, 1995) and (McGrath et al, 1996) to understand how the layout of graphs depicting social network data influences the inferences viewers draw about social networks. Our previous work focused on the perception of prominence or bridging of a particular node. Here we focus on perceptions of clustering among nodes.
BibTeX: @article{McGrath96SeeingGroupsin, author = {Cathleen McGrath and Jim Blythe and David Krackhardt}, title = {Seeing Groups in Graph Layout}, journal = {Connections}, year = {1996}, volume = {19}, number = {2}, pages = {22--29}, url = {http://www.andrew.cmu.edu/user/cm3t/groups.html} }
Purchase, H.C., McGill, M., Colpoys, L. & Carrington, D.	Graph drawing aesthetics and the comprehension of UML class diagrams: an empirical study [Abstract] [BibTeX]	2001	APVis '01: Proceedings of the 2001 Asia-Pacific symposium on Information visualisation, pp. 129-137	inproceedings	URL
Abstract: Many existing automatic graph layout algorithms are unrelated to any particular semantic domain. Designers of such algorithms tend to conform to layout aesthetics, and claim that by doing so, the resultant diagram is easy to understand. Few algorithms are designed for a specific domain, and there is no guarantee that the aesthetics used for generic layout algorithms will be useful for the visualisation of domain-specific diagrams (for example, visual programs, or entity-relationship diagrams). This paper describes a study which aimed to identify the most important aesthetics for the automatic layout of UML class diagrams from a human comprehension point of view. The results suggest that for specific domains, the actual semantics of the given graph may need to be considered before an appropriate graph drawing can be produced.
BibTeX: @inproceedings{Purchase01Graphdrawingaesthetics, author = {Helen C. Purchase and Matthew McGill and Linda Colpoys and David Carrington}, title = {Graph drawing aesthetics and the comprehension of UML class diagrams: an empirical study}, booktitle = {APVis '01: Proceedings of the 2001 Asia-Pacific symposium on Information visualisation}, publisher = {Australian Computer Society, Inc.}, year = {2001}, pages = {129--137}, url = {http://portal.acm.org/citation.cfm?id=564056} }
Purchase, H.C., Hoggan, E. & Görg, C.	How Important is the "Mental Map"? -- an Empirical Investigation of a Dynamic Graph Layout Algorithm [Abstract] [BibTeX]	2007	Vol. 4372/2007GD '06: Proceedings of 14th International Symposium on Graph Drawing, pp. 184-195	inproceedings	DOI URL
Abstract: While some research has been performed on the human understanding of static graph layout algorithms, dynamic graph layout algorithms have only recently been developed sufficiently to enable similar investigations. This paper presents the first empirical analysis of a dynamic graph layout algorithm, focusing on the assumption that maintaining the "mental map" between time-slices assists with the comprehension of the evolving graph. The results confirm this assumption with respect to some categories of tasks.
BibTeX: @inproceedings{Purchase07HowImportantis, author = {Helen C. Purchase and Eve Hoggan and Carsten Görg}, title = {How Important is the "Mental Map"? -- an Empirical Investigation of a Dynamic Graph Layout Algorithm}, booktitle = {GD '06: Proceedings of 14th International Symposium on Graph Drawing}, publisher = {Springer}, year = {2007}, volume = {4372/2007}, pages = {184--195}, url = {http://www.springerlink.com/content/t771t31jw72165q4}, doi = {http://dx.doi.org/10.1007/978-3-540-70904-6_19} }
Dwyer, T., Marriott, K. & Wybrow, M.	Integrating Edge Routing into Force-Directed Layout [Abstract] [BibTeX]	2007	Vol. 4372/2007GD '06: Proceedings of 14th International Symposium on Graph Drawing, pp. 8-19	inproceedings	DOI URL
Abstract: The typical use of force-directed layout is to create organic-looking, straight-edge drawings of large graphs while combinatorial techniques are generally preferred for high-quality layout of small to medium sized graphs. In this paper we integrate edge-routing techniques into a force-directed layout method based on constrained stress majorisation. Our basic procedure takes an initial layout for the graph, including poly-line paths for the edges, and improves this layout by moving the nodes to reduce stress and moving edge bend points to straighten the edges and reduce their overall length. Separation constraints between nodes and edge bend points are used to ensure that nodes do not overlap edges or other nodes and that no additional edge crossings are introduced.
BibTeX: @inproceedings{Dwyer07IntegratingEdgeRouting, author = {Tim Dwyer and Kim Marriott and Michael Wybrow}, title = {Integrating Edge Routing into Force-Directed Layout}, booktitle = {GD '06: Proceedings of 14th International Symposium on Graph Drawing}, publisher = {Springer}, year = {2007}, volume = {4372/2007}, pages = {8--19}, url = {http://www.springerlink.com/content/77437331n25p6w04}, doi = {http://dx.doi.org/10.1007/978-3-540-70904-6_3} }
Kohavi, R., Henne, R.M. & Sommerfield, D.	Practical guide to controlled experiments on the web: listen to your customers not to the hippo [Abstract] [BibTeX]	2007	KDD '07: Proceedings of the 13th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pp. 959-967	inproceedings	DOI URL
Abstract: The web provides an unprecedented opportunity to evaluate ideas quickly using controlled experiments, also called randomized experiments (single factor or factorial designs), A/B tests (and their generalizations), split tests, Control/Treatment tests, and parallel flights. Controlled experiments embody the best scientific design for establishing a causal relationship between changes and their influence on user-observable behavior. We provide a practical guide to conducting online experiments, where end-users can help guide the development of features. Our experience indicates that significant learning and return-on-investment (ROI) are seen when development teams listen to their customers, not to the Highest Paid Person's Opinion (HiPPO). We provide several examples of controlled experiments with surprising results. We review the important ingredients of running controlled experiments, and discuss their limitations (both technical and organizational). We focus on several areas that are critical to experimentation, including statistical power, sample size, and techniques for variance reduction. We describe common architectures for experimentation systems and analyze their advantages and disadvantages. We evaluate randomization and hashing techniques, which we show are not as simple in practice as is often assumed. Controlled experiments typically generate large amounts of data, which can be analyzed using data mining techniques to gain deeper understanding of the factors influencing the outcome of interest, leading to new hypotheses and creating a virtuous cycle of improvements. Organizations that embrace controlled experiments with clear evaluation criteria can evolve their systems with automated optimizations and real-time analyses. Based on our extensive practical experience with multiple systems and organizations, we share key lessons that will help practitioners in running trustworthy controlled experiments.
BibTeX: @inproceedings{Kohavi07Practicalguideto, author = {Ron Kohavi and Randal M. Henne and Dan Sommerfield}, title = {Practical guide to controlled experiments on the web: listen to your customers not to the hippo}, booktitle = {KDD '07: Proceedings of the 13th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining}, publisher = {ACM}, year = {2007}, pages = {959--967}, url = {http://portal.acm.org/citation.cfm?doid=1281192.1281295}, doi = {http://dx.doi.org/10.1145/1281192.1281295} }
Gansner, E.R., Koren, Y. & North, S.	Graph Drawing by Stress Majorization [Abstract] [BibTeX]	2005	Vol. 3383/2005GD '04: Proceedings of 12th International Symposium on Graph Drawing, pp. 239-250	inproceedings	DOI URL
Abstract: One of the most popular graph drawing methods is based on achieving graph-theoretic target distances. This method was used by Kamada and Kawai [15], who formulated it as an energy optimization problem. Their energy is known in the multidimensional scaling (MDS) community as the stress function. In this work, we show how to draw graphs by stress majorization, adapting a technique known in the MDS community for more than two decades. It appears that majorization has advantages over the technique of Kamada and Kawai in running time and stability. We also found the majorization-based optimization being essential to a few extensions to the basic energy model. These extensions can improve layout quality and computation speed in practice.
BibTeX: @inproceedings{Gansner05GraphDrawingby, author = {Emden R. Gansner and Yehuda Koren and Stephen North}, title = {Graph Drawing by Stress Majorization}, booktitle = {GD '04: Proceedings of 12th International Symposium on Graph Drawing}, publisher = {Springer}, year = {2005}, volume = {3383/2005}, pages = {239--250}, url = {http://www.springerlink.com/content/jrn52j7cx8grcy6v}, doi = {http://dx.doi.org/10.1007/b105810} }
Noack, A.	An Energy Model for Visual Graph Clustering [Abstract] [BibTeX]	2004	Vol. 2912/2004GD '03: Proceedings of 11th International Symposium on Graph Drawing, pp. 425-436	inproceedings	DOI URL
Abstract: We introduce an energy model whose minimum energy drawings reveal the clusters of the drawn graph. Here a cluster is a set of nodes with many internal edges and few edges to nodes outside the set. The drawings of the best-known force and energy models do not clearly show clusters for graphs whose diameter is small relative to the number of nodes. We formally characterize the minimum energy drawings of our energy model. This characterization shows in what sense the drawings separate clusters, and how the distance of separated clusters to the other nodes can be interpreted.
BibTeX: @inproceedings{Noack04EnergyModelVisual, author = {Andreas Noack}, title = {An Energy Model for Visual Graph Clustering}, booktitle = {GD '03: Proceedings of 11th International Symposium on Graph Drawing}, publisher = {Springer}, year = {2004}, volume = {2912/2004}, pages = {425--436}, url = {http://www.springerlink.com/content/bnkwtl1vanl222ln}, doi = {http://dx.doi.org/10.1007/b94919} }
Reips, U.	Standards for Internet-based experimenting [Abstract] [BibTeX]	2002	Experimental Psychology Vol. 49(4), pp. 243-256	article	URL
Abstract: This article summarizes expertise gleaned from the first years of Internet-based experimental research and presents recommendations on: (1) ideal circumstances for conducting a study on the Internet; (2) what precautions have to be undertaken in Web experimental design; (3) which techniques have proven useful in Web experimenting; (4) which frequent errors and misconceptions need to be avoided; and (5) what should be reported. Procedures and solutions for typical challenges in Web experimenting are discussed. Topics covered include randomization, recruitment of samples, generalizability, dropout, experimental control, identity checks, multiple submissions, configuration errors, control of motivational confounding, and pre-testing. Several techniques are explained, including "warm-up," "high hurdle," password methods, "multiple site entry," randomization, and the use of incentives. The article concludes by proposing 16 standards for Internet-based experimenting.
BibTeX: @article{Reips02StandardsInternet-basedexperimenting, author = {Reips, U.D.}, title = {Standards for Internet-based experimenting}, journal = {Experimental Psychology}, year = {2002}, volume = {49}, number = {4}, pages = {243--256}, url = {http://psycnet.apa.org/journals/zea/49/4/243/} }
Perer, A. & Shneiderman, B.	Balancing Systematic and Flexible Exploration of Social Networks [Abstract] [BibTeX]	2006	IEEE Transactions on Visualization and Computer Graphics Vol. 12(5), pp. 693-700	article	DOI URL
Abstract: Social network analysis (SNA) has emerged as a powerful method for understanding the importance of relationships in networks. However, interactive exploration of networks is currently challenging because: (1) it is difficult to find patterns and comprehend the structure of networks with many nodes and links, and (2) current systems are often a medley of statistical methods and overwhelming visual output which leaves many analysts uncertain about how to explore in an orderly manner. This results in exploration that is largely opportunistic. Our contributions are techniques to help structural analysts understand social networks more effectively. We present SocialAction, a system that uses attribute ranking and coordinated views to help users systematically examine numerous SNA measures. Users can (1) flexibly iterate through visualizations of measures to gain an overview, filter nodes, and find outliers, (2) aggregate networks using link structure, find cohesive subgroups, and focus on communities of interest, and (3) untangle networks by viewing different link types separately, or find patterns across different link types using a matrix overview. For each operation, a stable node layout is maintained in the network visualization so users can make comparisons. SocialAction offers analysts a strategy beyond opportunism, as it provides systematic, yet flexible, techniques for exploring social networks
BibTeX: @article{Perer06BalancingSystematicand, author = {Adam Perer and Ben Shneiderman}, title = {Balancing Systematic and Flexible Exploration of Social Networks}, journal = {IEEE Transactions on Visualization and Computer Graphics}, year = {2006}, volume = {12}, number = {5}, pages = {693--700}, url = {http://ieeexplore.ieee.org/search/wrapper.jsp?arnumber=4015419}, doi = {http://dx.doi.org/10.1109/TVCG.2006.122} }
Dwyer, T. & Marriott, K.	IPSep-CoLa: An Incremental Procedure for Separation Constraint Layout of Graphs [Abstract] [BibTeX]	2006	IEEE Transactions on Visualization and Computer Graphics Vol. 12(5), pp. 821-828	article	DOI URL
Abstract: We extend the popular force-directed approach to network (or graph) layout to allow separation constraints, which enforce a minimum horizontal or vertical separation between selected pairs of nodes. This simple class of linear constraints is expressive enough to satisfy a wide variety of application-specific layout requirements, including: layout of directed graphs to better show flow; layout with non-overlapping node labels; and layout of graphs with grouped nodes (called clusters). In the stress majorization force-directed layout process, separation constraints can be treated as a quadratic programming problem. We give an incremental algorithm based on gradient projection for efficiently solving this problem. The algorithm is considerably faster than using generic constraint optimization techniques and is comparable in speed to unconstrained stress majorization. We demonstrate the utility of our technique with sample data from a number of practical applications including gene-activation networks, terrorist networks and visualization of high-dimensional data.
BibTeX: @article{Dwyer06IPSep-CoLa_IncrementalProcedure, author = {Tim Dwyer and Kim Marriott}, title = {IPSep-CoLa: An Incremental Procedure for Separation Constraint Layout of Graphs}, journal = {IEEE Transactions on Visualization and Computer Graphics}, year = {2006}, volume = {12}, number = {5}, pages = {821--828}, url = {http://ieeexplore.ieee.org/search/wrapper.jsp?arnumber=4015435}, doi = {http://dx.doi.org/10.1109/TVCG.2006.156} }
Barnes, J. & Hut, P.	A hierarchical O(N log N) force-calculation algorithm [Abstract] [BibTeX]	1986	Nature Vol. 324(6096), pp. 446-449	article	DOI URL
Abstract: Until recently the gravitational N-body problem has been modelled numerically either by direct integration, in which the computation needed increases as N^2, or by an iterative potential method in which the number of operations grows as N log N. Here we describe a novel method of directly calculating the force on N bodies that grows only as N log N. The technique uses a tree-structured hierarchical subdivision of space into cubic cells, each of which is recursively divided into eight subcells whenever more than one particle is found to occupy the same cell. This tree is constructed anew at every time step, avoiding ambiguity and tangling. Advantages over potential-solving codes are: accurate local interactions; freedom from geometrical assumptions and restrictions; and applicability to a wide class of systems, including (proto-)planetary, stellar, galactic and cosmological ones. Advantages over previous hierarchical tree-codes include simplicity and the possibility of rigorous analysis of error. Although we concentrate here on stellar dynamical applications, our techniques of efficiently handling a large number of long-range interactions and concentrating computational effort where most needed have potential applications in other areas of astrophysics as well.
BibTeX: @article{Barnes86hierarchicalONlog, author = {Josh Barnes and Piet Hut}, title = {A hierarchical O(N log N) force-calculation algorithm}, journal = {Nature}, year = {1986}, volume = {324}, number = {6096}, pages = {446--449}, url = {http://www.nature.com/nature/journal/v324/n6096/abs/324446a0.html}, doi = {http://dx.doi.org/10.1038/324446a0} }
Hachul, S. & Jünger, M.	An Experimental Comparison of Fast Algorithms for Drawing General Large Graphs [Abstract] [BibTeX]	2006	Vol. 3843/2006GD '05: Proceedings of 13th International Symposium on Graph Drawing, pp. 235-250	inproceedings	DOI URL
Abstract: In the last decade several algorithms that generate straight-line drawings of general large graphs have been invented. In this paper we investigate some of these methods that are based on force-directed or algebraic approaches in terms of running time and drawing quality on a big variety of artificial and real-world graphs. Our experiments indicate that there exist significant differences in drawing qualities and running times depending on the classes of tested graphs and algorithms.
BibTeX: @inproceedings{Hachul06ExperimentalComparisonof, author = {Stefan Hachul and Michael Jünger}, title = {An Experimental Comparison of Fast Algorithms for Drawing General Large Graphs}, booktitle = {GD '05: Proceedings of 13th International Symposium on Graph Drawing}, publisher = {Springer}, year = {2006}, volume = {3843/2006}, pages = {235--250}, url = {http://www.springerlink.com/content/p22q4271k72734qn}, doi = {http://dx.doi.org/10.1007/11618058_22} }
Hachul, S. & Jünger, M.	Drawing Large Graphs with a Potential-Field-Based Multilevel Algorithm [Abstract] [BibTeX]	2005	Vol. 3383/2005GD '04: Proceedings of 12th International Symposium on Graph Drawing, pp. 285-295	inproceedings	DOI URL
Abstract: Force-directed graph drawing algorithms are widely used for drawing general graphs. However, these methods do not guarantee a sub-quadratic running time in general. We present a new force-directed method that is based on a combination of an efficient multilevel scheme and a strategy for approximating the repulsive forces in the system by rapidly evaluating potential fields. Given a graph G=( V, E), the asymptotic worst case running time of this method is O(textbarVtextbartextbackslashlogtextbarVtextbar+textbarEtextbar) with linear memory requirements. In practice, the algorithm generates nice drawings of graphs containing 100000 nodes in less than 5 minutes. Furthermore, it clearly visualizes even the structures of those graphs that turned out to be challenging for some other methods.
BibTeX: @inproceedings{Hachul05DrawingLargeGraphs, author = {Stefan Hachul and Michael Jünger}, title = {Drawing Large Graphs with a Potential-Field-Based Multilevel Algorithm}, booktitle = {GD '04: Proceedings of 12th International Symposium on Graph Drawing}, publisher = {Springer}, year = {2005}, volume = {3383/2005}, pages = {285--295}, url = {http://www.springerlink.com/content/u14g4c8tax0x7m9e}, doi = {http://dx.doi.org/10.1007/b105810} }
Huang, W., Hong, S. & Eades, P.	Effects of Sociogram Drawing Conventions and Edge Crossings in Social Network Visualizations [Abstract] [BibTeX]	2007	Journal of Graph Algorithms and Applications Vol. 11(2), pp. 397-429	article	URL
Abstract: This paper describes a user study examining the effects of different spatial layouts on human sociogram perception. The study compares the relative effectiveness of five sociogram drawing conventions in communicating the underlying network substance, based on task performance and user preference. The impact of edge crossings is also explored by using social network specific tasks. Both quantitative and qualitative methods are employed in the study. It was found that 1) both edge crossings and drawing conventions have significant effects on user preference and performance of finding groups, but neither has much impact on the perception of actor importance. On the other hand, node positioning and angular resolution may be more important in perceiving the importance of actors. In visualizing social networks, it is important to note that techniques that are highly preferred by users do not necessarily lead to optimal task performance. 2) the subjects have a strong preference for placing nodes on the top or in the center to highlight importance, and clustering nodes in the same group and separating clusters to highlight groups. They have tendency to believe that nodes on the top or in the center are more important, and nodes in close proximity belong to the same group. Some preliminary recommendations for sociogram design are also proposed.
BibTeX: @article{Huang07EffectsofSociogram, author = {Weidong Huang and Seok-Hee Hong and Peter Eades}, title = {Effects of Sociogram Drawing Conventions and Edge Crossings in Social Network Visualizations}, journal = {Journal of Graph Algorithms and Applications}, year = {2007}, volume = {11}, number = {2}, pages = {397--429}, url = {http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.63.636} }
McGrath, C., Blythe, J. & Krackhardt, D.	The effect of spatial arrangement on judgments and errors in interpreting graphs [Abstract] [BibTeX]	1997	Social Networks Vol. 19(3), pp. 223-242	article	DOI URL
Abstract: The spatial arrangement of social network data in graphs can influence viewers' perceptions of structural characteristics such as prominence, bridging and grouping. To study the extent of this effect, we conducted an experiment with 80 graduate students. Each student viewed three of five different spatial arrangements of the same network. We found that viewers' perceptions of structural features of the network changed as the spatial arrangement of the network changed.
BibTeX: @article{McGrath97effectofspatial, author = {Cathleen McGrath and Jim Blythe and David Krackhardt}, title = {The effect of spatial arrangement on judgments and errors in interpreting graphs}, journal = {Social Networks}, year = {1997}, volume = {19}, number = {3}, pages = {223--242}, url = {http://www.sciencedirect.com/science/article/B6VD1-3SWYCMP-8/2/90db2cbc12cefc1a2b9d4cde251af062}, doi = {http://dx.doi.org/10.1016/S0378-8733(96)00299-7} }
Moreno, J.L.	Who Shall Survive?: Foundations of Sociometry, Group Psychotherapy and Sociodrama [BibTeX]	1953	, pp. 141	book
Review: E: Edge crossings should be avoided in constructing good sociograms Huang05Layouteffectssociogram: Edge crossings has long been widely accepted a major aesthetic. Huang07EffectsofSociogram: ``The fewer the number of lines crossing, the better the sociogram.", p. 141
BibTeX: @book{Moreno53WhoShallSurvive?_, author = {Jacob L. Moreno}, title = {Who Shall Survive?: Foundations of Sociometry, Group Psychotherapy and Sociodrama}, publisher = {Beacon House}, year = {1953}, pages = {141} }
Purchase, H.C., Allder, J. & Carrington, D.	Graph Layout Aesthetics in UML Diagrams: User Preferences [Abstract] [BibTeX]	2002	Journal of Graph Algorithms and Applications Vol. 6(3), pp. 255-279	article	URL
Abstract: The merit of automatic graph layout algorithms is typically judged by their computational efficiency and the extent to which they conform to aesthetic criteria (for example, minimising the number of crossings, maximising orthogonality). Experiments investigating the worth of such algorithms from the point of view of human usability can take different forms, depending on whether the graph has meaning in the real world, the nature of the usability measurement, and the effect being investigated (algorithms or aesthetics). Previous studies have investigated performance on abstract graphs with respect to both aesthetics and algorithms, finding support for reducing the number of crossings and bends, and increasing the display of symmetry. This paper reports on preference experiments assessing the effect of individual aesthetics in the application domain of UML diagrams. Subjects’ preferences for one diagram over another were collected as quantitative data. Their stated reasons for their choice were collected as qualitative data. Analysis of this data enabled us to produce a priority listing of aesthetics for this domain. These UML preference results reveal a difference in aesthetic priority from those of previous domain-independent experiments.
BibTeX: @article{Purchase02GraphLayoutAesthetics, author = {Helen C. Purchase and Jo-Anne Allder and David Carrington}, title = {Graph Layout Aesthetics in UML Diagrams: User Preferences}, journal = {Journal of Graph Algorithms and Applications}, year = {2002}, volume = {6}, number = {3}, pages = {255--279}, url = {http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.84.4917} }
Ghoniem, M., Fekete, J. & Castagliola, P.	A Comparison of the Readability of Graphs Using Node-Link and Matrix-Based Representations [Abstract] [BibTeX]	2004	InfoVis '04: Proceedings of the 2004 IEEE Symposium on Information Visualization, pp. 17-24	inproceedings	DOI URL
Abstract: In this paper, we describe a taxonomy of generic graph related tasks and an evaluation aiming at assessing the readability of two representations of graphs: matrix-based representations and node-link diagrams. This evaluation bears on seven generic tasks and leads to important recommendations with regard to the representation of graphs according to their size and density. For instance, we show that when graphs are bigger than twenty vertices, the matrix-based visualization performs better than node-link diagrams on most tasks. Only path finding is consistently in favor of node-link diagrams throughout the evaluation.
BibTeX: @inproceedings{Ghoniem04ComparisonofReadability, author = {Mohammad Ghoniem and Jean-Daniel Fekete and Philippe Castagliola}, title = {A Comparison of the Readability of Graphs Using Node-Link and Matrix-Based Representations}, booktitle = {InfoVis '04: Proceedings of the 2004 IEEE Symposium on Information Visualization}, publisher = {IEEE Computer Society}, year = {2004}, pages = {17--24}, url = {http://www2.computer.org/portal/web/csdl/abs/proceedings/infovis/2004/8779/00/87790017abs.htm}, doi = {http://dx.doi.org/10.1109/INFOVIS.2004.1} }
Perer, A. & Shneiderman, B.	Integrating statistics and visualization: case studies of gaining clarity during exploratory data analysis [Abstract] [BibTeX]	2008	CHI '08: Proceeding of the 26th annual SIGCHI Conference on Human Factors in Computing Systems, pp. 265-274	inproceedings	DOI URL
Abstract: Although both statistical methods and visualizations have been used by network analysts, exploratory data analysis remains a challenge. We propose that a tight integration of these technologies in an interactive exploratory tool could dramatically speed insight development. To test the power of this integrated approach, we created a novel social network analysis tool, SocialAction, and conducted four long-term case studies with domain experts, each working on unique data sets with unique problems. The structured replicated case studies show that the integrated approach in SocialAction led to significant discoveries by a political analyst, a bibliometrician, a healthcare consultant, and a counter-terrorism researcher. Our contributions demonstrate that the tight integration of statistics and visualizations improves exploratory data analysis, and that our evaluation methodology for long-term case studies captures the research strategies of data analysts.
BibTeX: @inproceedings{Perer08Integratingstatisticsand, author = {Adam Perer and Ben Shneiderman}, title = {Integrating statistics and visualization: case studies of gaining clarity during exploratory data analysis}, booktitle = {CHI '08: Proceeding of the 26th annual SIGCHI Conference on Human Factors in Computing Systems}, publisher = {ACM}, year = {2008}, pages = {265--274}, url = {http://portal.acm.org/citation.cfm?doid=1357054.1357101}, doi = {http://doi.acm.org/10.1145/1357054.1357101} }
Scott, J.	Social Network Analysis: A Handbook [Abstract] [BibTeX]	2000		book	URL
Abstract: The revised and updated edition of this bestselling text provides an accessible introduction to the theory and practice of network analysis in the social sciences. It gives a clear and authoritative guide to the general framework of network analysis, explaining the basic concepts, technical measures and reviewing the available computer programs. The book outlines both the theoretical basis of network analysis and the key techniques for using it as a research tool. Building upon definitions of points, lines and paths, John Scott demonstrates their use in clarifying such measures as density, fragmentation and centralization. He identifies the various cliques, components and circles into which networks are formed, and outlines an approach to the study of socially structured positions. He also discusses the use of multidimensional methods for investigating social networks. Social Network Analysis is an invaluable resource for researchers across the social sciences and for students of social theory and research methods.
BibTeX: @book{Scott00SocialNetworkAnalysis_, author = {Scott, J.}, title = {Social Network Analysis: A Handbook}, publisher = {Sage}, year = {2000}, url = {http://books.google.com/books?id=Ww3_bKcz6kgC&printsec=frontcover#PPR9,M1} }
McGrath, C., Krackhardt, D. & Blythe, J.	Visualizing Complexity in Networks: Seeing Both the Forest and the Trees [Abstract] [BibTeX]	2003	Connections Vol. 25(1), pp. 37-47	article	URL
Abstract: Visualization of complex relational information has become increasingly important as complex data and computational power have become more available to social network researchers. Common sources of relational complexity include change over time, multiple relationships, network size, and network density. The most useful method for displaying complex data often depends upon the source of complexity and the nature of the information to be learned. In this paper, we explore the use of motion, especially for representation of change over time and relationship. Also, using data from a large Wall Street investment bank, we demonstrate several strategies to represent complex relational data in two-dimensions.
BibTeX: @article{McGrath03VisualizingComplexityin, author = {Cathleen McGrath and David Krackhardt and Jim Blythe}, title = {Visualizing Complexity in Networks: Seeing Both the Forest and the Trees}, journal = {Connections}, year = {2003}, volume = {25}, number = {1}, pages = {37--47}, url = {http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.74.3461} }
McGrath, C. & Blythe, J.	Do You See What I Want You to See? The Effects of Motion and Spatial Layout on Viewers' Perceptions of Graph Structure [Abstract] [BibTeX]	2004	Journal of Social Structure Vol. 5(2), pp. ?	article	URL
Abstract: In this study, we explore the combined effects of layout and motion on viewers' perceptions of social network data. We ask viewers to interpret the overall network and we ask domain specific questions about managing change within a departmental team to understand how network display influences viewers' overall perception of networks. We find that motion has a positive effect on the accuracy of viewers' perceptions of change in status from formal to informal networks. We also find no main effect for hierarchical versus spatially central layout on viewers' accuracy. There is a significant interaction effect of motion and graph layout on viewers perception of change. Finally, we find that when viewers are asked to make interpretations of the overall graph, they bring their own pre-existing graphical vocabulary that may influence their interpretation.
BibTeX: @article{McGrath04DoYouSee, author = {Cathleen McGrath and Jim Blythe}, title = {Do You See What I Want You to See? The Effects of Motion and Spatial Layout on Viewers' Perceptions of Graph Structure}, journal = {Journal of Social Structure}, year = {2004}, volume = {5}, number = {2}, pages = {?}, url = {http://www.cmu.edu/joss/content/articles/volume5/McGrathBlythe} }
Formann, M., Hagerup, T., Haralambides, J., Kaufmann, M., Leighton, F.T., Symvonis, A., Welzl, E. & Woeginger, G.J.	Drawing graphs in the plane with high resolution [Abstract] [BibTeX]	1993	SIAM Journal on Computing Vol. 22(5), pp. 1035-1052	article	DOI URL
Abstract: The problem of drawing a graph in the plane so that edges appear as straight lines and the minimum angle formed by any pair of incident edges is maximized is studied. The resolution of a layout is defined to be the size of the minimum angle formed by incident edges of the graph, and the resolution of a graph is defined to be the maximum resolution of any layout of the graph. The resolution R of a graph is characterized in terms of the maximum node degree d of the graph by proving that Omega(1/d2)&les;R&les;2pi/d for any graph. Moreover, it is proved that R=Theta(1/d ) for many graphs, including planar graphs, complete graphs, hypercubes, multidimensional meshes and tori, and other special networks. It is also shown that the problem of deciding if R=2pi/d for a graph is NP-hard for d=4, and a counting argument is used to show that R=O(log d /d2) for many graphs
BibTeX: @article{Formann93Drawinggraphsin, author = {Michael Formann and Torben Hagerup and James Haralambides and Michael Kaufmann and Frank Thomson Leighton and Antonios Symvonis and Emo Welzl and Gerhard J. Woeginger}, title = {Drawing graphs in the plane with high resolution}, journal = {SIAM Journal on Computing}, publisher = {Society for Industrial and Applied Mathematics}, year = {1993}, volume = {22}, number = {5}, pages = {1035--1052}, url = {http://scitation.aip.org/getabs/servlet/GetabsServlet?prog=normal&id=SMJCAT000022000005001035000001&idtype=cvips&gifs=yes}, doi = {http://dx.doi.org/10.1137/0222063} }
Blythe, J., McGrath, C. & Krackhardt, D.	The Effect of Graph Layout on Inference from Social Network Data [Abstract] [BibTeX]	1996	Vol. 1027/1996GD '95: Proceedings of the 3rd International Symposium on Graph Drawing, pp. 40-51	inproceedings	DOI URL
Abstract: Social network analysis uses techniques from graph theory to analyze the structure of relationships among social actors such as individuals or groups. We investigate the effect of the layout of a social network on the inferences drawn by observers about the number of social groupings evident and the centrality of various actors in the network. We conducted an experiment in which eighty subjects provided answers about three drawings. The subjects were not told that the drawings were chosen from five different layouts of the same graph. We found that the layout has a significant effect on their inferences and present some initial results about the way certain Euclidean features will affect perceptions of structural features of the network. There is no "best" layout for a social network; when layouts are designed one must take into account the most important features of the network to be presented as well as the network itself.
BibTeX: @inproceedings{Blythe96EffectofGraph, author = {Jim Blythe and Cathleen McGrath and David Krackhardt}, title = {The Effect of Graph Layout on Inference from Social Network Data}, booktitle = {GD '95: Proceedings of the 3rd International Symposium on Graph Drawing}, publisher = {Springer}, year = {1996}, volume = {1027/1996}, pages = {40--51}, url = {http://www.springerlink.com/content/f17640275016m645}, doi = {http://dx.doi.org/10.1007/BFb0021783} }
Körner, C.	Sequential Processing in Comprehension of Hierarchical Graphs [Abstract] [BibTeX]	2004	Applied Cognitive Psychology Vol. 18(4), pp. 467-480	article	DOI URL
Abstract: Hierarchical graphs represent the relationships between non-numerical entities or concepts (like computer file systems, family trees, etc). Graph nodes represent the concepts and interconnecting lines represent the relationships. We recorded participants' eye movements while viewing such graphs to test two possible models of graph comprehension. Graph readers had to answer interpretive questions, which required comparisons between two graph nodes. One model postulates a search and a combined search-reasoning stage of graph comprehension (two-stage model), whereas the second model predicts three stages, two stages devoted to the search of the relevant graph nodes and a separate reasoning stage. A detailed analysis of the eye movement data provided clear support for the three-stage model. This is in line with recent studies, which suggest that participants serialize problem solving tasks in order to minimize the overall processing load.
BibTeX: @article{Korner04SequentialProcessingin, author = {Christof Körner}, title = {Sequential Processing in Comprehension of Hierarchical Graphs}, journal = {Applied Cognitive Psychology}, year = {2004}, volume = {18}, number = {4}, pages = {467--480}, url = {http://www3.interscience.wiley.com/journal/108063531/abstract}, doi = {http://dx.doi.org/10.1002/acp.997} }
Purchase, H.C., Carrington, D. & Allder, J.	Empirical Evaluation of Aesthetics-based Graph Layout [Abstract] [BibTeX]	2002	Empirical Software Engineering Vol. 7(3), pp. 233-255	article	DOI URL
Abstract: Many automatic graph layout algorithms have been designed and implemented to display relational data in a graphical (usually node-arc) manner. The success of these algorithms is typically measured by their computational efficiency and the extent to which they conform to aesthetic criteria (for example, minimising the number of crossings, maximising symmetry). Little research has been performed on the usability aspects of such algorithms: do they produce graph drawings that make the embodied information easy to use and understand&quest; Is the computational effort expended on conforming to the assumed aesthetic criteria justifiable with respect to better usability&quest; This paper reports on usability studies that were performed to investigate the merit of automatic graph layout algorithms with respect to human use. The paper describes three ways in which this issue has been considered experimentally: first, investigating individual aesthetic criteria in simple, abstract graph structures; second, investigating the results of common automatic graph layout algorithms; and third, investigating individual aesthetic criteria and other relevant secondary notations in Unified Modeling Language class and collaboration diagrams. The results show that the use of only some aesthetics affect usability significantly, and that the semantic domain of the graph drawings affects which aesthetic criteria need to be emphasised.
BibTeX: @article{Purchase02EmpiricalEvaluationof, author = {Helen C. Purchase and David Carrington and Jo-Anne Allder}, title = {Empirical Evaluation of Aesthetics-based Graph Layout}, journal = {Empirical Software Engineering}, publisher = {Kluwer Academic Publishers}, year = {2002}, volume = {7}, number = {3}, pages = {233--255}, url = {http://www.springerlink.com/content/a7jj4ghv9nc4twg1}, doi = {http://dx.doi.org/10.1023/A:1016344215610} }
Purchase, H.C., Cohen, R.F. & James, M.	Validating Graph Drawing Aesthetics [Abstract] [BibTeX]	1996	Vol. 1027/1996GD '95: Proceedings of the 3rd International Symposium on Graph Drawing, pp. 435-446	inproceedings	DOI URL
Abstract: Designers of graph drawing algorithms and systems claim to illuminate application data by producing layouts that optimize measurable aesthetic qualities. Examples of these aesthetics include symmetry (where possible, a symmetrical view of the graph should be displayed), minimize edge crossings (the number of edge crossings in the display should be minimized), and minimize bends (the total number of bends in polyline edges should be minimized). The aim of this paper is to describe our work to validate these claims by performing empirical studies of human understanding of graphs drawn using various layout aesthetics. This work is important since it helps indicate to algorithm and system designers what are the aesthetic qualities most important to aid understanding, and consequently to build more effective systems.
BibTeX: @inproceedings{Purchase96ValidatingGraphDrawing, author = {Helen C. Purchase and Robert F. Cohen and Murray James}, title = {Validating Graph Drawing Aesthetics}, booktitle = {GD '95: Proceedings of the 3rd International Symposium on Graph Drawing}, publisher = {Springer}, year = {1996}, volume = {1027/1996}, pages = {435--446}, url = {http://www.springerlink.com/content/f73573q233v1h17u}, doi = {http://dx.doi.org/10.1007/BFb0021827} }
Purchase, H.C.	Performance of Layout Algorithms: Comprehension, not Computation [Abstract] [BibTeX]	1998	Journal of Visual Languages & Computing Vol. 9(6), pp. 647-657	article	DOI URL
Abstract: Many algorithms address the problem of rendering an abstract graph structure as a diagram in as efficient and as elegant a manner as possible. The criteria for judging the worth of these algorithms are typically the extent to which they conform to common aesthetic criteria (e.g. minimising the number of crossings, maximising symmetry), or their computational efficiency. The algorithms are not usually judged on their ability to produce diagrams that maximise humans’ performance on tasks which require their use. This paper presents an example experimental methodology for considering the relative worth of eight layout algorithms with respect to human performance, together with details of an experiment using a single graph. The results indicate that, with the exception of one algorithm, there is no statistical difference between the performance data of the algorithms when applied to this graph, indicating that they produce drawings of comparable difficulty. This result is despite the different aesthetic bases for the algorithms.
BibTeX: @article{Purchase98PerformanceofLayout, author = {Helen C. Purchase}, title = {Performance of Layout Algorithms: Comprehension, not Computation}, journal = {Journal of Visual Languages & Computing}, year = {1998}, volume = {9}, number = {6}, pages = {647--657}, url = {http://www.sciencedirect.com/science/article/B6WMM-45J5BKS-5/2/f2d27b9e887b63c9f3247c933f4a9bf2}, doi = {http://dx.doi.org/10.1006/jvlc.1998.0093} }
Purchase, H.C. & Leonard, D.	Graph Drawing Aesthetic Metrics [BibTeX]	1996	(361)	techreport
BibTeX: @techreport{Purchase96GraphDrawingAesthetic, author = {Helen C. Purchase and David Leonard}, title = {Graph Drawing Aesthetic Metrics}, year = {1996}, number = {361} }
Perer, A. & Shneiderman, B.	Systematic yet flexible discovery: guiding domain experts through exploratory data analysis [Abstract] [BibTeX]	2008	IUI '08: Proceedings of the 13th International Conference on Intelligent User Interfaces, pp. 109-118	inproceedings	DOI URL
Abstract: During exploratory data analysis, visualizations are often useful for making sense of complex data sets. However, as data sets increase in size and complexity, static information visualizations decrease in comprehensibility. Interactive techniques can yield valuable discoveries, but current data analysis tools typically support only opportunistic exploration that may be inefficient and incomplete. We present a refined architecture that uses systematic yet flexible (SYF) design goals to guide domain expert users through complex exploration of data over days, weeks and months. The SYF system aims to support exploratory data analysis with some of the simplicity of an e-commerce check-out while providing added flexibility to pursue insights. The SYF system provides an overview of the analysis process, suggests unexplored states, allows users to annotate useful states, supports collaboration, and enables reuse of successful strategies. The affordances of the SYF system are demonstrated by integrating it into a social network analysis tool employed by social scientists and intelligence analysts. The SYF system is a tool-independent component and can be incorporated into other data analysis tools.
BibTeX: @inproceedings{Perer08Systematicyetflexible, author = {Adam Perer and Ben Shneiderman}, title = {Systematic yet flexible discovery: guiding domain experts through exploratory data analysis}, booktitle = {IUI '08: Proceedings of the 13th International Conference on Intelligent User Interfaces}, publisher = {ACM}, year = {2008}, pages = {109--118}, url = {http://portal.acm.org/citation.cfm?doid=1378773.1378788}, doi = {http://doi.acm.org/10.1145/1378773.1378788} }
Brandes, U., Kenis, P., Raab, J., Schneider, V. & Wagner, D.	Explorations into the visualization of policy networks [Abstract] [BibTeX]	1999	Journal of Theoretical Politics Vol. 11(11), pp. 75-106	article	DOI
Abstract: Visualization is an important aspect of both exploration and communication of categorical as well as relational data. Graphical displays of policy networks are particularly attractive, since they enable authors to display in a compact way the relevant actors in a network, how they are related to each other, and what the overall structure looks like. Sociograms were early companions of social network analysis, but have received surprisingly little attention during the following decades. Only in the last few years has easy accessibility to quality computing and graphic equipment revived a now rapidly growing interest. In this paper, we analyze the problem of visualizing policy networks. We first argue why network visualization is important and non-trivial. Then we show that current methods are somewhat ad hoc in their attempt to convey information contained in a network. Our main contribution is a systematic approach to network visualization, closely following the general principles of information visualization. It provides a generic formalization which may serve as a guideline for further developments.
BibTeX: @article{Brandes99Explorationsintovisualization, author = {Ulrik Brandes and Patrick Kenis and Jörg Raab and Volker Schneider and Dorothea Wagner}, title = {Explorations into the visualization of policy networks}, journal = {Journal of Theoretical Politics}, year = {1999}, volume = {11}, number = {11}, pages = {75--106}, doi = {http://dx.doi.org/10.1177/0951692899011001004} }
Huang, W., Hong, S. & Eades, P.	How people read sociograms: a questionnaire study [Abstract] [BibTeX]	2006	APVis '06: Proceedings of the 2006 Asia-Pacific Symposium on Information Visualisation, pp. 199-206	inproceedings	URL
Abstract: Visualizing social network data into sociograms plays an important role in communicating information about network characteristics. Previous studies have shown that human perceptions of network features can be affected by the layout of a sociogram [McGrath et al. 1996, 1997]. An empirical user study has been conducted to investigate effectiveness of five different network visualization conventions and impact of edge crossings on sociogram perceptions, using both quantitative performance and preference measures and qualitative questionnaire study. This paper reports results and findings of the questionnaire study. We relate qualitative questionnaire results with quantitative findings and discuss their implications for sociogram design. We found that subjects had a strong preference of placing nodes on the top or in the center to highlight importance, and clustering nodes in the same group and separating groups to highlight groups. They had tendency to believe that nodes in the center or on the top are more important, and nodes in close proximity belong to the same group. Some preliminary recommendations for sociogram design and hypotheses about human reading behaviors are proposed.
BibTeX: @inproceedings{Huang06Howpeopleread, author = {Weidong Huang and Seok-Hee Hong and Peter Eades}, title = {How people read sociograms: a questionnaire study}, booktitle = {APVis '06: Proceedings of the 2006 Asia-Pacific Symposium on Information Visualisation}, year = {2006}, pages = {199--206}, url = {http://portal.acm.org/citation.cfm?id=1151932} }
Sugiyama, K.	Graph Drawing and Applications for Software and Knowledge Engineers [Abstract] [BibTeX]	2002	Vol. 11Hardcover	book	URL
Abstract: This book is useful for readers who want to visualize graphs as representing structural knowledge in a variety of fields. It gives an outline of the whole field, describes in detail the representative methods for drawing graphs, explains extensions such as fisheye and dynamic drawing, presents many practical applications, and discusses ways of evaluation. It makes the intuitive understanding of these easier by using examples and diagrams, and provides a wealth of references for those readers who wish to know more. Contents: A Framework for Automatic Graph Drawing Methods; Outlines of Automatic Graph Drawing Methods; Details of Automatic Graph Drawing Methods; Extensions of Automatic Graph Drawing Methods; A Variety of Applications; Applications for Creativity Support.
BibTeX: @book{Sugiyama02GraphDrawingand, author = {Kozo Sugiyama}, title = {Graph Drawing and Applications for Software and Knowledge Engineers}, publisher = {World Scientific Publishing Company}, year = {2002}, volume = {11}, url = {http://books.google.com/books?id=H06j5GJKITIC} }
Batini, C., Furlani, L. & Nardelli, E.	What is a Good Diagram? A Pragmatic Approach [BibTeX]	1985	ER '85: Proceedings of the 4th International Conference on the Entity-Relationship Approach to Software Engineering, pp. 312-319	inproceedings	URL
BibTeX: @inproceedings{Batini85WhatisGood, author = {Carlo Batini and L. Furlani and Enrico Nardelli}, title = {What is a Good Diagram? A Pragmatic Approach}, booktitle = {ER '85: Proceedings of the 4th International Conference on the Entity-Relationship Approach to Software Engineering}, publisher = {IEEE Computer Society}, year = {1985}, pages = {312--319}, url = {http://portal.acm.org/citation.cfm?id=647510.726382} }
Eichelberger, H.	Nice class diagrams admit good design? [Abstract] [BibTeX]	2003	SoftVis '03: Proceedings of the 2003 ACM Symposium on Software Visualization, pp. 159-216	inproceedings	DOI URL
Abstract: Analysis and design of programs by using tools has emerged to a standard technique in object-oriented software engineering. Many of these tools claim to implement methods according to the UML standard and some of the tools provide automatic layout of the diagrams drawn by the user or generated automatically from source code. In this paper we propose a set of aesthetic criteria for UML class diagrams and discuss the relation between these criteria, HCI and design aspects of object-oriented software.First we describe critics from the viewpoint of HCI to the UML notation and restrict ourself to changes which do not require nonstandard modifications to the UML notation guide, then we list quality relations between class diagrams and object-oriented software models. After that our set of aesthetic criteria, that reflect the highly sophisticated structural and semantic features of UML class diagrams, is explained. Finally, we show that an implementation and measurement of this proposal is realizable using a prototypical graph drawing framework.
BibTeX: @inproceedings{Eichelberger03Niceclassdiagrams, author = {Holger Eichelberger}, title = {Nice class diagrams admit good design?}, booktitle = {SoftVis '03: Proceedings of the 2003 ACM Symposium on Software Visualization}, publisher = {ACM}, year = {2003}, pages = {159--216}, url = {http://portal.acm.org/citation.cfm?doid=774833.774857}, doi = {http://doi.acm.org/10.1145/774833.774857} }
Ware, C.	Information visualization: perception for design [BibTeX]	2004		book	URL
BibTeX: @book{Ware04Informationvisualization_perception, author = {Colin Ware}, title = {Information visualization: perception for design}, publisher = {Morgan Kaufmann Publishers Inc.}, year = {2004}, url = {http://books.google.com/books?id=2ZlORD5hX7QC} }
Purchase, H.C.	The effects of graph layout [Abstract] [BibTeX]	1998	OZCHI '08: Proceedings of the 2008 Australasian Computer Human Interaction Conference, pp. 80-86	inproceedings	DOI URL
Abstract: Information visualisation systems which generate diagrams representing discrete relational information must consider potential users if they are to be effective. Many algorithms which render an abstract graph structure as a diagram are valued for their conformance to aesthetic criteria, or for computational efficiency. They are not usually judged on their ability to produce diagrams that maximise human performance. The paper presents the results of experiments investigating the relative worth (from an HCI point of view) of graph drawing aesthetics and algorithms using a single graph. The results indicate that while some individual aesthetics affect human performance, it is difficult to say that one algorithm is `better' than another from a relational understanding point of view
BibTeX: @inproceedings{Purchase98effectsofgraph, author = {Helen C. Purchase}, title = {The effects of graph layout}, booktitle = {OZCHI '08: Proceedings of the 2008 Australasian Computer Human Interaction Conference}, year = {1998}, pages = {80--86}, url = {http://ieeexplore.ieee.org/search/wrapper.jsp?arnumber=732199}, doi = {http://dx.doi.org/10.1109/OZCHI.1998.732199} }
Wetherell, C. & Shannon, A.	Tidy Drawings of Trees [Abstract] [BibTeX]	1979	IEEE Transactions on Software Engineering Vol. SE-5(5), pp. 514-520	article	DOI URL
Abstract: Trees are extremely common data structures, both as internal objects and as models for program output. But it is unusual to see a program actually draw trees for visual inspection. Although part of the difficulty lies in programming graphics devices, most of the problem arises because naive algorithms to draw trees use too much drawing space and sophisticated algorithms are not obvious. We survey two naive tree drawers, formalize aesthetics for tidy trees, and descnbe two algorithms which draw tidy trees. One of the algorithms may be shown to require the minimum possible paper width. Along with the algorithms proper, we discuss the reasoning behind the algorithm development.
BibTeX: @article{Wetherell79TidyDrawingsof, author = {Charles Wetherell and Alfred Shannon}, title = {Tidy Drawings of Trees}, journal = {IEEE Transactions on Software Engineering}, publisher = {IEEE Press}, year = {1979}, volume = {SE-5}, number = {5}, pages = { 514--520}, url = {http://ieeexplore.ieee.org/search/wrapper.jsp?arnumber=1702661}, doi = {http://dx.doi.org/10.1109/TSE.1979.234212} }
Coleman, M.K. & Parker, D.S.	Aesthetics-based graph layout for human consumption [Abstract] [BibTeX]	1996	Software: Practice and Experience Vol. 26(12), pp. 1415-1438	article	DOI URL
Abstract: Automatic graph layout is an important and long-studied problem. The basic straight-edge graph layout problem is to find spatial positions for the nodes of an input graph that maximize some measure of desirability. When graph layout is intended for human consumption, we call this measure of desirability an aesthetic. We seek an algorithm that produces graph layouts of high aesthetic quality not only for general graphs, but also for specific classes of graphs, such as trees and directed acyclic graphs. The Aesthetic Graph Layout (AGLO) approach described in this paper models graph layout as a multiobjective optimization problem, where the value of a layout is determined by multiple user-controlled layout aesthetics. The current AGLO algorithm combines the power and flexibility of the simulated annealing approach of Davidson and Harel (1989) with the relative speed of the method of Fruchterman and Reingold (1991). In addition, it is more general, and incorporates several new layout aesthetics to support new layout styles. Using these aesthetics, we are able to produce pleasing displays for graphs on which these other methods flounder.
BibTeX: @article{Coleman96Aesthetics-basedgraphlayout, author = {Michael K. Coleman and D. Stott Parker}, title = {Aesthetics-based graph layout for human consumption}, journal = {Software: Practice and Experience}, publisher = {John Wiley & Sons, Inc.}, year = {1996}, volume = {26}, number = {12}, pages = {1415--1438}, url = {http://www3.interscience.wiley.com/journal/16781/abstract}, doi = {http://dx.doi.org/10.1002/(SICI)1097-024X(199612)26:12<1415::AID-SPE69>3.3.CO;2-G} }
Fruchterman, T.M.J. & Reingold, E.M.	Graph Drawing by Force-directed Placement [Abstract] [BibTeX]	1991	Software: Practice and Experience Vol. 21(11), pp. 1129-1164	article	DOI URL
Abstract: We present a modification of the spring-embedder model of Eades [ Congresses Numerantium, 42, 149–160, (1984)] for drawing undirected graphs with straight edges. Our heuristic strives for uniform edge lengths, and we develop it in analogy to forces in natural systems, for a simple, elegant, conceptuallyintuitive, and efficient algorithm.
BibTeX: @article{Fruchterman91GraphDrawingby, author = {Thomas M. J. Fruchterman and Edward M. Reingold}, title = {Graph Drawing by Force-directed Placement}, journal = {Software: Practice and Experience}, publisher = {John Wiley & Sons, Inc.}, year = {1991}, volume = {21}, number = {11}, pages = {1129--1164}, url = {http://portal.acm.org/citation.cfm?id=137556.137557}, doi = {http://dx.doi.org/10.1002/spe.4380211102} }
Davidson, R. & Harel, D.	Drawing graphs nicely using simulated annealing [Abstract] [BibTeX]	1996	ACM Transactions on Graphics Vol. 15(4), pp. 301-331	article	DOI URL
Abstract: The paradigm of simulated annealing is applied to the problem of drawing graphs “nicely.” Our algorithm deals with general undirected graphs with straight-line edges, and employs several simple criteria for the aesthetic quality of the result. The algorithm is flexible, in that the relative weights of the criteria can be changed. For graphs of modest size it produces good results, competitive with those produced by other methods, notably, the “spring method” and its variants.
BibTeX: @article{Davidson96Drawinggraphsnicely, author = {Ron Davidson and David Harel}, title = {Drawing graphs nicely using simulated annealing}, journal = {ACM Transactions on Graphics}, publisher = {ACM}, year = {1996}, volume = {15}, number = {4}, pages = {301--331}, url = {http://portal.acm.org/citation.cfm?doid=234535.234538}, doi = {http://doi.acm.org/10.1145/234535.234538} }
Sugiyama, K., Tagawa, S. & Toda, M.	Methods for Visual Understanding of Hierarchical System Structures [Abstract] [BibTeX]	1981	IEEE Transactions on Systems, Man and Cybernetics Vol. 11(2), pp. 109-125	article	DOI URL
Abstract: Two kinds of new methods are developed to obtain effective representations of hierarchies automatically: theoretical and heuristic methods. The methods determine the positions of vertices in two steps. First the order of the vertices in each level is determined to reduce the number of crossings of edges. Then horizontal positions of the vertices are determined to improve further the readability of drawings. The theoretical methods are useful in recognizing the nature of the problem, and the heuristic methods make it possible to enlarge the size of hierarchies with which we can deal. Performance tests of the heuristic methods and several applications are presented.
BibTeX: @article{Sugiyama81MethodsVisualUnderstanding, author = {Kozo Sugiyama and Shojiro Tagawa and Mitsuhiko Toda}, title = {Methods for Visual Understanding of Hierarchical System Structures}, journal = {IEEE Transactions on Systems, Man and Cybernetics}, year = {1981}, volume = {11}, number = {2}, pages = {109--125}, url = {http://ieeexplore.ieee.org/search/wrapper.jsp?arnumber=4308636}, doi = {http://dx.doi.org/10.1109/TSMC.1981.4308636} }
Eades, P.	Symmetry finding algorithms [BibTeX]	1988	Computational Morphology	inproceedings
BibTeX: @inproceedings{Eades88Symmetryfindingalgorithms, author = {Peter Eades}, title = {Symmetry finding algorithms}, booktitle = {Computational Morphology}, publisher = {North-Holland}, year = {1988} }
Lipton, R.J., North, S.C. & Sandberg, J.S.	A method for drawing graphs [Abstract] [BibTeX]	1985	SCG '85: Proceedings of the 1st Annual Symposium on Computational Geometry, pp. 153-160	inproceedings	DOI URL
Abstract: Intro: We are developing programs that draw pictures of graphs in the plane. Since graphs are a very powerful way to capture information such programs have many applications. However, there is a fundamental problem with creating such programs: graphs are abstract objects, and do not include any information about how they are to be displayed. There are an infinite number of pictures that represent a given graph. How are we to decide which is best. Our main contribution is observing that a drawing of a graph is “good” when it displays as many symmetries as possible.
BibTeX: @inproceedings{Lipton85methoddrawinggraphs, author = {R. J. Lipton and S. C. North and J. S. Sandberg}, title = {A method for drawing graphs}, booktitle = {SCG '85: Proceedings of the 1st Annual Symposium on Computational Geometry}, publisher = {ACM}, year = {1985}, pages = {153--160}, url = {http://portal.acm.org/citation.cfm?doid=323233.323254}, doi = {http://doi.acm.org/10.1145/323233.323254} }
Manning, J., Atallah, M.J., Cudjoe, K., Lozito, J. & Pacheco, R.	A System for Drawing Graphs with Geometric Symmetry [Abstract] [BibTeX]	1995	Vol. 894/1995GD '94: Proceedings of the 1994 DIMACS International Workshop on Graph Drawing, pp. 262-265	inproceedings	DOI URL
Abstract: This demonstration presents a computer system to generate symmetric drawings of certain classes of planar graphs.
BibTeX: @inproceedings{Manning95SystemDrawingGraphs, author = {Joseph Manning and Mikhail J. Atallah and Kingsley Cudjoe and Joe Lozito and Ron Pacheco}, title = {A System for Drawing Graphs with Geometric Symmetry}, booktitle = {GD '94: Proceedings of the 1994 DIMACS International Workshop on Graph Drawing}, publisher = {Springer}, year = {1995}, volume = {894/1995}, pages = {262--265}, url = {http://www.springerlink.com/content/p26540808r747803}, doi = {http://dx.doi.org/10.1007/3-540-58950-3_378} }
Wasserman, S. & Faust, K.	Social Network Analysis: Methods and Applications [BibTeX]	1994	, pp. 857	book	URL
BibTeX: @book{Wasserman94SocialNetworkAnalysis_, author = {Stanley Wasserman and Katherine Faust}, title = {Social Network Analysis: Methods and Applications}, publisher = {Cambridge University Press}, year = {1994}, pages = {857}, edition = {1}, url = {http://books.google.com/books?id=CAm2DpIqRUIC} }
Eades, P.A.	A heuristic for graph drawing. [BibTeX]	1984	Vol. 42Congressus Numerantium, pp. 149-160	inproceedings
Review: E: Huang06Howpeopleread: Commonly used social network analysis and visualization tools typically use, for example, variants of the spring embedder M: Original spring paper
BibTeX: @inproceedings{Eades84heuristicgraphdrawing., author = {Peter A. Eades}, title = {A heuristic for graph drawing.}, booktitle = {Congressus Numerantium}, year = {1984}, volume = {42}, pages = {149--160} }
Brandes, U., Raab, J. & Wagner, D.	Exploratory Network Visualization: Simultaneous Display of Actor Status and Connections [Abstract] [BibTeX]	2001	Journal of Social Structure Vol. 2(4), pp. ?	article	URL
Abstract: We propose a novel visualization approach that facilitates graphical exploration and communication of relative actor status in social networks. The main idea is to map, in a drawing of the entire network, actor status scores to vertical coordinates. The resulting problem of determining horizontal positions of actors and routing of connecting lines such that the overall layout is readable is algorithmically diﬃcult, yet well-studied in the literature on graph drawing. We outline a customized approach. The advantages of our method are illustrated in a study of policy making structures from the privatization processes of former East German industrial conglomerates, in which the visual approach led to additional ﬁndings that are unlikely to have been revealed using non-visual means of analysis.
BibTeX: @article{Brandes01ExploratoryNetworkVisualization_, author = {Ulrik Brandes and Jörg Raab and Dorothea Wagner}, title = {Exploratory Network Visualization: Simultaneous Display of Actor Status and Connections}, journal = {Journal of Social Structure}, year = {2001}, volume = {2}, number = {4}, pages = {?}, url = {http://citeseer.ist.psu.edu/brandes01exploratory.html} }
Finkel, B. & Tamassia, R.	Curvilinear Graph Drawing Using the Force-Directed Method [Abstract] [BibTeX]	2005	Vol. 3383/2005GD '04: Proceedings of the 12th International Symposium on Graph Drawing, pp. 448-453	inproceedings	DOI URL
Abstract: We present a method for modifying a force-directed graph drawing algorithm into an algorithm for drawing graphs with curved lines. Our method is based on embedding control points as dummy vertices so that edges can be drawn as splines. Our experiments show that our method yields aesthetically pleasing curvilinear drawing with improved angular resolution. Applying our method to the GEM algorithm on the test suite of the "Rome Graphs" resulted in an average improvement of 46% in angular resolution and of almost 6% in edge crossings.
BibTeX: @inproceedings{Finkel05CurvilinearGraphDrawing, author = {Benjamin Finkel and Roberto Tamassia}, title = {Curvilinear Graph Drawing Using the Force-Directed Method}, booktitle = {GD '04: Proceedings of the 12th International Symposium on Graph Drawing}, publisher = {Springer}, year = {2005}, volume = {3383/2005}, pages = {448--453}, url = {http://www.springerlink.com/content/cml27dvuphba30ax}, doi = {http://dx.doi.org/10.1007/b105810} }
Misue, K., Eades, P., Lai, W. & Sugiyama, K.	Layout Adjustment and the Mental Map [Abstract] [BibTeX]	1995	Journal of Visual Languages & Computing Vol. 6(2), pp. 183-210	article	DOI URL
Abstract: Many models in software and information engineering use graph representations; examples are data flow diagrams, state transition diagrams, flow charts, PERT charts, organization charts, Petri nets and entity-relationship diagrams. The usefulness of these graph representations depends on the quality of the layout of the graphs. Automatic graph layout, which can release humans from graph drawing, is now available in several visualization systems. Most automatic layout facilities take a purely combinatorial description of a graph and produce a layout of the graph; these methods are called 'layout creation' methods. For interactive systems, another kind of layout is needed: a facility which can adjust a layout after a change is made by the user or by the application. Although layout adjustment is essential in interactive systems, most existing layout algorithms are designed for layout creation. The use of a layout creation method for layout adjustment may totally rearrange the layout and thus destroy the user's 'mental map' of the diagram; thus a set of layout adjustment methods, separate from layout creation methods, is needed. This paper discusses some layout adjustment methods and the preservation of the 'mental map' of the diagram. First, several models are proposed to make the concept of 'mental map' more precise. Then two kinds of layout adjustments are described. One is an algorithm for rearranging a diagram to avoid overlapping nodes, and the other is a method aimed at changing the focus of interest of the user without destroying the mental map. Next, some experience with visualization systems in which the techniques have been employed is also described.
BibTeX: @article{Misue95LayoutAdjustmentand, author = {Kazuo Misue and Peter Eades and Wei Lai and Kozo Sugiyama}, title = {Layout Adjustment and the Mental Map}, journal = {Journal of Visual Languages & Computing}, year = {1995}, volume = {6}, number = {2}, pages = {183--210}, url = {http://www.sciencedirect.com/science/article/B6WMM-45PVMS3-13/2/0f1f0f6cf4f49a7892fb6064751b128c}, doi = {http://dx.doi.org/10.1006/jvlc.1995.1010} }
Seo, J. & Shneiderman, B.	A rank-by-feature framework for interactive exploration of multidimensional data [Abstract] [BibTeX]	2005	Information Visualization Vol. 4(2), pp. 96-113	article	DOI URL
Abstract: Interactive exploration of multidimensional data sets is challenging because: (1) it is difficult to comprehend patterns in more than three dimensions, and (2) current systems often are a patchwork of graphical and statistical methods leaving many researchers uncertain about how to explore their data in an orderly manner. We offer a set of principles and a novel rank-by-feature framework that could enable users to better understand distributions in one (1D) or two dimensions (2D), and then discover relationships, clusters, gaps, outliers, and other features. Users of our framework can view graphical presentations (histograms, boxplots, and scatterplots), and then choose a feature detection criterion to rank 1D or 2D axis-parallel projections. By combining information visualization techniques (overview, coordination, and dynamic query) with summaries and statistical methods users can systematically examine the most important 1D and 2D axis-parallel projections. We summarize our Graphics, Ranking, and Interaction for Discovery (GRID) principles as: (1) study 1D, study 2D, then find features (2) ranking guides insight, statistics confirm. We implemented the rank-by-feature framework in the Hierarchical Clustering Explorer, but the same data exploration principles could enable users to organize their discovery process so as to produce more thorough analyses and extract deeper insights in any multidimensional data application, such as spreadsheets, statistical packages, or information visualization tools.
BibTeX: @article{Seo05rank-by-featureframeworkinteractive, author = {Jinwook Seo and Ben Shneiderman}, title = {A rank-by-feature framework for interactive exploration of multidimensional data}, journal = {Information Visualization}, publisher = {Palgrave Macmillan}, year = {2005}, volume = {4}, number = {2}, pages = {96--113}, url = {http://www.palgrave-journals.com/ivs/journal/v4/n2/abs/9500091a.html}, doi = {http://dx.doi.org/10.1057/palgrave.ivs.9500091} }
Batagelj, V. & Mrvar, A.	Pajek - Program for Large Network Analysis [Abstract] [BibTeX]	1998	Connections Vol. 21, pp. 47-57	article	URL
Abstract: Large networks, having thousands of vertices and lines, can be found in many different areas, e. g: genealogies, flow graphs of programs, molecule, computer networks, transportation networks, social networks, intra/inter organisational networks... Many standard network algorithms are very time and space consuming and therefore unsuitable for analysis of such networks. In the article we present some approaches to analysis and visualisation of large networks implemented in programPajek. Some typical examples are also given. 1
BibTeX: @article{Batagelj98Pajek-Program, author = {Vladimir Batagelj and Andrej Mrvar}, title = {Pajek - Program for Large Network Analysis}, journal = {Connections}, year = {1998}, volume = {21}, pages = {47--57}, url = {http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.27.9156} }
Viégas, F.B. & Wattenberg, M.	Communication-Minded Visualization: A Call to Action [BibTeX]	2006	IBM Systems Journal Vol. 45(4), pp. 801-812	article	URL
BibTeX: @article{Viegas06Communication-MindedVisualization_Call, author = {Fernanda B. Viégas and Martin Wattenberg}, title = {Communication-Minded Visualization: A Call to Action}, journal = {IBM Systems Journal}, year = {2006}, volume = {45}, number = {4}, pages = {801--812}, url = {http://www.research.ibm.com/journal/sj/454/viegas.html} }
Shneiderman, B.	The Eyes Have It: A Task by Data Type Taxonomy for Information Visualizations [Abstract] [BibTeX]	1996	VL '96: Proceedings of the 1996 IEEE Symposium on Visual Languages, pp. 336-343	inproceedings	DOI URL
Abstract: A useful starting point for designing advanced graphical user interfaces is the visual information seeking Mantra: overview first, zoom and filter, then details on demand. But this is only a starting point in trying to understand the rich and varied set of information visualizations that have been proposed in recent years. The paper offers a task by data type taxonomy with seven data types (one, two, three dimensional data, temporal and multi dimensional data, and tree and network data) and seven tasks (overview, zoom, filter, details-on-demand, relate, history, and extracts)
BibTeX: @inproceedings{Shneiderman96EyesHaveIt_, author = {Ben Shneiderman}, title = {The Eyes Have It: A Task by Data Type Taxonomy for Information Visualizations}, booktitle = {VL '96: Proceedings of the 1996 IEEE Symposium on Visual Languages}, publisher = {IEEE Computer Society}, year = {1996}, pages = {336--343}, url = {http://ieeexplore.ieee.org/search/wrapper.jsp?arnumber=545307}, doi = {http://dx.doi.org/10.1109/VL.1996.545307} }
Adamic, L.A. & Glance, N.	The political blogosphere and the 2004 U.S. election: divided they blog [Abstract] [BibTeX]	2005	LinkKDD '05: Proceedings of the 3rd International Workshop on Link Discovery, pp. 36-43	inproceedings	DOI URL
Abstract: In this paper, we study the linking patterns and discussion topics of political bloggers. Our aim is to measure the degree of interaction between liberal and conservative blogs, and to uncover any differences in the structure of the two communities. Specifically, we analyze the posts of 40 "A-list" blogs over the period of two months preceding the U.S. Presidential Election of 2004, to study how often they referred to one another and to quantify the overlap in the topics they discussed, both within the liberal and conservative communities, and also across communities. We also study a single day snapshot of over 1,000 political blogs. This snapshot captures blogrolls (the list of links to other blogs frequently found in sidebars), and presents a more static picture of a broader blogosphere. Most significantly, we find differences in the behavior of liberal and conservative blogs, with conservative blogs linking to each other more frequently and in a denser pattern.
BibTeX: @inproceedings{Adamic05politicalblogosphereand, author = {Lada A. Adamic and Natalie Glance}, title = {The political blogosphere and the 2004 U.S. election: divided they blog}, booktitle = {LinkKDD '05: Proceedings of the 3rd International Workshop on Link Discovery}, publisher = {ACM}, year = {2005}, pages = {36--43}, url = {http://portal.acm.org/citation.cfm?doid=1134271.1134277}, doi = {http://doi.acm.org/10.1145/1134271.1134277} }
Fisher, D., Smith, M. & Welser, H.T.	You Are Who You Talk To: Detecting Roles in Usenet Newsgroups [Abstract] [BibTeX]	2006	HICSS '06: Proceedings of the 39th Annual Hawaii International Conference on System Sciences, pp. 59.2	inproceedings	DOI URL
Abstract: Understanding the social roles of the members a group can help to understand the social context of the group. We present a method of applying social network analysis to support the task of characterizing authors in Usenet newsgroups. We compute and visualize networks created by patterns of replies for each author in selected newsgroups and find that second-degree ego-centric networks give us clear distinctions between different types of authors and newsgroups. Results show that newsgroups vary in terms of the populations of participants and the roles that they play. Newsgroups can be characterized by populations that include question and answer newsgroups, conversational newsgroups, social support newsgroups, and flame newsgroups. This approach has applications for both researchers seeking to characterize different types of social cyberspaces as well as participants seeking to distinguish interaction partners and content authors.
BibTeX: @inproceedings{Fisher06YouAreWho, author = {Danyel Fisher and Marc Smith and Howard T. Welser}, title = {You Are Who You Talk To: Detecting Roles in Usenet Newsgroups}, booktitle = {HICSS '06: Proceedings of the 39th Annual Hawaii International Conference on System Sciences}, publisher = {IEEE Computer Society}, year = {2006}, pages = {59.2}, url = {http://ieeexplore.ieee.org/xpls/abs_all.jsp?arnumber=1579410}, doi = {http://dx.doi.org/10.1109/HICSS.2006.536} }
Welser, H.T., Gleave, E., Fisher, D. & Smith, M.	Visualizing the Signatures of Social Roles in Online Discussion Groups [Abstract] [BibTeX]	2007	The Journal of Social Structure Vol. 8(2)	article	URL
Abstract: Social roles in online discussion forums can be described by patterned characteristics of communication between network members which we conceive of as ‘structural signatures.' This paper uses visualization methods to reveal these structural signatures and regression analysis to confirm the relationship between these signatures and their associated roles in Usenet newsgroups. Our analysis focuses on distinguishing the signatures of one role from others, the role of “answer people." Answer people are individuals whose dominant behavior is to respond to questions posed by other users. We found that answer people predominantly contribute one or a few messages to discussions initiated by others, are disproportionately tied to relative isolates, have few intense ties and have few triangles in their local networks. OLS regression shows that these signatures are strongly correlated with role behavior and, in combination, provide a strongly predictive model for identifying role behavior (R2=.72). To conclude, we consider strategies for further improving the identification of role behavior in online discussion settings and consider how the development of a taxonomy of author types could be extended to a taxonomy of newsgroups in particular and discussion systems in general.
BibTeX: @article{Welser07VisualizingSignaturesof, author = {Howard T. Welser and Eric Gleave and Danyel Fisher and Marc Smith}, title = {Visualizing the Signatures of Social Roles in Online Discussion Groups}, journal = {The Journal of Social Structure}, year = {2007}, volume = {8}, number = {2}, url = {http://www.cmu.edu/joss/content/articles/volume8/Welser/} }
Smith, M., Shneiderman, B., Milic-Frayling, N., Rodrigues, E.M., Barash, V., Dunne, C., Capone, T., Perer, A. & Gleave, E.	Analyzing (Social Media) Networks with NodeXL [BibTeX]	2009	C&T '09: Proceedings of the Fourth International Conference on Communities and Technologies	inproceedings
BibTeX: @inproceedings{Smith09AnalyzingNetworkData, author = {Marc Smith and Ben Shneiderman and Natasa Milic-Frayling and Eduarda Mendes Rodrigues and Vladimir Barash and Cody Dunne and Tony Capone and Adam Perer and Eric Gleave}, title = {Analyzing (Social Media) Networks with NodeXL}, booktitle = {C&T '09: Proceedings of the Fourth International Conference on Communities and Technologies}, publisher = {Springer}, year = {2009} }

Created by JabRef on 01/02/2009.