Layout Algorithms (KLay) - KLay Planar 

Page / - last modified by Richard Kreissig on 2023/09/14 10:23 

KLay Planar 
last modified by Richard Kreissig
on 2023/09/14 10:23

Table of Contents
Project Overview

Project Overview
Related Theses:
•	Ole Claußen, Implementing an algorithm for orthogonal graph layout, September 2010 (pdf)
•	Christian Kutschmar, Planarisierung von Hypergraphen, September 2010 (pdf)
•	Paul Klose, A generic framework for topology-shape-metrics-based layout, October 2012 (pdf)
KLay Planar encompasses planarization based layout algorithms. The main approach employed here is the topology-shape-metrics approach, which consists of the following phases:
 1.	Planar subgraph - Remove edges until the resulting subgraph is planar. The goal is to minimize the number of removed edges.
 2.	Edge insertion - Reinsert the previously removed edges and replace all resulting crossings by new dummy nodes. The result is a planar embedding (topology). The goal is to minimize the number of introduced dummy nodes.
 3.	Orthogonalization - Find an orthogonal form by computing a series left or right bends for each edge (shape). The goal is to minimize the number of bends.
 4.	Compaction - Determine specific coordinates for nodes and edge bend points (metrics). The goal is to minimize the length of edge segments.
The implementation is currently in progress...