Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userVertex Splitting, Coincident Realisations and Global Rigidity of Braced Triangulations
77
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
We give a short proof of a result of Jordan and Tanigawa that a 4-connected graph which has a spanning planar triangulation as a proper subgraph is generically globally rigid in R^3. Our proof is based on a new sufficient condition for the so called vertex splitting operation to preserve generic global rigidity in R^d.
rate research
Read More
We consider the problem of finding an inductive construction, based on vertex splitting, of triangulated spheres with a fixed number of additional edges (braces). We show that for any positive integer $b$ there is such an inductive construction of triangulations with $b$ braces, having finitely many base graphs. In particular we establish a bound for the maximum size of a base graph with $b$ braces that is linear in $b$. In the case that $b=1$ or $2$ we determine the list of base graphs explicitly. Using these results we show that doubly braced triangulations are (generically) minimally rigid in two distinct geometric contexts arising from a hypercylinder in $mathbb{R}^4$ and a class of mixed norms on $mathbb{R}^3$.
Fekete, Jordan and Kaszanitzky [4] characterised the graphs which can be realised as 2-dimensional, infinitesimally rigid, bar-joint frameworks in which two given vertices are coincident. We formulate a conjecture which would extend their characterisation to an arbitrary set T of vertices and verify our conjecture when |T| = 3.
For a simple graph $G$, denote by $n$, $Delta(G)$, and $chi(G)$ its order, maximum degree, and chromatic index, respectively. A connected class 2 graph $G$ is edge-chromatic critical if $chi(G-e)<Delta(G)+1$ for every edge $e$ of $G$. Define $G$ to be overfull if $|E(G)|>Delta(G) lfloor n/2 rfloor$. Clearly, overfull graphs are class 2 and any graph obtained from a regular graph of even order by splitting a vertex is overfull. Let $G$ be an $n$-vertex connected regular class 1 graph with $Delta(G) >n/3$. Hilton and Zhao in 1997 conjectured that if $G^*$ is obtained from $G$ by splitting one vertex of $G$ into two vertices, then $G^*$ is edge-chromatic critical, and they verified the conjecture for graphs $G$ with $Delta(G)ge frac{n}{2}(sqrt{7}-1)approx 0.82n$. The graph $G^*$ is easily verified to be overfull, and so the hardness of the conjecture lies in showing that the deletion of every of its edge decreases the chromatic index. Except in 2002, Song showed that the conjecture is true for a special class of graphs $G$ with $Delta(G)ge frac{n}{2}$, no other progress on this conjecture had been made. In this paper, we confirm the conjecture for graphs $G$ with $Delta(G) ge 0.75n$.
A linearly constrained framework in $mathbb{R}^d$ is a point configuration together with a system of constraints which fixes the distances between some pairs of points and additionally restricts some of the points to lie in given affine subspaces. It is globally rigid if the configuration is uniquely defined by the constraint system, and is rigid if it is uniquely defined within some small open neighbourhood. Streinu and Theran characterised generic rigidity of linearly constrained frameworks in $mathbb{R}^2$ in 2010. We obtain an analagous characterisation for generic global rigidity in $mathbb{R}^2$. More precisely we show that a generic linearly constrained framework in $mathbb{R}^2$ is globally rigid if and only if it is redundantly rigid and `balanced. For generic frameworks which are not balanced, we determine the precise number of solutions to the constraint system whenever the underlying rigidity matroid of the given framework is connected. We also obtain a stress matrix sufficient condition and a Hendrickson type necessary condition for a generic linearly constrained framework to be globally rigid in $mathbb{R}^d$.
We show that a generic framework $(G,p)$ on the cylinder is globally rigid if and only if $G$ is a complete graph on at most four vertices or $G$ is both redundantly rigid and $2$-connected. To prove the theorem we also derive a new recursive construction of circuits in the simple $(2,2)$-sparse matroid, and a characterisation of rigidity for generic frameworks on the cylinder when a single designated vertex is allowed to move off the cylinder.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
