Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userOn Graph Crossing Number and Edge Planarization
157
0
0.0
(
0
)
Added by
Julia Chuzhoy
Publication date
2010
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
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.
rate research
Read More
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-trivial approximation algorithms are only known for bounded-degree graphs. Even for this special case, the best current algorithm achieves a $tilde O(sqrt n)$-approximation, while the best current negative result is APX-hardness. All current approximation algorithms for the problem build on the same paradigm: compute a set $E$ of edges (called a emph{planarizing set}) such that $Gsetminus E$ is planar; compute a planar drawing of $Gsetminus E$; then add the drawings of the edges of $E$ to the resulting drawing. Unfortunately, there are examples of graphs, in which any implementation of this method must incur $Omega (text{OPT}^2)$ crossings, where $text{OPT}$ is the value of the optimal solution. This barrier seems to doom the only known approach to designing approximation algorithms for the problem, and to prevent it from yielding a better than $O(sqrt n)$-approximation. In this paper we propose a new paradigm that allows us to overcome this barrier. We show an algorithm that, given a bounded-degree graph $G$ and a planarizing set $E$ of its edges, computes another set $E$ with $Esubseteq E$, such that $|E|$ is relatively small, and there exists a near-optimal drawing of $G$ in which only edges of $E$ participate in crossings. This allows us to reduce the Crossing Number problem to emph{Crossing Number with Rotation System} -- a variant in which the ordering of the edges incident to every vertex is fixed as part of input. We show a randomized algorithm for this new problem, that allows us to obtain an $O(n^{1/2-epsilon})$-approximation for Crossing Number on bounded-degree graphs, for some constant $epsilon>0$.
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 one such criterion, usually at the expense of others. We propose a layout approach, Graph Drawing via Gradient Descent, $(GD)^2$, that can handle multiple readability criteria. $(GD)^2$ can optimize any criterion that can be described by a smooth function. If the criterion cannot be captured by a smooth function, a non-smooth function for the criterion is combined with another smooth function, or auto-differentiation tools are used for the optimization. Our approach is flexible and can be used to optimize several criteria that have already been considered earlier (e.g., obtaining ideal edge lengths, stress, neighborhood preservation) as well as other criteria which have not yet been explicitly optimized in such fashion (e.g., vertex resolution, angular resolution, aspect ratio). We provide quantitative and qualitative evidence of the effectiveness of $(GD)^2$ with experimental data and a functional prototype: url{http://hdc.cs.arizona.edu/~mwli/graph-drawing/}.
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 of diagrammatic moves on triple-crossing diagrams analogous to the Reidemeister moves on ordinary diagrams. The existence of n-crossing diagrams for every n>1 allows the definition of the n-crossing number. We prove that for any nontrivial, nonsplit link, other than the Hopf link, its triple-crossing number is strictly greater than its quintuple-crossing number.
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 graph has a emph{convex} straight-line drawing, e.g., a drawing with vertices in convex position, that maximizes the number of edge crossings. We disprove this conjecture by constructing a planar graph on twelve vertices that allows a non-convex drawing with more crossings than any convex one. Bald et al. [Proc. COCOON, 2016] showed that it is NP-hard to compute the maximum number of crossings of a geometric graph and that the weighted geometric case is NP-hard to approximate. We strengthen these results by showing hardness of approximation even for the unweighted geometric case and prove that the unweighted topological case is NP-hard.
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 types of edge weights. In this note we describe a simple 3/2 approximation for the graph balancing problem with two-edge types, settling this very special case of makespan minimization.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
