Subdividing a graph toward a unit-distance graph in the plane (Q1971803): Difference between revisions
From MaRDI portal
Created a new Item |
Added link to MaRDI item. |
||
links / mardi / name | links / mardi / name | ||
Revision as of 17:38, 1 February 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Subdividing a graph toward a unit-distance graph in the plane |
scientific article |
Statements
Subdividing a graph toward a unit-distance graph in the plane (English)
0 references
9 June 2000
0 references
What is the least number \(\text{sd}(G)\) of vertices to be added to the edges of a graph \(G\), so as to be able to imbed it in the plane with only unit length segments as edges? This subdivision number is studied for complete and complete bipartite graphs. The following bounds are obtained: \(\frac{1}{2}n(n-1) - t(n) \leq \text{sd}(K_n) \leq \frac{1}{2}(n-2)(n-3)+2\), where \(t(n)\) is the largest number of edges of a 4-cycle-less graph on \(n\) vertices; and \(\text{sd}(K(m,n))= (m-1)(n-m) \) when \(n \geq m(m-1)\). Tables of exact values are derived for small values of \(n\) and \(m\).
0 references
unit distance graph
0 references
homeomorphic graph
0 references
subdivision number
0 references