Subdividing a graph toward a unit-distance graph in the plane (Q1971803): Difference between revisions
From MaRDI portal
Added link to MaRDI item. |
ReferenceBot (talk | contribs) Changed an Item |
||
(2 intermediate revisions by 2 users not shown) | |||
Property / MaRDI profile type | |||
Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank | |||
Property / full work available at URL | |||
Property / full work available at URL: https://doi.org/10.1006/eujc.1999.0348 / rank | |||
Normal rank | |||
Property / OpenAlex ID | |||
Property / OpenAlex ID: W1973100834 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Graphs without four-cycles / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q3309635 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q5186278 / rank | |||
Normal rank |
Latest revision as of 14:59, 29 May 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