Drawing Clustered Graphs

The Future of Graph Drawing and a rhapsody Peter Eades 1 Question: What is the future of Graph Drawing? Answer: ... Ill tell you later ... But first: some constraints, and a brief history .... 2 Two different motivations for research Extrovert

I do research to make some impact on the world I want to solve problems posed by others I want to make the world a better place Introvert I do research because I really want to know the answer I am driven to uncover the truth I am driven by my personal curiosity Constraint: This talk is mostly aimed at extroverts

3 What is the relationship between extroverted research and the real world? extroverted research Research that is inspired by the real world Research that is useful for the real world Note: Fundamental research (theory) is usually inspired

by the real world 4 A brief history 5 1970s An idea emerges: Visualise graphs using a computer! Inspired by the need for better human decision making Implementations aimed at business decision making, circuit schematics, software diagrams, organisation charts, network protocols, and graph theory Some key ideas defined Aesthetic criteria defined (intuitively)

Key scientific challenge defined: layout to optimise aesthetic criteria 6 1980s Exciting algorithms and geometry: Many fundamental graph layout algorithms designed, enunciated, implemented, and analysed Extra inspirational ideas from graph theory, geometry, and algorithmics Planarity becomes a central concept 7 1990s

Maturity Graph Drawing matures as a discipline The Graph Drawing Conference begins The academic Graph Drawing community emerges More demand High data volumes increase demand for visualization Small companies appear More communities Information Visualization discipline appears 8 2000s Even more demand Data volumes become higher than ever imagined, and demand for visualization increases accordingly

New customers: systems biology, social networks, security, ... Better engineering More usable products, both free and commercial More companies started, older companies become stable Invisibility Graph drawing algorithms become invisible in vertical tool 9 Question: What is the future of Graph Drawing? Answer: ... Ill tell you later ... But first: A rhapsody: unsupported conjectures, subjective observations, outlandish claims, a few plain lies, and some open problems

10 Subjective Observation: Graph Drawing is successful 11 Graph Drawing is successful Algorithms for graph drawing are used in many industries: Biotechnology

Software engineering Networks Business intelligence Security Graph drawing software is an industry: Employs about 500 FTE people Market worth up to $100,000,000 per year About 100 FTE researchers Graph Drawing is scientifically significant Graph Drawing has provided

an elegant algorithmic approach to the centuries-old interplay between combinatorial and geometric structures GD2010 is a rank A conference Graph drawing papers appear in many top journals and conference proceedings 12 Graph Drawing is the big success story in information visualization Stephen North, September 2010

13 Subjective Observation: Graph Drawing is connected to many other disciplines 14 Keith Nesbitt 2003: use metro map metaphor for abstract data connections many applications large ABSTRACT DATA

HUMAN PERCEPTION multiattributed finding automated intelligent tools VIRTUAL ENVIRONMENT human S new user-interface perceptual tools technology

many interaction styles INFORMATION DISPLAY increase humancomputer bandwidth virtual real worlds SOFTWARE CASE ENGINEERING STUDY abstraction architectur e taxonomy iterative

prototyping finding trading rules visual data mining vision information visualisation quality principles

Data Mining MS-Taxonomy Information Display MS-Guidelines sensory bias sensory interaction Human Perception MS-Process

Software Engineering Case Study - Stock Market hearing haptics information sonification information haptisation spatial

metaphors virtual abstract worlds temporal metaphors guidelines information for perceptualisation information stock display market

data guidelines guidelines for structure MSTaxonomy MS-TAXONOMY guidelines for perception guidelines guidelines for spatial for direct metaphors metaphors process structure task analysis

design guidelines informatio n metaphors direct metaphors virtual hybrid worlds technical analysis

design process MSPROCESS physiology perceptual data mining Virtual Environments cognition patterns

DATA MINING Abstract Data data characterisatio n MS-GUIDELINES display mapping guidelines for temporal

metaphors mapping mapping mapping spatial direct temporal metaphors metaphors metaphors summativ e evaluation formative evaluation VE platform s

consider hardware platform consider software platform i-CONE Barco Baron Responsive Workbenc h Haptic Workbench WEDGE prototyping

expert heuristic evaluation evaluation 3D bar chart moving average surface bidAsk landscape haptic 3D bar chart haptic

moving average surface auditory bidAsk landscape 15 Info Vis Computer Graphics DataMining

GraphDrawing HCI Algorithms Computational Geometry Computer Science VisualLanguages Graph Drawing: Connections

CombinatorialGeometry GraphTheory Graphic Art LinearAlgebra 16 InfoVis Biology Security GraphDrawing

H D V is ta Da Computer Science Social Networks Finance ining M a t a D

17 Unsolved problem: make a really good metro map of graph drawing connections Based on real data Each metro line represents a community, as instantiated by a conference Each station joining different lines indicates that there are papers coauthored by people in different communities VisualLan guages Graph Drawing:

Connecti ons Algori thms Computa tional Geometr y H C I Data Minin

g GraphD rawing Inf o Vis Comp uter Graph ics $10+ CombinatorialG eometry

GraphTh eory Grap hicAr t LinearA lgebra 18 VisualLan guages Graph Drawing:

Connecti ons Algori thms Computa tional Geometr y H C I Data Minin

g GraphD rawing Inf o Vis Comp uter Graph ics Unsolved problem: Create algorithms and systems to draw (ordered) hypergraphs in the

metro-map metaphor. CombinatorialG eometry GraphTh eory Grap hicAr t LinearA lgebra 19 Outlandish claim:

Graph Drawing is dying 20 Interview with a Very Experienced Industry Researcher in a Telco, Sept 14, 2010 Interviewer: What are the most useful results from the Graph Drawing researchers in the last ten years? Industry Researcher: <60 seconds of silence> Scale! Those force directed algorithms run much faster now than they did around 2000, using the Koren/Quigley/Walshaw methods!

For force directed methods, visual complexity is now a problem . 21 Interview with a Very Experienced Industry Researcher in a Telco, Sept 14, 2010 Interviewer: Any other useful results from the Graph Drawing researchers in the last ten years? Industry Researcher: <60 seconds of silence> No

22 Interview with the CEO and CTO of a Graph Drawing software company, Sept 15, 2010 Interviewer: What are the most useful results from the Graph Drawing researchers in the last ten years? CTO:Fast force directed methods. When was that? Interviewer: Around GD2000, I think ... Almost 10 years ago. CTO:Yes. We implemented some of them. We had to fix them a bit, but they gave us much better runtimes. Interviewer: Any other useful results from the Graph Drawing researchers in the last ten years? Industry people: ....

CEO: I know one thing: nested drawings. This models the data better than previously. Interviewer: Anything else? 23 Interview with the CEO and CTO of a Graph Drawing software company, Sept 15, 2010 CEO: Well, our tools are much better engineered than ten years ago. Weve spent a lot of energy ... Interviewer: Yes, but I guess that kind of thing didnt come from the Graph Drawing research community? CEO: Oh, I guess not.

CIO: I dont think we have used any of the other results. They are certainly interesting, but ... 24 Data source: citeceer 25 100% 85% ings w a r d f o

Quality 50% Unsubstantiated claim: the quality of graph drawings isnt getting any better. 1980 1990 2000 2010 Data source: none 26

Open Problem: Is it worth the money? 27 Average cost of Graph Drawing Researcher per year (assuming $100Kpa, 2.5 oncost multiplier) = $250K. There are probably about 100 FTE GD researchers in the world. The cost of the past ten years of Graph Drawing Research is about $25M $250M $250M Open Problem: Has the world made a profit

from this $25M investment yet? If not, how long will it take to get some ROI? 28 100% 85% $250M Open Problem: Has the world made a profit from this $25M investment yet? If not, how long will it take to get some ROI?

1980 1990 2000 2010 29 Open Problem: What kind of community is GD? 30 The GD community

Every node is a paper at the GD conference Edge from A to B if A cites B 31 A high (academic) impact community Large indegree Influences other fields Fundamental area of research 32 An engineering community Large outdegree Uses many other fields to produce solutions for problems ?Perhaps has commercial impact? 33

An island community Not much connection to the outside ?Perhaps has no impact? ?Introspective community? 34 Unsolved problem Open $10+ Problem: What kind of community is GD? Has its character changed over time?

Can you show this in a picture (or a time-lapse animation) of citation network(s)? 35 Unsupported conjecture: Planarity has about 5 years to either live or die 36 1930s: Fary Theorem Straight-line drawings exist 1960s: Tuttes algorithm A straight-line drawing algorithm 1970s: Reads algorithm

Linear time straight-line drawing 1984: Tamassia algorithm Minimum number of bends 1987: Tamassia-Tollis algorithms Visibility drawing, upward planarity 1989: de Frassieux - Pach - Pollack Theorem Quadratic area straight-line drawing 37 Conversation at GD1994, between an academic delegate and a industry delegate Industry delegate: Why are you guys so obsessed with planarity? Most graphs that I want to draw arent planar. Academic delegate: Well, planarity is a central concept even for non-planar graphs. To be able to draw general

graphs, we find a topology with a small number of edge crossings, model this topology as a planar graph, and draw that planar graph. Industry delegate: Sounds good. But I dont know how to solve these sub-problems, for example, how to find a topology with a small number of crossings Academic delegate: These problems are fairly difficult and we dont have perfect solutions. But we expect a few more years of research and we will get good results Industry delegate: Sounds good ... I guess Im looking forward to it 38 Mid 1990s: Mutzels thesis Crossing reduction by integer linear programming 1995: Purchase experiments

Crossings really do inhibit understanding Late 1990s: Many beautiful papers on drawing planar graphs Good crossing reduction methods Early 2000s: Many more beautiful papers on drawing planar graphs e ru t ... ... ... t s o ... m

l A Plain lie: GD2010: More than 60% of papers are about planar graphs Subjective Observation: The graph drawing community is obsessed with planarity. 39 Interview with the CEO and CIO of a Graph Visualization company, Sept 15 2010 Interviewer: Do you use planar graph drawing

algorithms? CEO: No. Interviewer: Why not? CEO: Too much white space. Stability is a problem. Too difficult to integrate constraints. Incremental planar drawing doesnt work well. CIO: 40 Interview with a Very Senior Software Engineer in a Very Large Company that has a Very Small Section that produces visualization software, Sept 23 2010 Interviewer: Do your graph visualization tools use planar graph drawing algorithms? Software Engineer: Our customers want hierarchical layout first, and hierarchical layout second, and then

they want hierarchical layout. We also have spring algorithms, but Im not sure whether they use them. Interviewer: Yes, but maybe deep down in your software there is a planarity algorithm, or maybe a planar graph drawing algorithm? Software Engineer: No. No planarity. Note: Yworks does use planar graph drawing algorithms 41 Outlandish claim: Planarity-based methods are valuable, but need more time to prove themselves.

Unsupported conjecture: Around 2015, either: Yworks wins a much larger market share, based on the competitive advantage of planarity-based methods, or Yworks finds that planaritybased methods are not useful, and drops the idea. Subjective observation: To know whether planar graph drawing is worthwhile: We need to do lots more empirical work.

We probably dont need many more theorems. 42 Outlandish Claim: The graph drawing community can contribute a lot to solving the scale problem 43 1950 1960 1970

1980 1990 2000 44 Amo unt o store f data d elect ronic ally 350M 300M Social networks: Number of Facebook users

250M 200M 150M 100M 50M 0 04 05 06 07 08

09 45 The scale problem currently drives much of Computer Science Data sets are growing at a faster rate than the human ability to understand them. Businesses (and sciences) believe that their data sets contains useful information, and they want to get some business (or scientific) value out of these data sets. 46

For Graph Drawing, there are two facets of the scale problem: 1. Computational complexity Efficiency Runtime We need more efficient algorithms 2. Visual complexity Effectiveness Readability We need better ways to untangle large graphs 47 Graph Drawing has proposed three approaches to the scale problem: 1. Use 3D: spread the data over a third dimension

2. Use interaction: spread the data over time 3. Use clustering: view an abstraction of the data 48 Well supported claim: 3D is almost dead 49 Conversation between an Australian academic and a Canadian IBM research manager, 1992 IBM Research Manager: Graphics cards capable of fast 3D rendering will soon become commodity items. They will give an unprecedented ability to draw diagrams in 3D. This is completely new territory. Academic: What?

IBM Research Manager: Every PC will be able to do 3D. In IBM we do lots of graph drawing to model software. We think that 3D graph drawing will become commonplace. Academic: Really? IBM Research Manager: Theres more space in 3D, edge crossings can be avoided in 3D, navigation in 3D is natural. Academic: Really? IBM Research Manager: If you do a 3D graph drawing project, then IBM will fund it. Academic: Lets do it! 50 1980s 2D Theorem: Every planar graph with maximum degree 4 admits a 2D orthogonal drawing with no edge crossings and at most 4 bends per

edge. . P Eades, C Stirk, S Whitesides, The techniques of Komolgorov and Bardzin for three dimensional orthogonal graph drawings Information Processing Letters, 1996 A Papakostas, I Tollis, Incremental orthogonal graph drawing in three dimensions - Graph Drawing, 1997 - Springer P Eades, A Symvonis, S Whitesides, Three-dimensional orthogonal graph drawing algorithms, Discrete Applied Mathematics, 2000 DR Wood, Optimal three-dimensional orthogonal graph drawing in the general position model, Theoretical Computer Science, 2003 1996 3D Theorem: Every graph (even if it

is nonplanar) with maximum degree 6 admits a 3D orthogonal drawing with no edge crossings and a constant number of bends per edge. M Closson, S Gartshore, J Johansen, S Wismath, Fully dynamic 3-dimensional orthogonal graph drawing, Graph Drawing, 1999 TC Biedl, Heuristics for 3D-orthogonal graph drawings, Proc. 4th Twente Workshop on Graphs and , 1995 G Di Battista, M Patrignani, F Vargiu, A split&push approach to 3D orthogonal drawing, Graph Drawing, 1998 D Wood, An algorithm for three-dimensional orthogonal graph drawing, Graph Drawing, 1998 M Patrignani, F Vargiu, 3DCube: A tool for three dimensional graph drawing, Graph Drawing, 1997

51 Maurizio Patrignani 3D orthogonal drawing of K7 52 100% of y lit a Qu

gs n i w a r d 3D orthogonal graph drawing 50% 1980 1990 2000

2010 Data source: none 53 1990 2005: Many theorems on 3D Many metaphors Many research grants Many experiments A start-up company Mostly, 3D failed. 54 2004+: success with 2.5D?

Colin Ware: use 3D with a 2D attitude Tim Dwyer: use the third dimension for a single simple parameter (eg time) SeokHee Hong: Multiplane method 55 Tim Dwyer

56 Market movement use the third dimension for a single simple parameter Multiplane method 1. Partition the graph 2. Draw each part on a 2D manifold in 3D 3. Connect the parts with inter-manifold edges Motifs in a protein-protein interaction network Lanbo Zheng et al. 57

Joshua Ho 58 Multilevel visualization of clustered graphs (Feng, 1996) Draw the clusters on height i of the cluster tree on the plane z=i Draw on the plane z=2 Draw on the plane z=1 Draw on the plane z=0 The most cited paper in clustered graph drawing

59 Unsupported conjecture: There is some hope of life for 2.5D graph drawing Unsupported conjecture: There are many interesting algorithmic and geometric problems for graph drawing in the multiplane style. 60 Graph Drawing has proposed three approaches to the scale

problem: 1. Use 3D: spread the data over a third dimension 2. Use interaction: spread the data over time 3. Use clustering: view an abstraction of the data 61 The classical graph drawing pipeline Data analysis Graph visualization

Picture 62 In practice . . Many iterations Data analysis Graph visualization

Picture interaction Updates Action/decision the real worldAction/decision 63 Interaction flow 1. The human looks at key frame Fi. 2. The human thinks. 3. The human clicks on something. 4. System computes new key frame Fi+1. 5. System computes in-betweening animation from key frame F i

to key frame Fi+1. 6. System displays animated transition from Fi to Fi+1. 7. i++ 8. Go to 1. Outrageous claim: all graph drawing algorithms need to be designed with interaction flow in mind 64 Interaction can solve both problems: Computational complexity: The layout is only computed for the key frame (a relatively small graph) The user think time can be used for

computation Visual complexity: At any one time, only a small graph is on the screen 65 Interaction also raises some problems: Cognitive complexity: The user must remember stuff from one key frame to the next mental map problem Unsupported conjecture: Interaction flow poses many

interesting problems for graph drawing 66 Graph Drawing has proposed three approaches to the scale problem: 1. Use 3D: spread the data over a third dimension 2. Use interaction: spread the data over time 3. Use clustering: view an abstraction of the data 67 A clustered graph C=(G,T) consists of a classical graph G, and

a tree T such that the leaves of the tree T are the vertices of G. The tree T defines a clustering of the vertices of G. 68 Clustered graph drawing pipeline Data clustering Clustered Graph

visualization Picture 69 Clustered graph drawing pipeline More precisely:- Data Clustered Graph precis Picture

70 We can only draw a part of a huge graph at a time. What part shall we draw? A prcis: a graph formed from an antichain in the cluster tree. A prcis forms an abstraction of the data set. 71 Australia Qld Vic

JCU Bris UQ QUT Griffith Deakin Melb LaTrobe UNE Wlng UTS USyd

MU Monash NSW UNSW Sydney 72 A prcis is a graph, and can be drawn with the usual graph drawing algorithms JCU Brisbane Deakin

Melb UNE Sydney Wlng 73 Australia NSW UQ Bris

JCU UNSW UTS USyd UNE Wlng Deakin Sydney MU

Monash LaTrobe Melb Qld Griffith Vic QUT A prcis of a clustered graph

is a graph defined by an antichain in the cluster tree 74 Drill down The basic human interaction with a clustered graph is drill down: Open a node to see what it contains, that is, i.e, replace a node in the antichain with its children. Also, we need drill-up: Close a set of nodes to make the picture simpler i.e, replace a set of siblings in the antichain with their parent Note: In practical systems the human performs drill-down the system performs drill-up

75 Clustered graph drawing pipeline Data Clustered Graph precis Picture Drill down interaction Unsubstantiated

conjecture: Drill down/up are the only important interactions for large graphs. Outlandish claim: the Graph Drawing community can drive research into the algorithmics and combinatorial geometry of drill down/up interaction 76 Michael Wybrow 77 For interaction:

Drill down on node X changes the size of X Drill up should be performed by the system, not by the user Nodes must move to accommodate change in size of node X The new picture must be nice in the usual graph drawing sense The mental map must be preserved: Preserve orthogonal ordering Preserve proximity Partially supported Preserve topology conjecture: Graph drawing researchers can design algorithms to give good drill down/up interaction 78

Totally planar clustered graph drawing Say C is a clustered graph with cluster tree T=(V,E) and underlying graph G=(U,F). A drawing is a mapping p:VR2 (edges are straight lines). A drawing is totally planar if For every node u of T, all vertices inside the convex hull of the descendents of u are descendents of u. And every prcis is planar. 1 0

7 3 2 4 6 5 8 1 0 7 134

027 3 2 4 root 5 6 568 8 79

1 0 7 3 2 4 6 5 r a n a

pl 8 Root Drill down 134 027 568 80 1

0 7 3 2 4 6 5 8 1 134 027 Drill down 134

568 3 027 4 568 81 1 0 7 3 2

4 6 5 8 1 1 027 3 4 6 5

8 0 7 Drill down 027 3 2 4 6 5 8 82

Open problem: Does every cplanar graph have a totally planar drawing? Equivalently: Almost equivalently: Open problem: Does every cplanar graph have straight-line multilevel drawing in which: Every level is planar The projection of a ith-level vertex onto level i-1 lies within the convex hull of its children 83 Unsubstantiated claim: The only chance for a solution to

the scale problem for graph drawing lies in the algorithmics and geometry of interaction and clusters 84 Outrageous suggestion: Graph drawings are artworks 85 A personal timeline Early 1980s: I used intuition and introspection to evaluate graph drawings

Late 1980s: I read Shneidermans book Quality of an interface is a scientifically measurable function Task time, error rate, etc Now: I think graph drawings need to be beautiful as well as useful. Katy Borner, 2009: "In order to change behaviour, data graphics have to touch people intellectually and emotionally. 86 Visual Connections Sydney June 2008 87

88 89 90 91 92 Outlandish claim: Graph drawings researchers have the skills needed to create graph drawing art 93

George Birkoff, 1933: Beauty can be measured as a ratio M=O/C O = order ~= Kolmogorov complexity C = complexity ~= Shannon complexity Graph drawing problem as an optimization problem A number of objective functions f:DrawingsRealNumber Given a graph G, find a drawing p(G) that optimizes f 94 Unsupported conjecture: Using Birkoff-style functions, graph drawing algorithms can produce art.

95 Size of Star represents the amount of email Social circle Each person is a star Distance between two stars represents closeness 96 Currently:

Graph drawing aims for 100% information display, and 0% art Outlandish suggestion: Graph drawing should have a range of methods, aiming for x% information display and (100-x)% art, for all 0 <= x <= 100 97 + 0 1 $

Open problem: Use integer linear programming to produce valuable graph drawing art. 98 Open problem: Why do force directed methods work? 99 Force directed methods There have been many experiments A few more theorems would be good One theorem has been proved: If a graph has the right automorphisms, then there is a local minimum of a spring drawing that is symmetric. Some theory exists

Combinatorial rigidity theory Theory of multidimensional scaling But there are many questions that I dont know the answer Warning : this is i ntrospec tive rese arch! 100 Open problem: How many local minima are

there? Open problem: How close are Euclidean distances to the graph theoretic distances? Open problem: What is the time complexity of a spring algorithm? Open problem: Do force directed methods give bounded crossings most of the time?

101 This is the end of the rhapsody of unsupported conjectures, subjective observations, outlandish claims, a few plain lies, and open problems 102 Back to the main question: What is the future of Graph Drawing? Where does the road lead? 103 Where does the road lead?

104 105 106 107 ter Pe 108 Question: What is the future of Graph Drawing? ..... Sorry, Ive run out of time.

109 Question: What is the future of Graph Drawing? Answer: its up to you. 110 Many thanks 111

Recently Viewed Presentations

  • Count Objects to 100 Exemplification Find the following

    Count Objects to 100 Exemplification Find the following

    Complete the addition pyramids. ... Using the same values of ?, ?, ? and ?, write an algebraic expression that gives the values. 1 10 −10 55 ...
  • PowerPoint Presentation

    PowerPoint Presentation

    The E-Enterprise Leadership Council (EELC) will form an IPT to fully scope this project and clearly articulate the need. The scoping effort will identify ways in which states, tribes and EPA can work together, including in their interactions with each...
  • The - campbell.k12.ky.us

    The - campbell.k12.ky.us

    The United States had more or less successfully stayed out of the British/French conflicts from Washington's second administration until 1812 . The combined pressures of the new Western Congressmen and impatience with British naval policy finally tipped the balance in...
  • Implementation of the Joint Operations Plan

    Implementation of the Joint Operations Plan

    Joint Operations Plan (JOP) The JOP is an agreement between: Clackamas River Water (CRW) North Clackamas County Water Commission (NCCWC) South Fork Water Board (SFWB) Purpose: Effective and efficient use of the water resource for the benefit of all customers...
  • Psalm 32 - Simple Bible Studies

    Psalm 32 - Simple Bible Studies

    A Maskil "The last word of the title, "Maschil," is thought to mean that the psalm was intended for instruction, warning, or admonition; The word maschil, or rather maskil, being formed from askil, "to instruct" is taken from the first...
  • PhD -- Hints on Writing

    PhD -- Hints on Writing

    Good writing is hard work. But it does not require the intellectual abilities that you needed to get this far in your studies. Good writing requires skills. Anyone can learn most writing skills. Good writing requires practice. I am a...
  • 5 Ways AI Will Enable Recruiting to Be More Human, Not Less

    5 Ways AI Will Enable Recruiting to Be More Human, Not Less

    Virgin media realized it was doing this poorly. Now credits $7M revenue stream. Collaboration: how many of you can get your work done with out any interaction or support from the business? Even our most basic metrics as recruiters are...
  • Expansion Strategies Derek Schutz Director of Programs 2012

    Expansion Strategies Derek Schutz Director of Programs 2012

    Acquire laterals 6.4000000000000001E-2 6.9000000000000006E-2 0.109 0.27900000000000003 0.29499999999999998 0.68200000000000005 0.92300000000000004 Not Sure Consider being acquired Open new overseas office/s Merger of equals Open new US office/s Acquire law firm/s Acquire groups Acquire laterals 5.5E-2 2.3E-2 0.11799999999999999 0 ...