Distinct Distances in Graph Drawings

Details Distinct Distances in Graph Drawings Distinct Distances in Graph Drawings

2008-04-23

arxiv.org/abs/0804.3690v1

The Electronic Journal of Combinatorics 15(1):R107, 2008

Mathematics

Combinatorics

Scientific paper

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

Affiliated with

Also associated with

No associations

Rating

Distinct Distances in Graph Drawings does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Distinct Distances in Graph Drawings, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Distinct Distances in Graph Drawings will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-104897