ﻻ يوجد ملخص باللغة العربية
Given an n-vertex graph G, a drawing of G in the plane is a mapping of its vertices into points of the plane, and its edges into continuous curves, connecting the images of their endpoints. A crossing in such a drawing is a point where two such curves intersect. In the Minimum Crossing Number problem, the goal is to find a drawing of G with minimum number of crossings. The value of the optimal solution, denoted by OPT, is called the graphs crossing number. This is a very basic problem in topological graph theory, that has received a significant amount of attention, but is still poorly understood algorithmically. The best currently known efficient algorithm produces drawings with $O(log^2 n)(n + OPT)$ crossings on bounded-degree graphs, while only a constant factor hardness of approximation is known. A closely related problem is Minimum Edge Planarization, in which the goal is to remove a minimum-cardinality subset of edges from G, such that the remaining graph is planar. Our main technical result establishes the following connection between the two problems: if we are given a solution of cost k to the Minimum Edge Planarization problem on graph G, then we can efficiently find a drawing of G with at most $poly(d)cdot kcdot (k+OPT)$ crossings, where $d$ is the maximum degree in G. This result implies an $O(ncdot poly(d)cdot log^{3/2}n)$-approximation for Minimum Crossing Number, as well as improved algorithms for special cases of the problem, such as, for example, k-apex and bounded-genus graphs.
Graph Crossing Number is a fundamental problem with various applications. In this problem, the goal is to draw an input graph $G$ in the plane so as to minimize the number of crossings between the images of its edges. Despite extensive work, non-triv
Readability criteria, such as distance or neighborhood preservation, are often used to optimize node-link representations of graphs to enable the comprehension of the underlying data. With few exceptions, graph drawing algorithms typically optimize o
Every link in the 3-sphere has a projection to the plane where the only singularities are pairwise transverse triple points. The associated diagram, with height information at each triple point, is a triple-crossing diagram of the link. We give a set
Research about crossings is typically about minimization. In this paper, we consider emph{maximizing} the number of crossings over all possible ways to draw a given graph in the plane. Alpert et al. [Electron. J. Combin., 2009] conjectured that any g
In the graph balancing problem the goal is to orient a weighted undirected graph to minimize the maximum weighted in-degree. This special case of makespan minimization is NP-hard to approximate to a factor better than 3/2 even when there are only two