Inf-MP-ES: Masterprojekt Echtzeitsysteme/Eingebettete Systeme (Layout)

Welcome!

Welcome to the Wiki page of the Master project offered by the Real Time and Embedded Systems group on orthogonal layout.

• We give you some insight about what the project is about.
• It's the place where we post important information on the project, such as due dates and similar information.
• And finally, it's the place where each group will document their project.

About the Orthogonal Layout and the Topology Shape Metrics Approach

The topology shape metrics approach follows three steps:

• Topology: Making sure that the order of edges around a node is good and therefore the topology of the graph is good
  • This should consider potential constraints ports might have and nodes might need, such as the port constraints supported by ELK, since this might be required for visualizing bus routes.
  • Other idea: Do octagonal layout or hexagonal layouts meaning that we do not have 4 sides of a node but 8 or 6.
• Shape: Make sure that we have minimal edge bends, i.e. the drawing has a nice shape
• Metrics: Assign real coordinates to nodes and routes to edges, e.g. on a grid or following other constraints

Topics for this Master's Project

In this Master's project, we want you to bring your expertise as a computer scientist interested in algorithm engineering or person interested in visualization to tackle the following tasks:

• Create an algorithm for orthogonal layout using as part of the Eclipse Layout Kernel
• Visualize all bus routes in Kiel using the orthogonal layout algorithm.
• Use test-driven development to ensure functionality

Contact us:

The project is supervised by the following university staff. Please contact us if you have questions regarding the project.

Prof. Dr. Reinhard von Hanxleden (rvh@informatik...)
Maximilian Kasperowski (mka@informatik...)
Sören Domrös (sdo@informatik...)

Important dates:

Kick-Off Meeting: Date 22.10.25 Time 14:15 Location CAP 4 R.1115

Examples:

See what yworks has to offer.

Get inspired by the map of KVG bus lines.

Literature

• Implementing an Algorithm for Orthogonal Graph Layout (Bachelor Thesis), https://rtsys.informatik.uni-kiel.de/%7Ebiblio/downloads/theses/ocl-bt.pdf
• A Generic Framework for Topology-Shape-Metrics-Based Layout, https://rtsys.informatik.uni-kiel.de/~biblio/downloads/theses/pkl-mt.pdf
• A Topology-Shape-Metrics Approach for the Automatic Layout of UML Class Diagrams, https://dl.acm.org/doi/pdf/10.1145/774833.774860
• HOLA: Human-like Orthogonal Network Layout, https://ieeexplore.ieee.org/abstract/document/7192690
• Orthogonal graph drawing with constraints: algorithms and applications, https://bibliographie.uni-tuebingen.de/xmlui/bitstream/handle/10900/49366/pdf/diss.pdf;sequence=1
• Non-planar Orthogonal Drawings with Fixed Topology, https://link.springer.com/chapter/10.1007/978-3-540-30577-4_13
• yFiles Orthogonal Layout, https://docs.yworks.com/yfilesjavafx/doc/api/#/dguide/orthogonal_layout
• The Open Graph Drawing Framework (OGDF), (see https://ogdf.uos.de/),https://ogdf.uos.de/wp-content/uploads/2019/04/ogdf.pdf

Metro Line Layout

• Automatic Metro Map Layout Using Multicriteria Optimization, https://ieeexplore.ieee.org/stamp/stamp.jsp?arnumber=5406516

Port Constraints

• Drawing layered graphs with port constraints https://www.sciencedirect.com/science/article/pii/S1045926X13000943
• Layered drawing of undirected graphs with generalized port constraints, https://www.sciencedirect.com/science/article/pii/S0925772122000293
• Orthogonal Graph Drawing with Constraints, https://dl.acm.org/doi/pdf/10.5555/338219.338225