اشترك بالحزمة الذهبية واحصل على وصول غير محدود شمرا أكاديميا
تسجيل مستخدم جديدThe Tree Stabbing Number is not Monotone
143
0
0.0
(
0
)
اسأل ChatGPT حول البحث
ﻻ يوجد ملخص باللغة العربية
Let $P subseteq mathbb{R}^2$ be a set of points and $T$ be a spanning tree of $P$. The emph{stabbing number} of $T$ is the maximum number of intersections any line in the plane determines with the edges of $T$. The emph{tree stabbing number} of $P$ is the minimum stabbing number of any spanning tree of $P$. We prove that the tree stabbing number is not a monotone parameter, i.e., there exist point sets $P subsetneq P$ such that treestab{$P$} $>$ treestab{$P$}, answering a question by Eppstein cite[Open Problem~17.5]{eppstein_2018}.
قيم البحث
اقرأ أيضاً
We describe a family of graphs with queue-number at most 4 but unbounded stack-number. This resolves open problems of Heath, Leighton and Rosenberg (1992) and Blankenship and Oporowski (1999).
The emph{segment number} of a planar graph is the smallest number of line segments whose union represents a crossing-free straight-line drawing of the given graph in the plane. The segment number is a measure for the visual complexity of a drawing; i
t has been studied extensively. In this paper, we study three variants of the segment number: for planar graphs, we consider crossing-free polyline drawings in 2D; for arbitrary graphs, we consider crossing-free straight-line drawings in 3D and straight-line drawings with crossings in 2D. We first construct an infinite family of planar graphs where the classical segment number is asymptotically twice as large as each of the new variants of the segment number. Then we establish the $existsmathbb{R}$-completeness (which implies the NP-hardness) of all variants. Finally, for cubic graphs, we prove lower and upper bounds on the new variants of the segment number, depending on the connectivity of the given graph.
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.
In a geometric network G = (S, E), the graph distance between two vertices u, v in S is the length of the shortest path in G connecting u to v. The dilation of G is the maximum factor by which the graph distance of a pair of vertices differs from the
ir Euclidean distance. We show that given a set S of n points with integer coordinates in the plane and a rational dilation delta > 1, it is NP-hard to determine whether a spanning tree of S with dilation at most delta exists.
سجل دخول لتتمكن من نشر تعليقات
التعليقات
جاري جلب التعليقات
سجل دخول لتتمكن من متابعة معايير البحث التي قمت باختيارها
