Node overlap removal by growing a tree

Conference paper

Nachmanson, L., Nocaj, A., Bereg, S., Zhang, L. and Holroyd, A. 2016. Node overlap removal by growing a tree. GD16, 24th International Symposium on Graph Drawing & Network Visualization. Athens, Greece 19 - 21 Sep 2016 Springer. pp. 33-43 https://doi.org/10.1007/978-3-319-50106-2_3
TypeConference paper
TitleNode overlap removal by growing a tree
AuthorsNachmanson, L., Nocaj, A., Bereg, S., Zhang, L. and Holroyd, A.
Abstract

Node overlap removal is a necessary step in many scenarios including laying out a graph, or visualizing a tag cloud. Our contribution is a new overlap removal algorithm that iteratively builds a Minimum Spanning Tree on a Delaunay triangulation of the node centers and removes the node overlaps by ”growing” the tree. The algorithm is simple to implement yet produces high quality layouts. According to our experiments it runs several times faster than the current state-of-the-art methods.

ConferenceGD16, 24th International Symposium on Graph Drawing & Network Visualization
Page range33-43
ISSN0302-9743
ISBN
Hardcover9783319501055
PublisherSpringer
Publication dates
Online08 Dec 2016
Publication process dates
Deposited24 Oct 2016
Accepted25 Jul 2016
Output statusPublished
Accepted author manuscript
Copyright Statement

The final publication is available at Springer via http://doi.org/10.1007/978-3-319-50106-2_3

Additional information

Nachmanson L., Nocaj A., Bereg S., Zhang L., Holroyd A. (2016) Node Overlap Removal by Growing a Tree. In: Hu Y., Nöllenburg M. (eds) Graph Drawing and Network Visualization. GD 2016. Lecture Notes in Computer Science, vol 9801. Springer, Cham

Digital Object Identifier (DOI)https://doi.org/10.1007/978-3-319-50106-2_3
LanguageEnglish
Book titleGraph Drawing and Network Visualization: 24th International Symposium, GD 2016, Athens, Greece, September 19-21, 2016, Revised Selected Papers
Permalink -

https://repository.mdx.ac.uk/item/86qv3

Log in to edit

Download files

Accepted author manuscript
main (2).pdf

  • 20
    total views
  • 6
    total downloads
  • 4
    views this month
  • 1
    downloads this month

Export as

Related outputs

Automated identification of insight seeking behaviours, strategies and rules: a preliminary study
Hepenstal, S., Zhang, L. and Wong, B. 2021. Automated identification of insight seeking behaviours, strategies and rules: a preliminary study. SAGE Publications. https://doi.org/10.1177/1071181321651348
Developing conversational agents for use in criminal investigations
Hepenstal, S., Zhang, L., Kodagoda, N. and Wong, B. 2021. Developing conversational agents for use in criminal investigations. ACM Transactions on Interactive Intelligent Systems. 11 (3-4), pp. 1-35. https://doi.org/10.1145/3444369
Providing a foundation for interpretable autonomous agents through elicitation and modeling of criminal investigation pathways
Hepenstal, S., Zhang, L., Kodagoda, N. and Wong, B. 2020. Providing a foundation for interpretable autonomous agents through elicitation and modeling of criminal investigation pathways. Proceedings of the Human Factors and Ergonomics Society Annual Meeting. 64 (1), pp. 239-243. https://doi.org/10.1177/1071181320641057
Pan: conversational agent for criminal investigations
Hepenstal, S., Zhang, L., Kodagoda, N. and Wong, B. 2020. Pan: conversational agent for criminal investigations. IUI '20: 25th International Conference on Intelligent User Interfaces. Cagliari, Italy 17 - 20 Mar 2020 Association for Computing Machinery (ACM). pp. 134-135 https://doi.org/10.1145/3379336.3381463
Case-based reasoning of a deep learning network for prediction of early stage of oesophageal cancer
Gao, X., Braden, B., Zhang, L., Taylor, S., Pang, W. and Petridis, M. 2020. Case-based reasoning of a deep learning network for prediction of early stage of oesophageal cancer. 24th UK Symposium on Case-Based Reasoning (UKCBR 2019). Cambridge, UK 17 Dec 2019 BCS SGAI: The Specialist Group on Artificial Intelligence. pp. 1-12
How analysts think: a preliminary study of human needs and demands for AI-based conversational agents
Hepenstal, S., Wong, B., Zhang, L. and Kodagoda, N. 2019. How analysts think: a preliminary study of human needs and demands for AI-based conversational agents. SAGE Publications. https://doi.org/10.1177/1071181319631333
Algorithmic transparency of conversational agents
Hepenstal, S., Kodagoda, N., Zhang, L., Paudyal, P. and Wong, B. 2019. Algorithmic transparency of conversational agents. Trattner, C., Parra, D. and Riche, N. (ed.) IUI 2019 Workshop on Intelligent User Interfaces for Algorithmic Transparency in Emerging Technologies. Los Angeles, CA, USA 17 - 20 Mar 2019 CEUR Workshop Proceedings.
Towards an instrument for measuring sensemaking and an assessment of its theoretical features
Alsufiani, K., Attfield, S. and Zhang, L. 2018. Towards an instrument for measuring sensemaking and an assessment of its theoretical features. 4th International Conference on Emerging Research Paradigms in Business and Social Sciences. Dubai, UAE 16 - 18 Jan 2018
Making machine intelligence less scary for criminal analysts: reflections on designing a visual comparative case analysis tool
Jentner, W., Sacha, D., Stoffel, F., Ellis, G., Zhang, L. and Keim, D. 2018. Making machine intelligence less scary for criminal analysts: reflections on designing a visual comparative case analysis tool. The Visual Computer. 34 (9), pp. 1225-1241. https://doi.org/10.1007/s00371-018-1483-0
Evaluating interactive visualization of multidimensional data projection with feature transformation
Xu, K., Zhang, L., Pérez, D., Nguyen, P. and Ogilvie-Smith, A. 2017. Evaluating interactive visualization of multidimensional data projection with feature transformation. Multimodal Technologies and Interaction. 1 (3). https://doi.org/10.3390/mti1030013
Node overlap removal by growing a tree
Nachmanson, L., Nocaj, A., Bereg, S., Zhang, L. and Holroyd, A. 2017. Node overlap removal by growing a tree. Journal of Graph Algorithms and Applications. 21 (5), pp. 857-872. https://doi.org/10.7155/jgaa.00442
Towards an instrument for measuring sensemaking and an assessment of its theoretical features
Alsufiani, K., Attfield, S. and Zhang, L. 2017. Towards an instrument for measuring sensemaking and an assessment of its theoretical features. 31st International BCS Human Computer Interaction Conference (HCI 2017) - Digital Make-Believe. Sunderland, Tyne and Wear, UK. 03 - 06 Jul 2017 British Computer Society. pp. 1-5 https://doi.org/10.14236/ewic/HCI2017.86
Visual comparative case analytics
Sacha, D., Jentner, W., Zhang, L., Stoffel, F. and Ellis, G. 2017. Visual comparative case analytics. EuroVis Workshop on Visual Analytics. Barcelona, Spain 12 - 13 Jun 2017 The Eurographics Association. pp. 49-53 https://doi.org/10.2312/eurova.20171119
What you see is what you can change: Human-centred machine learning by interactive visualization
Sacha, D., Sedlmair, M., Zhang, L., Lee, J., Peltonen, J., Weiskopf, D., North, S. and Keim, D. 2017. What you see is what you can change: Human-centred machine learning by interactive visualization. Neurocomputing. 268, pp. 164-175. https://doi.org/10.1016/j.neucom.2017.01.105
Visual interaction with dimensionality reduction: a structured literature analysis
Sacha, D., Zhang, L., Sedlmair, M., Lee, J., Peltonen, J., Weiskopf, D., North, S. and Keim, D. 2017. Visual interaction with dimensionality reduction: a structured literature analysis. IEEE Transactions on Visualization and Computer Graphics. 23 (1), pp. 241-250. https://doi.org/10.1109/TVCG.2016.2598495
Spherical similarity explorer for comparative case analysis
Zhang, L., Rooney, C., Nachmanson, L., Wong, B., Kwon, B., Stoffel, F., Hund, M. and Qazi, N. 2016. Spherical similarity explorer for comparative case analysis. IS&T Electronic Imaging 2016 Conference on Visualization and Data Analysis 2016. San Francisco, CA, USA 16 - 18 Feb 2016 Society for Imaging Science and Technology. pp. 1-10 https://doi.org/10.2352/ISSN.2470-1173.2016.1.VDA-496
Human-centered machine learning through interactive visualization
Sacha, D., Sedlmair, M., Zhang, L., Lee, J., Weiskopf, D., North, S. and Keim, D. 2016. Human-centered machine learning through interactive visualization. 24th European Symposium on Artificial Neural Networks, Computational Intelligence and Machine Learning. Bruges, Belgium 27 - 29 Apr 2016 ESANN. pp. 641-646
Towards analytical provenance visualization for criminal intelligence analysis
Islam, J., Anslow, C., Xu, K., Wong, B. and Zhang, L. 2016. Towards analytical provenance visualization for criminal intelligence analysis. Computer Graphics & Visual Computing (CGVC) 2016. Bournemouth University, United Kingdom 15 - 16 Sep 2016 The Eurographics Association. pp. 17-24 https://doi.org/10.2312/cgvc.20161290
Interactive feature space extension for multidimensional data projection
Pérez, D., Zhang, L., Schaefer, M., Schreck, T., Keim, D. and Díaz, I. 2015. Interactive feature space extension for multidimensional data projection. Neurocomputing. 150 (Part B), pp. 611-626. https://doi.org/10.1016/j.neucom.2014.09.061
POLAR - an interactive patterns of life visualisation tool for intelligence analysis
Kodagoda, N., Attfield, S., Nguyen, P., Zhang, L., Xu, K., Wong, B., Wagstaff, A., Phillips, G., Bulloch, J., Marshall, J. and Bertram, S. 2014. POLAR - an interactive patterns of life visualisation tool for intelligence analysis. IEEE Joint Conference on Intelligence and Security Informatics Conference. The Hague, Netherlands Institute of Electrical and Electronics Engineers. pp. 327
VALCRI: addressing European needs for information exploitation of large complex data in criminal intelligence analysis
Wong, B., Zhang, L. and Shepherd, I. 2014. VALCRI: addressing European needs for information exploitation of large complex data in criminal intelligence analysis. European Data Forum 2014. Athens, Greece 19 - 20 Mar 2014
Wellformedness properties in Euler diagrams: which should be used?
Rodgers, P., Zhang, L. and Purchase, H. 2012. Wellformedness properties in Euler diagrams: which should be used? IEEE Transactions on Visualization and Computer Graphics. 18 (7), pp. 1089-1100. https://doi.org/10.1109/TVCG.2011.143
Inductively generating Euler diagrams
Stapleton, G., Rodgers, P., Howse, J. and Zhang, L. 2011. Inductively generating Euler diagrams. IEEE Transactions on Visualization and Computer Graphics. 17 (1), pp. 88-100. https://doi.org/10.1109/TVCG.2010.28
Drawing Euler diagrams with circles: the theory of piercings
Stapleton, G., Zhang, L., Howse, J. and Rodgers, P. 2011. Drawing Euler diagrams with circles: the theory of piercings. IEEE Transactions on Visualization and Computer Graphics. 17 (7), pp. 1020-1032. https://doi.org/10.1109/TVCG.2010.119
Euler graph transformations for Euler diagram layout
Rodgers, P., Stapleton, G., Howse, J. and Zhang, L. 2010. Euler graph transformations for Euler diagram layout. in: 2010 IEEE Symposium on Visual Languages and Human-Centric Computing Institute of Electrical and Electronics Engineers (IEEE). pp. 111-118