Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userThe Tree Stabbing Number is not Monotone
143
0
0.0
(
0
)
Added by
Johannes Obenaus
Publication date
2020
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
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}.
rate research
Read More
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; it 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 their 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.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
