Subdividing a graph toward a unit-distance graph in the plane (Q1971803): Difference between revisions
From MaRDI portal
Added link to MaRDI item. |
Set profile property. |
||
Property / MaRDI profile type | |||
Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank |
Revision as of 06:26, 5 March 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