Distinct Distances in Graph Drawings
| dc.creator | Carmi, Paz | |
| dc.creator | Dujmović, Vida | |
| dc.creator | Morin, Pat | |
| dc.creator | Wood, David R. | |
| dc.date | 2008-04-23 | |
| dc.date.accessioned | 2026-07-07T10:01:11Z | |
| dc.date.available | 2026-07-07T10:01:11Z | |
| dc.description | 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 $Δ$ increases the existential lower bound on the distance-number of $Δ$-regular graphs tends to $Ω(n^{0.864138})$. | |
| dc.identifier | https://arxiv.org/abs/0804.3690 | |
| dc.identifier | http://arxiv.org/abs/0804.3690 | |
| dc.identifier | The Electronic Journal of Combinatorics 15(1):R107, 2008 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/168550 | |
| dc.subject | Combinatorics | |
| dc.title | Distinct Distances in Graph Drawings | |
| dc.type | text |