Skip to Content

Wiki source code of KLay Planar

Version 4.1 by msp on 2012/11/15 09:11
Hide last authors
msp 1.1 1 {{panel title="Project Overview"}}
2 Responsible:
3
msp 4.1 4 * {{mention reference="XWiki.msp" style="FULL_NAME" anchor="XWiki-msp-arwCB"/}}
msp 1.1 5
6 Related Theses:
7
msp 3.1 8 * Ole Claußen, //Implementing an algorithm for orthogonal graph layout//, September 2010 ([[pdf>>url:http://rtsys.informatik.uni-kiel.de/~~biblio/downloads/theses/ocl-bt.pdf||shape="rect"]])
msp 1.1 9 * Christian Kutschmar, //Planarisierung von Hypergraphen//, September 2010 ([[pdf>>url:http://rtsys.informatik.uni-kiel.de/~~biblio/downloads/theses/cku-bt.pdf||shape="rect"]])(% style="color: rgb(0,0,0);" %)
10
msp 3.1 11 * Paul Klose, //A generic framework for topology-shape-metrics-based layout//, October 2012 ([[pdf>>url:http://rtsys.informatik.uni-kiel.de/~~biblio/downloads/theses/pkl-mt.pdf||shape="rect" class="external-link-new-window"]])
msp 1.1 12 {{/panel}}
13
14 KLay Planar encompasses planarization based layout algorithms. The main approach employed here is the //topology-shape-metrics// approach, which consists of the following phases:
15
16 1. Planar subgraph - Remove edges until the resulting subgraph is planar. The goal is to minimize the number of removed edges.
17 1. 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.
18 1. 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.
19 1. Compaction - Determine specific coordinates for nodes and edge bend points (//metrics//). The goal is to minimize the length of edge segments.
20
21 The implementation is currently in progress...