اشترك بالحزمة الذهبية واحصل على وصول غير محدود شمرا أكاديميا
تسجيل مستخدم جديدDistinct Distances in Graph Drawings
249
0
0.0
(
0
)
اسأل ChatGPT حول البحث
ﻻ يوجد ملخص باللغة العربية
The emph{distance-number} of a graph $G$ is the minimum number of distinct edge-lengths over all straight-line drawings of $G$ in the plane. This definition generalises many well-known concepts in combinatorial geometry. We consider the distance-number of trees, graphs with no $K^-_4$-minor, complete bipartite graphs, complete graphs, and cartesian products. Our main results concern the distance-number of graphs with bounded degree. We prove that $n$-vertex graphs with bounded maximum degree and bounded treewidth have distance-number in $mathcal{O}(log n)$. To conclude such a logarithmic upper bound, both the degree and the treewidth need to be bounded. In particular, we construct graphs with treewidth 2 and polynomial distance-number. Similarly, we prove that there exist graphs with maximum degree 5 and arbitrarily large distance-number. Moreover, as $Delta$ increases the existential lower bound on the distance-number of $Delta$-regular graphs tends to $Omega(n^{0.864138})$.
قيم البحث
اقرأ أيضاً
We study ErdH oss distinct distances problem under $ell_p$ metrics with integer $p$. We improve the current best bound for this problem from $Omega(n^{4/5})$ to $Omega(n^{6/7-epsilon})$, for any $epsilon>0$. We also characterize the sets that span an
asymptotically minimal number of distinct distances under the $ell_1$ and $ell_infty$ metrics.
We consider the number of distinct distances between two finite sets of points in ${bf R}^k$, for any constant dimension $kge 2$, where one set $P_1$ consists of $n$ points on a line $l$, and the other set $P_2$ consists of $m$ arbitrary points, such
that no hyperplane orthogonal to $l$ and no hypercylinder having $l$ as its axis contains more than $O(1)$ points of $P_2$. The number of distinct distances between $P_1$ and $P_2$ is then $$ Omegaleft(minleft{ n^{2/3}m^{2/3},; frac{n^{10/11}m^{4/11}}{log^{2/11}m},; n^2,; m^2right}right) . $$ Without the assumption on $P_2$, there exist sets $P_1$, $P_2$ as above, with only $O(m+n)$ distinct distances between them.
We consider the problem of placing arrow heads in directed graph drawings without them overlapping other drawn objects. This gives drawings where edge directions can be deduced unambiguously. We show hardness of the problem, present exact and heuristic algorithms, and report on a practical study.
In this paper we obtain a new lower bound on the ErdH{o}s distinct distances problem in the plane over prime fields. More precisely, we show that for any set $Asubset mathbb{F}_p^2$ with $|A|le p^{7/6}$, the number of distinct distances determined by
pairs of points in $A$ satisfies $$ |Delta(A)| gg |A|^{frac{1}{2}+frac{149}{4214}}.$$ Our result gives a new lower bound of $|Delta{(A)}|$ in the range $|A|le p^{1+frac{149}{4065}}$. The main tools we employ are the energy of a set on a paraboloid due to Rudnev and Shkredov, a point-line incidence bound given by Stevens and de Zeeuw, and a lower bound on the number of distinct distances between a line and a set in $mathbb{F}_p^2$. The latter is the new feature that allows us to improve the previous bound due Stevens and de Zeeuw.
For any cofinite Fuchsian group $Gammasubset {rm PSL}(2, mathbb{R})$, we show that any set of $N$ points on the hyperbolic surface $Gammabackslashmathbb{H}^2$ determines $geq C_{Gamma} frac{N}{log N}$ distinct distances for some constant $C_{Gamma}>0
$ depending only on $Gamma$. In particular, for $Gamma$ being any finite index subgroup of ${rm PSL}(2, mathbb{Z})$ with $mu=[{rm PSL}(2, mathbb{Z}): Gamma ]<infty$, any set of $N$ points on $Gammabackslashmathbb{H}^2$ determines $geq Cfrac{N}{mulog N}$ distinct distances for some absolute constant $C>0$.
سجل دخول لتتمكن من نشر تعليقات
التعليقات
جاري جلب التعليقات
سجل دخول لتتمكن من متابعة معايير البحث التي قمت باختيارها
