Do you want to publish a course? Click here

Distinct Distances in Graph Drawings

241   0   0.0 ( 0 )
 Added by David Wood
 Publication date 2008
  fields
and research's language is English




Ask ChatGPT about the research

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})$.



rate research

Read More

120 - Moaaz AlQady 2020
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.
153 - Xianchang Meng 2020
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$.
comments
Fetching comments Fetching comments
Sign in to be able to follow your search criteria
mircosoft-partner

هل ترغب بارسال اشعارات عن اخر التحديثات في شمرا-اكاديميا