Skip to Content
Last modified by Soeren Domroes on 2024/05/24 07:41
From version 8.1
edited by Alexander Schulz-Rosengarten
on 2022/10/06 10:05
Change comment: There is no comment for this version
To version 12.1
edited by Soeren Domroes
on 2024/02/06 11:08
Change comment: There is no comment for this version

Summary

Details

Page properties
Title
... ... @@ -1,1 +1,1 @@
1 -Node Placement with Flexible Node Size and Port Position
1 +New Crossing Minimization strategies for ELK and their use for SCCharts
Parent
... ... @@ -1,0 +1,1 @@
1 +Theses.Topics for Student Theses.WebHome
Author
... ... @@ -1,1 +1,1 @@
1 -XWiki.als
1 +XWiki.sdo
Content
... ... @@ -1,33 +1,13 @@
1 -{{layout}}
2 -{{layout-section ac:type="single"}}
3 -{{layout-cell}}
4 -The classic Sugiyama graph drawing algorithm consists of 5 phases: cycle breaking, layer assignment, crossing minimization, node placement and edge routing. Node placement sets the x-coordinates of nodes (in a downward layout) and creates alignment between nodes, improves edge straightness, or balances nodes based on their incoming edges. Node sizes can also be used to eliminate edge bends by increasing the size of nodes, as seen below, which makes the drawing easier to read, edges easier to follow and therefore easier to understand.
5 -{{/layout-cell}}
6 -{{/layout-section}}
1 +There exist many one-sided crossing minimization strategies such as the Barycenter heuristic [1], the median heursitic [2], as well as sifting [3].
7 7  
8 -{{layout-section ac:type="two_left_sidebar"}}
9 -{{layout-cell}}
10 -[[image:attach:jette-stpa-oyes-bad.png]]
11 -{{/layout-cell}}
3 +The Eclipse Layout Kernel currently supports only the Barycenter heuristic, as well as the greedy switch heuristic [4].
12 12  
13 -{{layout-cell}}
14 -[[image:attach:jette-stpa-oyes.png]]
15 -{{/layout-cell}}
16 -{{/layout-section}}
5 +Part of this thesis should be to implement, new crossing minimization strategies and compare them based on the SCCharts language and its models.
17 17  
18 -{{layout-section ac:type="single"}}
19 -{{layout-cell}}
20 -TODO Fehler labels in rot und prominenter
21 -
22 -Figure showing the current layout without flexible node size and the existing ONO (obviously not optimal) parts of a layout with flexible node size
23 -
24 24  = Goals =
25 25  
26 -* Improve the existing Network Simplex node placement strategy with flexible node size by:\\
27 -** centering edges on their nodes if it does not compromise the quality of the layout, if necessary by increasing node sizes even more
28 -** minimize the size of the drawing if possible
29 -* (optional) Explore options that need configuration depending on the context.
30 -** alignment of edges, ...
9 +* Implement already existing crossing minimization strategies in ELK
10 +* Evaluate their use for a SCCharts
31 31  
32 32  = Scope =
33 33  
... ... @@ -35,15 +35,15 @@
35 35  
36 36  = Related Work/Literature =
37 37  
38 -Emden R. Gansner, Eleftherios Koutsofios, Stephen C. North, Kiem-Phong Vo, //A technique for drawing directed graphs//. Software Engineering 19(3), pp. 214-230, 1993.
18 +1. K. Sugiyama, S. Tagawa, and M. Toda. Methods for visual understanding of hierarchical system structures. IEEE Transactions on Systems, Man and Cybernetics, 11(2):109–125, February 1981.
19 +1. P. Eades and S. Whitesides. Drawing graphs in two layers. Theoretical Computer Science, 131:361–374, 1994
20 +1. Matuszewski, Christian, Robby Schönfeld, and Paul Molitor. "Using sifting for k-layer straightline crossing minimization." //Graph Drawing: 7th International Symposium, GD’99 Štiřín Castle, Czech Republic September 15–19, 1999 Proceedings 7//. Springer Berlin Heidelberg, 1999.
21 +1. P. Eades and D. Kelly. Heuristics for reducing crossings in 2-layered networks. Ars Combin., 21.A:89–98, 1986.
39 39  
40 -Ulf Rüegg, //Sugiyama Layouts for Prescribed Drawing Areas //([[KCSS>>url:https://www.uni-kiel.de/journals/receive/jportal_jparticle_00000341||shape="rect" class="internal-link"]] 2018/1), Chapter 4.1: Network Simplex Approach
41 -
42 42  = Involved Languages/Technologies =
43 43  
44 44  * Java
45 45  * ELK
46 -** [[https:~~/~~/github.com/eclipse/elk/issues/853>>url:https://github.com/eclipse/elk/issues/853||shape="rect"]] (corresponding ticket in [[ELK>>url:https://www.eclipse.org/elk/||shape="rect"]])
47 47  
48 48  = Supervised By =
49 49  
... ... @@ -50,6 +50,3 @@
50 50  Sören Domrös
51 51  
52 52  sdo@ifi
53 -{{/layout-cell}}
54 -{{/layout-section}}
55 -{{/layout}}
jette-stpa-oyes-bad.png
Author
... ... @@ -1,0 +1,1 @@
1 +XWiki.sdo
Size
... ... @@ -1,0 +1,1 @@
1 +319.0 KB
Content
jette-stpa-oyes.png
Author
... ... @@ -1,0 +1,1 @@
1 +XWiki.sdo
Size
... ... @@ -1,0 +1,1 @@
1 +211.6 KB
Content
jette-stpa-oyes.svg
Author
... ... @@ -1,0 +1,1 @@
1 +XWiki.sdo
Size
... ... @@ -1,0 +1,1 @@
1 +74.7 KB
Content
Confluence.Code.ConfluencePageClass[0]
Id
... ... @@ -1,1 +1,1 @@
1 -136183977
1 +136183893
URL
... ... @@ -1,1 +1,1 @@
1 -https://rtsys.informatik.uni-kiel.de/confluence//wiki/spaces/RTSYS/pages/136183977/Node Placement with Flexible Node Size and Port Position
1 +https://rtsys.informatik.uni-kiel.de/confluence//wiki/spaces/RTSYS/pages/136183893/Node Placement with Flexible Node Size and Port Position