Transcription
Algorithms for Graph VisualizationForce-Directed AlgorithmsINSTITUT FÜR THEORETISCHE INFORMATIK · FAKULTÄT FÜR INFORMATIKTamara Mchedlidze21.12.20161Dr. Tamara Mchedlidze · Algorithmen zur Visualisierung von GraphenForce-Directed Algorithms
IntroductionBefore: always based on some properties: tree,series-parallel graph, planar graphand on some additional information: ordering of thevertices, decompositions into SP-componentsToday: more direct and intuitive method based on physicalanalogiesThe methods are very popular: intuitiveness, easy toprogram, generality, fairly satisfactory results,.2Dr. Tamara Mchedlidze · Algorithmen zur Visualisierung von GraphenForce-Directed Algorithms
General Layout ProblemGiven: Graph G (V, E)Find: Clear and readable drawing of G?3Which aesthetic criteria wouldyou optimize?Dr. Tamara Mchedlidze · Algorithmen zur Visualisierung von GraphenForce-Directed Algorithms
General Layout ProblemGiven: Graph G (V, E)Find: Clear and readable drawing of GCriteria:adjacent nodes are closenon-adjacent far apartedges short, straight-line, similar lengthdensly connected parts (clusters) form communitiesas few crossings as possiblenodes distributed evenly3Dr. Tamara Mchedlidze · Algorithmen zur Visualisierung von GraphenForce-Directed Algorithms
General Layout ProblemGiven: Graph G (V, E)Find: Clear and readable drawing of GCriteria:adjacent nodes are closenon-adjacent far apartedges short, straight-line, similar lengthdensly connected parts (clusters) form communitiesas few crossings as possiblenodes distributed evenly!3Optimization criteria partially contradict each otherDr. Tamara Mchedlidze · Algorithmen zur Visualisierung von GraphenForce-Directed Algorithms
Example: Fixed edge-lengthGiven: Graph G (V, E), required edge length (e), e EFind: Drawing of G which realizes all the edge lengthsNP-hard foredge lengths {1, 2}[Saxe, ’80]planar drawing with unit edge length [Eades, Wormald, ’90]4Dr. Tamara Mchedlidze · Algorithmen zur Visualisierung von GraphenForce-Directed Algorithms
Physical Model5Dr. Tamara Mchedlidze · Algorithmen zur Visualisierung von GraphenForce-Directed Algorithms
Physical Model“To embed a graph we replace the vertices by steel rings and replaceeach edge with a spring to form a mechanical system . . .5Dr. Tamara Mchedlidze · Algorithmen zur Visualisierung von GraphenForce-Directed Algorithms
Physical Model“To embed a graph we replace the vertices by steel rings and replaceeach edge with a spring to form a mechanical system . . . The vertices areplaced in some initial layout and let go so that the spring forces on therings move the system to a minimal energy state.” [Eades, ’84]5Dr. Tamara Mchedlidze · Algorithmen zur Visualisierung von GraphenForce-Directed Algorithms
Physical Model“To embed a graph we replace the vertices by steel rings and replaceeach edge with a spring to form a mechanical system . . . The vertices areplaced in some initial layout and let go so that the spring forces on therings move the system to a minimal energy state.” [Eades, ’84]5Dr. Tamara Mchedlidze · Algorithmen zur Visualisierung von GraphenForce-Directed Algorithms
Physical ModelSo-called spring-embedder algorithms that workaccordingto thisor similarprinciplesare ringsamong“To embeda graphwe replacethe verticesby steeland thereplaceeach mostedge witha spring usedto forma mechanical system. . . Thefrequentlygraph-drawingmethodsin vertices areplacedin some initial layout and let go so that the spring forces on thepractice.rings move the system to a minimal energy state.” [Eades, ’84]5Dr. Tamara Mchedlidze · Algorithmen zur Visualisierung von GraphenForce-Directed Algorithms
Notation (e)pv (xv , yv ) pu pv p pu v6ideal spring length for edge eposition of node vEuclidean distance between u and vunit vector pointing from u to vDr. Tamara Mchedlidze · Algorithmen zur Visualisierung von GraphenForce-Directed Algorithms
Spring-Embedder(Eades, 1984)Model:repulsive force between two non-adjacent nodes u and vcrep frep (pu , pv ) ·pu pv2 pv pu 7Dr. Tamara Mchedlidze · Algorithmen zur Visualisierung von GraphenForce-Directed Algorithms
Spring-Embedder(Eades, 1984)Model:repulsive force between two non-adjacent nodes u and vcrep frep (pu , pv ) ·pu pv2 pv pu attractive force between adjacent vertices u and v pu pv fspring (pu , pv ) cspring · log· pv pu 7Dr. Tamara Mchedlidze · Algorithmen zur Visualisierung von GraphenForce-Directed Algorithms
Spring-Embedder(Eades, 1984)Model:repulsive force between two non-adjacent nodes u and vcrep frep (pu , pv ) ·pu pv2 pv pu attractive force between adjacent vertices u and v pu pv fspring (pu , pv ) cspring · log· pv pu resulting displacement vector for node vXXFv frep (pu , pv ) u:{u,v}6 E7Dr. Tamara Mchedlidze · Algorithmen zur Visualisierung von Graphenfspring (pu , pv )u:{u,v} EForce-Directed Algorithms
Diagram of Spring-Embedder Forces(Eades, 1984)ForceAttractivefspringDistanceRepulsivel8frep (pu , pv ) frepcrep pv pu 2 · p u pvfspring (pu , pv ) cspring · logDr. Tamara Mchedlidze · Algorithmen zur Visualisierung von Graphen pu pv · p pv uForce-Directed Algorithms
Algorithm Spring-Embedder(Eades, 1984)Input: G (V, E) connected undirected graph with initialplacement p (pv )v V , number of interationsK N, threshold ε 0, constant δ 0Output: Layout p with ”low internal stress“t 1while t K and maxv V kFv (t)k ε doforeach v PV doFv (t) u:{u,v}6 E frep (pu , pv ) PFv (t) u:{u,v} E fspring (pu , pv )foreach v V dopv pv δ · Fv (t)t t 19Dr. Tamara Mchedlidze · Algorithmen zur Visualisierung von GraphenForce-Directed Algorithms
Algorithm Spring-Embedder(Eades, 1984)Input: G (V, E) connected undirected graph with initialplacement p (pv )v V , number of interationsK N, threshold ε 0, constant δ 0Output: Layout p with ”low internal stress“t 1while t K and maxv V kFv (t)k ε doforeach v PV doFv (t) u:{u,v}6 E frep (pu , pv ) PFv (t) u:{u,v} E fspring (pu , pv )foreach v V dopv pv δ · Fv (t)Demot t 19Dr. Tamara Mchedlidze · Algorithmen zur Visualisierung von GraphenForce-Directed Algorithms
Algorithm Spring-Embedder(Eades, 1984)Input: G (V, E) connected undirected graph with initialplacement p (pv )v V , number of interatiosK N, threshold ε 0, constant δ 0δ(t)Output: Layout p with ”low internal stress“Cooling of thescaling factor δt 1while t K and maxv V kFv (t)k ε doforeach v PV doFv (t) u:{u,v}6 E frep (pu , pv ) PFv (t) u:{u,v} E fspring (pu , pv )tforeach v V dopv pv δ(t) · Fv (t)t t 19Dr. Tamara Mchedlidze · Algorithmen zur Visualisierung von GraphenForce-Directed Algorithms
DiscussionAdvantagesvery simple Algorithmgood results for small and medium-sized graphsemphirically good representation of symmetry and structure10Dr. Tamara Mchedlidze · Algorithmen zur Visualisierung von GraphenForce-Directed Algorithms
DiscussionAdvantagesvery simple Algorithmgood results for small and medium-sized graphsemphirically good representation of symmetry and structureDisadvantagessystem is not stable at the endconverging to local minimatimewise fspring in O( E ) and frep in O( V 2 )10Dr. Tamara Mchedlidze · Algorithmen zur Visualisierung von GraphenForce-Directed Algorithms
DiscussionAdvantagesvery simple Algorithmgood results for small and medium-sized graphsemphirically good representation of symmetry and structureDisadvantagessystem is not stable at the endconverging to local minimatimewise fspring in O( E ) and frep in O( V 2 )InfluenceOriginal paper by Peter Eades got 1600 citations (400 inthe past two years)Basis for many further ideas10Dr. Tamara Mchedlidze · Algorithmen zur Visualisierung von GraphenForce-Directed Algorithms
Variant: Fruchterman & Reingold(1991)Model:repulsive force between all node pairs u and v 2 frep (pu , pv ) · p u pv pv pu 11Dr. Tamara Mchedlidze · Algorithmen zur Visualisierung von GraphenForce-Directed Algorithms
Variant: Fruchterman & Reingold(1991)Model:repulsive force between all node pairs u and v 2 frep (pu , pv ) · p u pv pv pu attractive force between two adjacent nodes u and v pu pv 2 fattr (pu , pv ) · pv pu 11Dr. Tamara Mchedlidze · Algorithmen zur Visualisierung von GraphenForce-Directed Algorithms
Variant: Fruchterman & Reingold(1991)Model:repulsive force between all node pairs u and v 2 frep (pu , pv ) · p u pv pv pu attractive force between two adjacent nodes u and v pu pv 2 fattr (pu , pv ) · pv pu resulting force between adjacent nodes u and vfspring (pu , pv ) frep (pu , pv ) fattr (pu , pv )11Dr. Tamara Mchedlidze · Algorithmen zur Visualisierung von GraphenForce-Directed Algorithms
Diagramm of Fruchtermann & Reingold lfrep · p u pvfrep (pu , pv ) 2 pv pu fattr (pu , pv ) pu pv 2 · p pv ufspring (pu , pv ) frep (pu , pv ) fattr (pu , pv )12Dr. Tamara Mchedlidze · Algorithmen zur Visualisierung von GraphenForce-Directed Algorithms
Diagramm of Fruchtermann & Reingold lsiveDemo · p u pvfrep (pu , pv ) 2 pv pu fattr (pu , pv ) pu pv 2 · p pv ufspring (pu , pv ) frep (pu , pv ) fattr (pu , pv )12Dr. Tamara Mchedlidze · Algorithmen zur Visualisierung von GraphenForce-Directed Algorithms
Other Possible ModificationsInertiaGravitationMagnetic forces13Dr. Tamara Mchedlidze · Algorithmen zur Visualisierung von GraphenForce-Directed Algorithms
Other Possible ModificationsInertiadefine node mass as Φ(v) 1 deg(v)/2set fattr (pu , pv ) fattr (pu , pv ) · 1/Φ(v)GravitationMagnetic forces13Dr. Tamara Mchedlidze · Algorithmen zur Visualisierung von GraphenForce-Directed Algorithms
Other Possible ModificationsInertiadefine node mass as Φ(v) 1 deg(v)/2set fattr (pu , pv ) fattr (pu , pv ) · 1/Φ(v)GravitationPdefine barycenter pbary 1/ V · v V pv fgrav (pv ) cgrav · Φ(v) · p pv baryMagnetic forces13Dr. Tamara Mchedlidze · Algorithmen zur Visualisierung von GraphenForce-Directed Algorithms
Other Possible ModificationsInertiadefine node mass as Φ(v) 1 deg(v)/2set fattr (pu , pv ) fattr (pu , pv ) · 1/Φ(v)GravitationPdefine barycenter pbary 1/ V · v V pv fgrav (pv ) cgrav · Φ(v) · p pv baryMagnetic forces– define magnetic fields (e.g. vertical, horizontal)– angle θ between edge and the direction of the field– define force that reduces this angleθ13Dr. Tamara Mchedlidze · Algorithmen zur Visualisierung von GraphenForce-Directed Algorithms
Bounded Drawing AreaFvRIf forceFv drives out of R, we adapt the vectorappropriately within R.14Dr. Tamara Mchedlidze · Algorithmen zur Visualisierung von GraphenForce-Directed Algorithms
Bounded Drawing AreaFvRIf forceFv drives out of R, we adapt the vectorappropriately within R.14Dr. Tamara Mchedlidze · Algorithmen zur Visualisierung von GraphenForce-Directed Algorithms
Bounded Drawing AreaFvRIf forceFv drives out of R, we adapt the vectorappropriately within R.14Dr. Tamara Mchedlidze · Algorithmen zur Visualisierung von GraphenForce-Directed Algorithms
Adaptive Displacement(Frick, Ludwig, Mehldau 1995)store previous displacementvector Fv (t 1)Fv (t 1)v15Dr. Tamara Mchedlidze · Algorithmen zur Visualisierung von GraphenForce-Directed Algorithms
Adaptive Displacement(Frick, Ludwig, Mehldau 1995)store previous displacementvector Fv (t 1)Fv (t)Fv (t 1) local temperaturev15αv (t)Dr. Tamara Mchedlidze · Algorithmen zur Visualisierung von Graphencos(αv (t)) 1:similar direction increase the temperatureForce-Directed Algorithms
Adaptive Displacement(Frick, Ludwig, Mehldau 1995)store previous displacementvector Fv (t 1)Fv (t 1) local temperatureαv (t)vcos(αv (t)) 1:similar direction increase the temperaturecos(αv (t)) 1:oscillation reduce the temperatureFv (t)15Dr. Tamara Mchedlidze · Algorithmen zur Visualisierung von GraphenForce-Directed Algorithms
Adaptive Displacement(Frick, Ludwig, Mehldau 1995)store previous displacementvector Fv (t 1)Fv (t 1) local temperatureFv0 (t)vαv (t)15Fv (t)Dr. Tamara Mchedlidze · Algorithmen zur Visualisierung von Graphencos(αv (t)) 1:similar direction increase the temperaturecos(αv (t)) 1:oscillation reduce the temperaturecos(αv (t)) 0:Rotation update rotation counter anddecrease temperature ifnecessaryForce-Directed Algorithms
DiscussionAdvantagesstill very simple algorithmfurther modifications improve layout quality and lead tofaster convergence16Dr. Tamara Mchedlidze · Algorithmen zur Visualisierung von GraphenForce-Directed Algorithms
DiscussionAdvantagesstill very simple algorithmfurther modifications improve layout quality and lead tofaster convergenceDisadvantagesstability is not guaranteedlocal minima possiblequadratic time for repulsive forces16Dr. Tamara Mchedlidze · Algorithmen zur Visualisierung von GraphenForce-Directed Algorithms
DiscussionAdvantagesstill very simple algorithmfurther modifications improve layout quality and lead tofaster convergenceDisadvantagesstability is not guaranteedlocal minima possiblequadratic time for repulsive forcesInfluenceVariants of Fruchterman and Reingold algorithms areprobably the most popular force-based methods (originalpaper cited 3500 times (1000 in the past two years))16Dr. Tamara Mchedlidze · Algorithmen zur Visualisierung von GraphenForce-Directed Algorithms
DiscussionAdvantagesstill very simple algorithmfurther modifications improve layout quality and lead tofaster convergenceDisadvantagesstability is not guaranteedCould we reduce this?local minima possiblequadratic time for repulsive forcesInfluenceVariants of Fruchterman and Reingold algorithms areprobably the most popular force-based methods (originalpaper cited 3500 times (1000 in the past two years))16Dr. Tamara Mchedlidze · Algorithmen zur Visualisierung von GraphenForce-Directed Algorithms
Grid Version(Fruchterman, Reingold, 1990)v17Dr. Tamara Mchedlidze · Algorithmen zur Visualisierung von GraphenForce-Directed Algorithms
Grid Version(Fruchterman, Reingold, 1990)v17Dr. Tamara Mchedlidze · Algorithmen zur Visualisierung von GraphenForce-Directed Algorithms
Grid Version(Fruchterman, Reingold, 1990)subdivide plane by a girdv17Dr. Tamara Mchedlidze · Algorithmen zur Visualisierung von GraphenForce-Directed Algorithms
Grid Version(Fruchterman, Reingold, 1990)subdivide plane by a girdcompute repulsive forcesonly for the nodes in theneighbouring cellsv17Dr. Tamara Mchedlidze · Algorithmen zur Visualisierung von GraphenForce-Directed Algorithms
Grid Version(Fruchterman, Reingold, 1990)subdivide plane by a girdv17Dr. Tamara Mchedlidze · Algorithmen zur Visualisierung von Graphencompute repulsive forcesonly for the nodes in theneighbouring cellsand only when thedistance is at most dmaxForce-Directed Algorithms
Grid Version(Fruchterman, Reingold, 1990)subdivide plane by a girdvcompute repulsive forcesonly for the nodes in theneighbouring cellsand only when thedistance is at most dmaxDiscussionmeaningful idea toimprove runtimeworst-case no advantageQuality loss (e.g.,oscillation dmax )17Dr. Tamara Mchedlidze · Algorithmen zur Visualisierung von GraphenForce-Directed Algorithms
Quad-TreeR018Dr. Tamara Mchedlidze · Algorithmen zur Visualisierung von Graphenr0QTForce-Directed Algorithms
Quad-TreeR1R2r0r1R318Dr. Tamara Mchedlidze · Algorithmen zur Visualisierung von GraphenQTr2r3r4R4Force-Directed Algorithms
Quad-TreeR7r0R5R8QTr1R9r5r2r3r4r12R6R10R11R1218Dr. Tamara Mchedlidze · Algorithmen zur Visualisierung von GraphenForce-Directed Algorithms
Quad-TreeR13r0R14r1R15r5R16r1318QTDr. Tamara Mchedlidze · Algorithmen zur Visualisierung von Graphenr2r6r3r4r12r16Force-Directed Algorithms
Quad-TreeQTr0r1r5R17r2r6r13r3r4r12r16R18r1718Dr. Tamara Mchedlidze · Algorithmen zur Visualisierung von Graphenr18Force-Directed Algorithms
Properties of Quad-Treeinitheight h log dsmin 23 , here dmin -smallest distancetime and space O(hn)compressed quad-tree in O(n log n) timer0r1r5r6r13sinit19Dr. Tamara Mchedlidze · Algorithmen zur Visualisierung von Graphenr2r3r4r12r16r17r18Force-Directed Algorithms
Forces with Quad-Trees(Barnes, Hut, 1986)QTr0r1ur5r13r2r6ur1720Dr. Tamara Mchedlidze · Algorithmen zur Visualisierung von Graphenr3r4r12r16r18Force-Directed Algorithms
Forces with Quad-Trees(Barnes, Hut, . Tamara Mchedlidze · Algorithmen zur Visualisierung von GraphenForce-Directed Algorithms
Forces with Quad-Trees(Barnes, Hut, 1986)σR5r0r1ur5r13r2r6ur1720QTDr. Tamara Mchedlidze · Algorithmen zur Visualisierung von Graphenr3r4r12r16r18Force-Directed Algorithms
Forces with Quad-Trees(Barnes, Hut, 1986)QTr0r1ur5r2r6r3r4r12σR16r13ur1720Dr. Tamara Mchedlidze · Algorithmen zur Visualisierung von Graphenr16r18Force-Directed Algorithms
Multilevel-Algorithms for Large GraphsMotivationclassical Spring-Embedder for large graphs are too slowscensitivity to random initialization of node positions21Dr. Tamara Mchedlidze · Algorithmen zur Visualisierung von GraphenForce-Directed Algorithms
Multilevel-Algorithms for Large GraphsMotivationclassical Spring-Embedder for large graphs are too slowscensitivity to random initialization of node positionsGRIP – Graph dRawing with Intelligent Placement(Gajer, Kobourov, 2004)Approachtop-down graph coarsening/filtrationbottom-up calculation of the layout:clever placement of new nodesforce-based refinement of their positions21Dr. Tamara Mchedlidze · Algorithmen zur Visualisierung von GraphenForce-Directed Algorithms
GRIP AlgorithmInput: Graph G (V, E)V Filtering V V0 V1 · · · Vkfor i k to 0 doforeach v Vi \ Vi 1 docompute neighbours of vcompute initial position of vfor j 1 to rounds doforeach v Vi doforce-based relaxation22Dr. Tamara Mchedlidze · Algorithmen zur Visualisierung von GraphenForce-Directed Algorithms
MIS-filteringMaximal Independent Set (MIS) filteringsequence of node sets V V0 V1 · · · Vk Vi is (inclusion-) maximal set of nodes, so thatdistance in G between nodes in Vi is 2i 1 1good balance betwen size of a level and depth ofdecompositon23Dr. Tamara Mchedlidze · Algorithmen zur Visualisierung von GraphenForce-Directed Algorithms
Computing MIS-FilteringAlgorithmincremental procedure: given Vi compute Vi 1select random element v in Viremove all elements from Vi with distance 2i to vuse BFS from v with search depth 2iuntil no further node remains in Vi24Dr. Tamara Mchedlidze · Algorithmen zur Visualisierung von GraphenForce-Directed Algorithms
Computing MIS-FilteringAlgorithmincremental procedure: given Vi compute Vi 1select random element v in Viremove all elements from Vi with distance 2i to vuse BFS from v with search depth 2iuntil no further node remains in ViDepth of Filtrationfor the last level k it holds that 2k diam(G)therefore the depth is O(log diam(G))24Dr. Tamara Mchedlidze · Algorithmen zur Visualisierung von GraphenForce-Directed Algorithms
Computing MIS-FilteringAlgorithmincremental procedure: given Vi compute Vi 1select random element v in Viremove all elements from Vi with distance 2i to vuse BFS from v with search depth 2iuntil no further node remains in ViDepth of Filtrationfor the last level k it holds that 2k diam(G)therefore the depth is O(log diam(G))Alternativecoarsening with contracting matchings: end vertices of each(Walshaw, JGAA 2003)matching edge are contracted24Dr. Tamara Mchedlidze · Algorithmen zur Visualisierung von GraphenForce-Directed Algorithms
Level-based Node PlacementStep 1for each node v Vi \ Vi 1 find optimal position withrespect to three adjacent nodes Vi 1Step 2perform force-based refinement, where forces are computedlocally only to a constant number of nearest neighbors in Vi25Dr. Tamara Mchedlidze · Algorithmen zur Visualisierung von GraphenForce-Directed Algorithms
Level-based Node PlacementStep 1for each node v Vi \ Vi 1 find optimal position withrespect to three adjacent nodes Vi 1Step 2perform force-based refinement, where forces are computedlocally only to a constant number of nearest neighbors in ViProperties of GRIPintelligent step-by-step calculation starting from a goodlayout and using MIS-filteringsignificantly faster convergencegraphs with 10,000 nodes in seconds (2004)25Dr. Tamara Mchedlidze · Algorithmen zur Visualisierung von GraphenForce-Directed Algorithms
Experimens(Hachul, Jünger 2007)Left: Grid version ofFruchterman Reingold.Right: GRIP26Dr. Tamara Mchedlidze · Algorithmen zur Visualisierung von GraphenForce-Directed Algorithms
Other ExamplesLombardi-Spring-Embedder (Chernobelskiy et al. 2012)edges are circular arcsgoal: optimal angular resolution 2π/ deg(v) at each node vadditional rotational forces27Dr. Tamara Mchedlidze · Algorithmen zur Visualisierung von GraphenForce-Directed Algorithms
Other ExamplesLombardi-Spring-Embedder (Chernobelskiy et al. 2012)edges are circular arcsgoal: optimal angular resolution 2π/ deg(v) at each node vadditional rotational forcesMetro Maps with Bézier curves (Fink et al. 2013)model paths as Bézier curvesforces on nodes and control points:lines are distinguishablefew bend pointsfew control points27Dr. Tamara Mchedlidze · Algorithmen zur Visualisierung von GraphenForce-Directed Algorithms
Other ExamplesLombardi-Spring-Embedder (Chernobelskiy et al. 2012)edges are circular arcsgoal: optimal angular resolution 2π/ deg(v) at each node vadditional rotational forcesMetro Maps with Bézier curves (Fink et al. 2013)model paths as Bézier curvesforces on nodes and control points:lines are distinguishablefew bend pointsfew control pointsRealistic Node Sizes (Gansner, North 1998)node positions are adjusted to avoid overlaps27Dr. Tamara Mchedlidze · Algorithmen zur Visualisierung von GraphenForce-Directed Algorithms
SummaryForce-based Approaches areeasily understandable and implementableno special requirements on the input graphdepending on the graphs (small and sparce) amazinglygood layouts (Symmetries, Clustering, .)easily adaptable and configurablerobustscalable28Dr. Tamara Mchedlidze · Algorithmen zur Visualisierung von GraphenForce-Directed Algorithms
SummaryForce-based Approaches areeasily understandable and implementableno special requirements on the input graphdepending on the graphs (small and sparce) amazinglygood layouts (Symmetries, Clustering, .)easily adaptable and configurablerobustscalableBut.usually no quality and running time guaraneesbad choice of starting layout slow convergencepossibly slow for large graphsfine-turning can be done by experts28Dr. Tamara Mchedlidze · Algorithmen zur Visualisierung von GraphenForce-Directed Algorithms
9Dr. Tamara Mchedlidze · Algorithmen zur Visualisierung von Graphenc Davis & HuForce-Directed Algorithms
Dr. Tamara Mchedlidze Algorithmen zur Visualisierung von Graphen Force-Directed Algorithms 4 Example: Fixed edge-length Given: Graph G (V;E), required edge length '(e), 8e 2 E Find: Drawing of G which realizes all the edge lengths NP-hard for edge lengths f1;2g [Saxe, '80] planar drawing with unit edge length [Eades, Wormald, '90]
