اشترك بالحزمة الذهبية واحصل على وصول غير محدود شمرا أكاديميا
تسجيل مستخدم جديدOn the Maximum Crossing Number
197
0
0.0
(
0
)
اسأل ChatGPT حول البحث
ﻻ يوجد ملخص باللغة العربية
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.
قيم البحث
اقرأ أيضاً
A graph drawn in the plane with n vertices is k-fan-crossing free for k > 1 if there are no k+1 edges $g,e_1,...e_k$, such that $e_1,e_2,...e_k$ have a common endpoint and $g$ crosses all $e_i$. We prove a tight bound of 4n-8 on the maximum number of
edges of a 2-fan-crossing free graph, and a tight 4n-9 bound for a straight-edge drawing. For k > 2, we prove an upper bound of 3(k-1)(n-2) edges. We also discuss generalizations to monotone graph properties.
We show that determining the crossing number of a link is NP-hard. For some weaker notions of link equivalence, we also show NP-completeness.
We introduce a model for random geodesic drawings of the complete bipartite graph $K_{n,n}$ on the unit sphere $mathbb{S}^2$ in $mathbb{R}^3$, where we select the vertices in each bipartite class of $K_{n,n}$ with respect to two non-degenerate probab
ility measures on $mathbb{S}^2$. It has been proved recently that many such measures give drawings whose crossing number approximates the Zarankiewicz number (the conjectured crossing number of $K_{n,n}$). In this paper we consider the intersection graphs associated with such random drawings. We prove that for any probability measures, the resulting random intersection graphs form a convergent graph sequence in the sense of graph limits. The edge density of the limiting graphon turns out to be independent of the two measures as long as they are antipodally symmetric. However, it is shown that the triangle densities behave differently. We examine a specific random model, blow-ups of antipodal drawings $D$ of $K_{4,4}$, and show that the triangle density in the corresponding crossing graphon depends on the angles between the great circles containing the edges in $D$ and can attain any value in the interval $bigl(frac{83}{12288}, frac{128}{12288}bigr)$.
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.
Given a set of points $P$ and axis-aligned rectangles $mathcal{R}$ in the plane, a point $p in P$ is called emph{exposed} if it lies outside all rectangles in $mathcal{R}$. In the emph{max-exposure problem}, given an integer parameter $k$, we want to
delete $k$ rectangles from $mathcal{R}$ so as to maximize the number of exposed points. We show that the problem is NP-hard and assuming plausible complexity conjectures is also hard to approximate even when rectangles in $mathcal{R}$ are translates of two fixed rectangles. However, if $mathcal{R}$ only consists of translates of a single rectangle, we present a polynomial-time approximation scheme. For range space defined by general rectangles, we present a simple $O(k)$ bicriteria approximation algorithm; that is by deleting $O(k^2)$ rectangles, we can expose at least $Omega(1/k)$ of the optimal number of points.
سجل دخول لتتمكن من نشر تعليقات
التعليقات
جاري جلب التعليقات
سجل دخول لتتمكن من متابعة معايير البحث التي قمت باختيارها
