DefinePK

Abstract

Routing, scheduling and location problems in our real-life can be formulated as combinatorial optimization problems whose goal is to find a linear layout of an input graph in such a way that the number of edge crossings is minimized. The problem of adding a new vertex to an existing straight-line graph drawing and connecting it to its adjacent vertices in such a way that the number of crossings made by adding this vertex is minimized is known as crossing minimization problem. Although many crossing number related problems are NP-Complete or NP-Hard. In this study, we present a polynomial time algorithm; O (|V|5.|E|). It checks a point in every Fully Drawing Region (FDR) and returns a point which is the position of the new vertex that minimizes the number of added crossings. It may be useful when we have an existing drawing which cannot be changed and we don’t know how vertices will be added in future.