Student Projects - 2025/26 Orthogonal Layout Project

Page / - last modified by Soeren Domroes on 2025/10/06 10:05

2025/26 Orthogonal Layout Project

last modified by Soeren Domroes

on 2025/10/06 10:05

Table of Contents

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

Welcome!

About the Orthogonal Layout and the Topology Shape Metrics Approach

Topics for this Master's Project

Contact us:

Important dates:

Examples:

Literature

Metro Line Layout

Port Constraints

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

Date
22.10.2025	Kick-Off Meeting in CAP 4 R. 1115
TBD	First intermediate Presentation
TBD	Second intermediate Presentation
TBD	Final Presentation

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