Edge Routing with Minimum Edge Crossings
Date Issued
2012
Date
2012
Author(s)
Liu, Chi-Hsien
Abstract
A solution to the problem of graph drawing can be considered to have two components, which are the positions of vertices and the routes of edges. These two components are not independent, and both need to be considered in order to produce a drawing that is more readable. However, the complexity of this problem, even a simpler version that only minimizes edge crossings, is already known to be NP-complete [1]. Thus, this thesis seeks to explore only the sub-problem of edge routing.
With the assumptions of knowing the positions and sizes of vertices and routing new edges one by one, this thesis implements and compares several methods of edge routing. Eventually, a visibility graph based method that can find routes which avoid vertices is extended to a weighted visibility graph based method that can not only avoid vertices but also minimize the number of edge crossings of the new route.
However, a shortcoming of this method is that its execution time depends primarily on the size of the graph such that routing an edge that needs to avoid few obstacles takes nearly as much time as routing an edge that needs to avoid many obstacles. This thesis improves on this by introducing a new approach whose execution time depends primarily on the number of obstacles that the edge being routed must avoid and is able to significantly reduce execution time for average cases.
Subjects
edge routing
edge crossings minimization
shortest path
weighted visibility graph
repeatedly expanding subgraph
Type
thesis
File(s)![Thumbnail Image]()
Loading...
Name
ntu-101-R99921041-1.pdf
Size
23.32 KB
Format
Adobe PDF
Checksum
(MD5):ecd35e03113b3dc323aaa30b8a6a9ea8