Algorithms for Graph Visualization Force-Directed Algorithms INSTITUT FU¨R THEORETISCHE INFORMATIK · FAKULTA¨T FU¨R INFORMATIK Tamara Mchedlidze 21.12.2016 1 DDrr.. TTaammaarraa MMcchheeddlliiddzzee ·· AAllggoorriitthhmmeenn zzuurr VViissuuaalliissiieerruunngg vvoonn GGrraapphheenn FFoorrccee--DDiirreecctteedd AAllggoorriitthhmmss Introduction Before: always based on some properties: tree, series-parallel graph, planar graph and on some additional information: ordering of the vertices, decompositions into SP-components Today: more direct and intuitive method based on physical analogies The methods are very popular: intuitiveness, easy to program, generality, fairly satisfactory results,... 2 Dr. Tamara Mchedlidze · Algorithmen zur Visualisierung von Graphen Force-Directed Algorithms General Layout Problem Given: Graph G = (V, E) Find: Clear and readable drawing of G Which aesthetic criteria would ? you optimize? 3 Dr. Tamara Mchedlidze · Algorithmen zur Visualisierung von Graphen Force-Directed Algorithms General Layout Problem Given: Graph G = (V, E) Find: Clear and readable drawing of G Criteria: adjacent nodes are close non-adjacent far apart edges short, straight-line, similar length densly connected parts (clusters) form communities as few crossings as possible nodes distributed evenly 3 Dr. Tamara Mchedlidze · Algorithmen zur Visualisierung von Graphen Force-Directed Algorithms General Layout Problem Given: Graph G = (V, E) Find: Clear and readable drawing of G Criteria: adjacent nodes are close non-adjacent far apart edges short, straight-line, similar length densly connected parts (clusters) form communities as few crossings as possible nodes distributed evenly ! Optimization criteria partially contradict each other 3 Dr. Tamara Mchedlidze · Algorithmen zur Visualisierung von Graphen Force-Directed Algorithms Example: Fixed edge-length Given: Graph G = (V, E), required edge length (cid:96)(e), ∀e ∈ E Find: Drawing of G which realizes all the edge lengths NP-hard for edge lengths {1, 2} [Saxe, ’80] planar drawing with unit edge length [Eades, Wormald, ’90] 4 Dr. Tamara Mchedlidze · Algorithmen zur Visualisierung von Graphen Force-Directed Algorithms Physical Model 5 Dr. Tamara Mchedlidze · Algorithmen zur Visualisierung von Graphen Force-Directed Algorithms Physical Model “To embed a graph we replace the vertices by steel rings and replace each edge with a spring to form a mechanical system . . . 5 Dr. Tamara Mchedlidze · Algorithmen zur Visualisierung von Graphen Force-Directed Algorithms Physical Model “To embed a graph we replace the vertices by steel rings and replace each edge with a spring to form a mechanical system . . . The vertices are placed in some initial layout and let go so that the spring forces on the rings move the system to a minimal energy state.” [Eades, ’84] 5 Dr. Tamara Mchedlidze · Algorithmen zur Visualisierung von Graphen Force-Directed Algorithms Physical Model “To embed a graph we replace the vertices by steel rings and replace each edge with a spring to form a mechanical system . . . The vertices are placed in some initial layout and let go so that the spring forces on the rings move the system to a minimal energy state.” [Eades, ’84] 5 Dr. Tamara Mchedlidze · Algorithmen zur Visualisierung von Graphen Force-Directed Algorithms