Search

Huber et al. (SIAM J Comput 43:1064-1084, 2014) introduced a concept of skew bisubmodularity, as a generalization of bisubmodularity, in their complexity dichotomy theorem for valued constraint satisfaction problems over the three-value domain, and Huber and Krokhin (SIAM J Discrete Math 28:1828-1837, 2014) showed the oracle tractability of minimization of skew-bisubmodular functions. Fujishige et al. (Discrete Optim 12:1-9, 2014) also showed a min-max theorem that characterizes the skew-bisubmodular function minimization, but devising a combinatorial polynomial algorithm for skew-bisubmodular function minimization was left open. In the present paper we give first combinatorial (weakly and strongly) polynomial algorithms for skew-bisubmodular function minimization. [ABSTRACT FROM AUTHOR]

We investigate how to find generic and globally rigid realizations of graphs in R d based on elementary geometric observations. Our arguments lead to new proofs of a combinatorial characterization of the global rigidity of graphs in R 2 by Jackson and Jordán and that of body-bar graphs in R d recently shown by Connelly, Jordán, and Whiteley. We also extend the 1-extension theorem and Connelly's composition theorem, which are main tools for generating globally rigid graphs in R d . In particular we show that any vertex-redundantly rigid graph in R d is globally rigid in R d , where a graph G = ( V , E ) is called vertex-redundantly rigid if G − v is rigid for any v ∈ V . [ABSTRACT FROM AUTHOR]

The mathematical theory of rigidity of body-bar and body-hinge frameworks provides a useful tool for analyzing the rigidity and flexibility of many articulated structures appearing in engineering, robotics and biochemistry. In this paper we develop a symmetric extension of this theory which permits a rigidity analysis of body-bar and body-hinge structures with point group symmetries. The infinitesimal rigidity of body-bar frameworks can naturally be formulated in the language of the exterior (or Grassmann) algebra. Using this algebraic formulation, we derive symmetry-adapted rigidity matrices to analyze the infinitesimal rigidity of body-bar frameworks with Abelian point group symmetries in an arbitrary dimension. In particular, from the patterns of these new matrices, we derive combinatorial characterizations of infinitesimally rigid body-bar frameworks which are generic with respect to a point group of the form Z / 2Z ×⋯×Z / 2Z. Our characterizations are given in terms of packings of bases of signed-graphic matroids on quotient graphs. Finally, we also extend our methods and results to body-hinge frameworks with Abelian point group symmetries in an arbitrary dimension. [ABSTRACT FROM AUTHOR]

We prove that the linear matroid that defines the generic rigidity of d-dimensional body-rod-bar frameworks (i.e., structures consisting of disjoint bodies and rods mutually linked by bars) can be obtained from the union of (d+1/2) copies of a graphic matroid by applying variants of Dilworth truncation operations nr times, where nr denotes the number of rods. This result leads to an alternative proof of Tay's combinatorial characterizations of the generic rigidity of rod-bar frameworks and that of identified body-hinge frameworks. [ABSTRACT FROM AUTHOR]

A non-crossing geometric graph is a graph embedded on a set of points in the plane with non-crossing straight line segments. In this paper we present a general framework for enumerating non-crossing geometric graphs on a given point set. Applying our idea to specific enumeration problems, we obtain faster algorithms for enumerating plane straight-line graphs, non-crossing spanning connected graphs, non-crossing spanning trees, and non-crossing minimally rigid graphs. Our idea also produces efficient enumeration algorithms for other graph classes, for which no algorithm has been reported so far, such as non-crossing matchings, non-crossing red-and-blue matchings, non-crossing k-vertex or k-edge connected graphs, or non-crossing directed spanning trees. The proposed idea is relatively simple and potentially applies to various other problems of non-crossing geometric graphs. [ABSTRACT FROM AUTHOR]

A d -dimensional body-hinge framework is a structure consisting of rigid bodies in d -space in which some pairs of bodies are connected by a hinge, restricting the relative position of the corresponding bodies. The framework is said to be globally rigid if every other arrangement of the bodies and their hinges can be obtained by a congruence of the space. The combinatorial structure of a body-hinge framework can be encoded by a multigraph H , in which the vertices correspond to the bodies and the edges correspond to the hinges. We prove that a generic body-hinge realization of a multigraph H is globally rigid in R d , d ≥ 3 , if and only if ( ( d + 1 2 ) − 1 ) H − e contains ( d + 1 2 ) edge-disjoint spanning trees for all edges e of ( ( d + 1 2 ) − 1 ) H . (For a multigraph H and integer k we use kH to denote the multigraph obtained from H by replacing each edge e of H by k parallel copies of e .) This implies an affirmative answer to a conjecture of Connelly, Whiteley, and the first author. We also consider bar-joint frameworks and show, for each d ≥ 3 , an infinite family of graphs satisfying Hendrickson's well-known necessary conditions for generic global rigidity in R d (that is, ( d + 1 ) -connectivity and redundant rigidity) which are not generically globally rigid in R d . The existence of these families disproves a number of conjectures, due to Connelly, Connelly and Whiteley, and the third author, respectively. [ABSTRACT FROM AUTHOR]

Abstract A one-to-one correspondence between the infinitesimal motions of bar-joint frameworks in R d and those in S d is a classical observation by Pogorelov, and further connections among different rigidity models in various different spaces have been extensively studied. In this paper, we shall extend this line of research to include the infinitesimal rigidity of frameworks consisting of points and hyperplanes. This enables us to understand correspondences between point-hyperplane rigidity, classical bar-joint rigidity, and scene analysis. Among other results, we derive a combinatorial characterization of graphs that can be realized as infinitesimally rigid frameworks in the plane with a given set of points collinear. This extends a result by Jackson and Jordán, which deals with the case when three points are collinear. [ABSTRACT FROM AUTHOR]