Distinct distances in graph drawings

MaRDI QIDQ1010836zbMATH OpenFDO

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 numberstraight 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 $mathcalO(logn)$. 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

• Graph drawings with few slopes
• Graphs whose vertices are graphs with bounded degree: Distance problems
• Drawing outerplanar graphs using three edge lengths
• Minimal distinct distance trees
• Degenerate drawing of outerplanar graphs with two edge lengths

Cited in

(13)

• Degenerate drawing of outerplanar graphs with two edge lengths
• Crossings in grid drawings
• Testing the planar straight-line realizability of 2-trees with prescribed edge lengths
• Product structure of graph classes with bounded treewidth
• Products of unit distance graphs
• Drawing outerplanar graphs using thirteen edge lengths
• On tree-partition-width
• scientific article; zbMATH DE number 5851309 (Why is no real title available?)
• scientific article; zbMATH DE number 6874575 (Why is no real title available?)
• Tree-partitions with bounded degree trees
• Bandwidth, expansion, treewidth, separators and universality for bounded-degree graphs
• Drawing outerplanar graphs using three edge lengths
• The plane-width of graphs

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)