Distinct distances in graph drawings

Authors Paz Carmi, Pat Morin, David R. Wood, Vida Dujmović

Publication date 7 April 2009

Published in The Electronic Journal of Combinatorics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/0804.3690, https://eudml.org/doc/117263, http://www.emis.de/journals/EJC/Volume_15/Abstracts/v15i1r107.html

IPFS File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

zbMATH Keywords

distance number straight line drawings of graphs in the plane

Mathematics Subject Classification ID

Distance in graphs (05C12) Graph representations (geometric and intersection representations, etc.) (05C62)

Abstract: 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

m a t h c a l O (l o g 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

D e l t a

increases the existential lower bound on the distance-number of

D e l t a

-regular graphs tends to

O m e g a (n^{0.864138})

.

Review text

Summary: The 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})\).

Recommendations

Cited in

(16)

This page was built for publication: Distinct distances in graph drawings

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1010836)