Seminars

NO.171 Trends and Perspectives for Graph Drawing and Network Visualization

Shonan Village Center

February 17 - 20, 2020 (Check-in: February 16, 2020 )

Organizers

  • Steven Chaplick
    • Universität Würzburg, Germany
  • Takayuki Itoh
    • Ochanomizu University, Japan
  • Giuseppe Liotta
    • University of Perugia, Italy
  • Kwan-Liu Ma
    • University of California – Davis, USA
  • Ignaz Rutter
    • Universität Passau, Germany

Overview

1 Introduction

Graph Drawing (GD) concerns geometric representations of graphs and networks and is motivated by applications requiring structural information to be visualized as graphs. This research area emerged as an independent discipline in the early 1990’s and is positioned at the intersection of different areas, such as graph algorithms, geometric computing, and interactive system design. The co-existence of combinatorial problems with questions from software engineering and experimental algorithmics within graph drawing makes it an extraordinary melting pot where theorists and practitioners can meet and share their knowledge. Indeed, the use of graph drawing approaches to present and visually analyze networked data sets has become a cornerstone in how information and knowledge is conveyed to users in many application domains such as social sciences, biological networks, software engineering, and forensic criminology.

The strong interaction of theory and practice within GD is reflected, for example, by the dual nature present within the proceedings of the main GD conference (the International Symposium of Graph Drawing and Network Visualization-:1), by the papers published by the flagship journal of the area (the Journal of Graph Algorithms and Applications), and by the many books and handbooks devoted to the subject. A prime example of this specialty of GD are the force-directed algorithms that are arguably among the most popular graph layout techniques in the information visualization community and that are also an endless source of deep mathematical questions. Namely, from the algorithmic point of view, the pioneering paper by Tutte [18], dating from the 1960’s and describing a simplified force-directed model for graph drawing, has motivated a sequence of papers on convex straight line planar drawings of graphs. From the system design point of view, visual analytics systems that use force-directed approaches are continuously evolving to handle the increasing complexity and size of the data.

This is an important time to reflect on Graph Drawing. Not only has there been a vast expansion in the variety of ways networks are visualized (e.g., node-link diagrams, treemaps, hybrid visualiza-tions, etc.), there has also been an explosion of the use of visual analytics as an essential ingredient in data science and information mining. These approaches are further being combined with new computational models arising from emerging architectural frameworks and infrastructures such as, for example, the streaming and the distributed models. Thus, we believe that it is essential to identify common research directions and consequently common language patterns for the increasing community that works on problems related to graph drawing and network visual analytics.

-:1 See graphdrawing.org for further information.

2 Aim and Topics of the Seminar

The idea of the seminar is to bring together active researchers from different areas of GD to identify relevant sub-fields and to phrase new key challenges. The envisioned outcome of the seminar is a unified forward-looking view of Graph Drawing to guide and inspire the research directions in the field for the coming decade and possibly beyond.

In the following we outline the primary high level topics currently focused on within the GD community, describe our expected outcomes of the seminar, explain how we intend to structure the seminar to achieve these outcomes, and relate our seminar to prior research meetings and conferences.

We feel that a concerted effort will be best suited to define and advance the current state and will lead to new fruitful goals for the entire community/area. We will discuss the emerging trends in GDNV starting from a core of fundamental research areas (briefly stated below). To this end we will coordinate several leading researchers to survey the aforementioned areas and inspire lively discussions. Our aims for the seminar are as follows.

• Bring together the most active researchers from the subareas of the field.
• Identify core challenges arising from ongoing research and real-world examples, e.g., regarding computational efficiency, visual complexity, and interaction.
• Examine extensibility and short-comings of the prior work to highlight particularly where new methods are needed. For example, to cope with accelerating growth in complexity and volume of networked data sets.
• Investigate limitations of the existing algorithmic techniques. Namely, regarding how to im-plement them as to best leverage distributed computing frameworks, e.g., could computing.

Graph Drawing and Network Visualization is at the intersection of three different disciplines, namely Graph Algorithms and Data Structures, Graph Combinatorics and Topology, and Visualization System Design. While many advances have been made within each discipline (where each has grown to have its own priorities and big open problems), a clear unified vision of the cross-disciplinary importance seems to be absent. Some of the areas covered include:

• Geometric Aspects of Drawings, e.g., the slope number of a graph or other parameters, such as the segment number, the obstacle number or the track number, see, e.g. [1, 9, 10, 12, 19].
• Topological Aspects of Drawings, e.g., planarity and (constrained) embeddings (see, e.g., [7, 16]). A recent trend here is beyond planarity where some crossings are allowed, see, e.g., [8, 13].
• Sets, Intersections, and Hypergraphs, e.g., in the context of set visualization, and visualization of dense graphs by geometric objects, see, e.g., [2, 14, 17, 3, 4, 5]).
• Network Visualization, e.g., the fundamental problems of laying out and interacting with a network. Here, e.g., issues of scale in dynamic networks are a key area [15], as well as visual analysis of streaming data, the development of incremental clustering and layout refinement
algorithms is in need [6, 11].
• Further considerations: many additional problems concern visualization of dynamically chang-ing data (i.e., how to best model changes? e.g., via morphing), as well as cognitive aspects (more user studies are needed), and practical aspects (more algorithm engineering is needed).


3 Relation to Other Seminars

The topic of the proposed seminar is quite related to several other past and upcoming seminars held in either Dagstuhl or Shonan, though none of these seminars, as listed below, was co-organized by applicants of the present proposal.

• Shonan No.54: Big Graph Drawing: Metrics and Methods (2015)
• Shonan No.85: Dynamic Networks Visual Analytics: Approaches to facilitate visual analysis of complex and dynamic network data (2016)
• Shonan No.89: Algorithmics for Beyond Planar Graphs (2016)
• Shonan No.106: Geometric Graphs: Theory and Applications (2017)
• Dagstuhl 17332: Scalable Set Visualizations (2017)
• Shonan No.127: Reimagining the Mental Map and Drawing Stability (2018)
• Dagstuhl 18482: Network Visualization in the Humanities (2018)
• Dagstuhl 19092: Beyond-Planar Graphs: Combinatorics, Models and Algorithms (2019)

The key difference is that each of these is concerned with one specific aspect of the research field. Moreover, structurally, most of these seminars focus on specific research questions and seek to make progress on these. As such, these seminars often produce contributions in the form of publications. While these may also lead to follow-up questions that partly shape the future research in the respective area, it is a by product rather than a conscious process. In contrast, we propose a seminar with a broader horizon, whose main contribution should be posing key questions, open problems, and long-term mission statements for several subfields of Graph Drawing that will help shape the research in these areas for an extended period.
The authors of this proposal previously organized three seminars. The first two seminars focused on immersive analytics which provides immersive system frameworks and environments for inter-active and explorative data understanding and knowledge discovery. The third seminar addressed academic and industrial questions on visualization system software. Graph drawing and network visualization are important components of immersive analytics and visualization software packages; therefore, the scope of our proposed seminar will engage and impact such communities.

• Shonan No.74: Immersive Analytics: A new multidisciplinary initiative to explore future in-teraction technologies for data analytics (2016)
• Shonan No.131: Immersive Analytics for Network and Trail Sets Data Analysis (2018)
• Shonan No.145: The Moving Target of Visualization Software for an Ever More Complex World (2019)

References

[1] H. Alpert, C. Koch, and J. D. Laison. Obstacle numbers of graphs. Discrete & Computational Geometry, 44(1):223–244, Jul 2010.
[2] T. C. Biedl, G. Liotta, and F. Montecchiani. Embedding-preserving rectangle visibility repre-sentations of nonplanar graphs. Discrete & Computational Geometry, 60(2):345–380, 2018.
[3] U. Brandes, S. Cornelsen, B. Pampel, and A. Sallaberry. Blocks of hypergraphs - applied to hypergraphs and outerplanarity. In C. S. Iliopoulos and W. F. Smyth, editors, Combinato-rial Algorithms - 21st International Workshop, IWOCA 2010, London, UK, July 26-28, 2010, Revised Selected Papers, volume 6460 of Lecture Notes in Computer Science, pages 201–211. Springer, 2010.
[4] K. Buchin, M. J. van Kreveld, H. Meijer, B. Speckmann, and K. Verbeek. On planar supports for hypergraphs. J. Graph Algorithms Appl., 15(4):533–549, 2011.
[5] T. Castermans, M. van Garderen, W. Meulemans, M. Nöllenburg, and X. Yuan. Short plane supports for spatial hypergraphs. CoRR, abs/1808.09729, 2018.
[6] T. Crnovrsanin, J. Chu, and K.-L. Ma. An incremental layout method for visualizing online dynamic graphs. Journal of Graph Algorithms and Applications, 21(1):55–80, 2017.
[7] G. Da Lozzo, G. Di Battista, F. Frati, and M. Patrignani. Computing nodetrix representations of clustered graphs. J. Graph Algorithms Appl., 22(2):139–176, 2018.
[8] W. Didimo, G. Liotta, and F. Montecchiani. A survey on graph drawing beyond planarity. CoRR, abs/1804.07257, 2018.
[9] V. Dujmovic, D. Eppstein, M. Suderman, and D. R. Wood. Drawings of planar graphs with few slopes and segments. Comput. Geom., 38(3):194–212, 2007.
[10] V. Dujmovic and D. R. Wood. Stacks, queues and tracks: Layouts of graph subdivisions. Discrete Mathematics & Theoretical Computer Science, 7(1):155–202, 2005.
[11] T. Itoh, K. Klein, and G. Liotta. Dynamic networks visual analytics: Approaches to facilitate visual analysis of complex and dynamic network data, 2016. NII Shonan Meeting Report.
[12] B. Keszegh, J. Pach, and D. Pálvölgyi. Drawing planar graphs of bounded degree with few slopes. SIAM J. Discrete Math., 27(2):1171–1183, 2013.
[13] S. G. Kobourov, G. Liotta, and F. Montecchiani. An annotated bibliography on 1-planarity. Computer Science Review, 25:49–67, 2017.
[14] J. Kratochvíl and Z. Tuza. Intersection dimensions of graph classes. Graphs and Combinatorics, 10(2-4):159–168, 1994.
[15] K.-L. Ma and C. Muelder. Large-scale graph visualization and analytics. IEEE Computer, 46(7):39–46, 2013.
[16] R. Tamassia, editor. Handbook on Graph Drawing and Visualization. Chapman and Hall/CRC, 2013.
[17] R. Tamassia and I. G. Tollis. A unified approach a visibility representation of planar graphs. Discrete & Computational Geometry, 1:321–341, 1986.
[18] W. T. Tutte. How to draw a graph. Proceedings of the London Mathematical Society, s3-13(1):743–767, 1963.
[19] G. A. Wade and J.-H. Chu. Drawability of complete graphs using a minimal slope set. The Computer Journal, 37(2):139–142, 1994.