2
$\begingroup$

I just want to ask, what is the significance of subdividing a graph toward a unit distance graph? I have seen several studies of it but I cannot find what its importance. I mean, like the study of Gervacio and Maehara.

Subdividing a Graph Toward a Unit-distance Graph in the Plane.

Severino V. Gervacio, Hiroshi Maehara Eur. J. Comb 01/2000; 21:223-229. DOI:10.1006/eujc.1999.0348 Source: DBLP ABSTRACT The subdivision number of a graph G is defined to be the minimum number of extra vertices inserted into the edges of G to make it isomorphic to a unit-distance graph in the plane. Lett (n) denote the maximum number of edges of a C4-free graph on n vertices. It is proved that the subdivision number of Knlies betweenn (n− 1)/2 −t(n) and (n− 2)(n− 3)/2 + 2, and that of K(m, n) equals (m− 1)(n−m) forn≥m(m− 1).

$\endgroup$

1 Answer 1

3
$\begingroup$

"Its importance" is a subjective judgement. As the introduction of the paper explains, not every graph is isomorphic to a unit-distance graph, but every graph is homeomorphic to a unit-distance graph by inserting vertices into edges. So it is a natural question to ask how many insertions are necessary.

Unit-distance graphs are of great interest in the area of geometric graph theory. They have been studied at least since 1946 when Erdős posed the question of counting unit-distance pairs of points, a still not entirely solved problem. More recently, unit-distance graphs have been used to model ad hoc wireless networks.
     enter image description here
     See the earlier MO question, "Erdős, Harary, Tutte's “dimension of graph”: Progress in last 48 yrs?"

$\endgroup$
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.