Content deleted Content added
→Changing the rules: other ones |
→Properties of the utility graph: intro sentence |
||
Line 47:
==Properties of the utility graph==
Beyond the utility puzzle, the same graph <math>K_{3,3}</math> comes up in several other mathematical contexts, including [[Structural rigidity|rigidity theory]], the classification of [[Cage (graph theory)|cages]] and [[well-covered graph]]s, the study of [[crossing number (graph theory)|graph crossing numbers]], and the theory of [[graph minor]]s.
===Rigidity===
The utility graph <math>K_{3,3}</math> is a [[Laman graph]], meaning that for [[almost all]] placements of its vertices in the plane, there is no way to continuously move its vertices while preserving all edge lengths, other than by a [[Rigid transformation|rigid motion]] of the whole plane, and that none of its spanning subgraphs have the same [[rigid system|rigidity]] property. It is the smallest example of a nonplanar Laman graph.{{r|streinu}} Despite being a minimally rigid graph, it has non-rigid embeddings with special placements for its vertices.{{r|dixon|wh07}} For general-position embeddings, a [[polynomial equation]] describing all possible placements with the same edge lengths has degree 16, meaning that in general there can be at most 16 placements with the same lengths. It is possible to find systems of edge lengths for which up to eight of the solutions to this equation describe realizable placements.{{r|wh07}}
Line 62 ⟶ 64:
{{clear}}
==References==
{{reflist|refs=
| |||