NDLI: Characterizing Graphs with Convex and Connected Cayley Configuration Spaces

Content Provider	Springer Nature Link
Author	Sitharam, Meera Gao, Heping
Copyright Year	2009
Abstract	We define and study exact, efficient representations of realization spaces Euclidean Distance Constraint Systems (EDCS), which include Linkages and Frameworks. These are graphs with distance assignments on the edges (frameworks) or graphs with distance interval assignments on the edges. Each representation corresponds to a choice of non-edge (squared) distances or Cayley parameters. The set of realizable distance assignments to the chosen parameters yields a parametrized Cayley configuration space. Our notion of efficiency is based on the convexity and connectedness of the Cayley configuration space, as well as algebraic complexity of sampling realizations, i.e., sampling the Cayley configuration space and obtaining a realization from the sample (parametrized) configuration. Significantly, we give purely graph-theoretic, forbidden minor characterizations for 2D and 3D EDCS that capture (i) the class of graphs that always admit efficient Cayley configuration spaces and (ii) the possible choices of representation parameters that yield efficient Cayley configuration spaces for a given graph. We show that the easy direction of the 3D characterization extends to arbitrary dimension d and is related to the concept of d-realizability of graphs. Our results automatically yield efficient algorithms for obtaining exact descriptions of the Cayley configuration spaces and for sampling realizations, without missing extreme or boundary realizations. In addition, our results are tight: we show counterexamples to obvious extensions.This is the first step in a systematic and graded program of combinatorial characterizations of efficient Cayley configuration spaces. We discuss several future theoretical and applied research directions.In particular, the results presented here are the first to completely characterize EDCS that have connected, convex and efficient Cayley configuration spaces, based on precise and formal measures of efficiency. It should be noted that our results do not rely on genericity of the EDCS. Some of our proofs employ an unusual interplay of (a) classical analytic results related to positive semi-definiteness of Euclidean distance matrices, with (b) recent forbidden minor characterizations and algorithms related to d-realizability of graphs. We further introduce a novel type of restricted edge contraction or reduction to a graph minor, a “trick” that we anticipate will be useful in other situations.
Starting Page	594
Ending Page	625
Page Count	32
File Format	PDF
ISSN	01795376
Journal	Discrete & Computational Geometry
Volume Number	43
Issue Number	3
e-ISSN	14320444
Language	English
Publisher	Springer-Verlag
Publisher Date	2009-04-03
Publisher Place	New York
Access Restriction	One Nation One Subscription (ONOS)
Subject Keyword	Underconstrained Geometric Constraint System Mechanism Cayley configuration space Combinatorial rigidity Linkage Framework Graph Minor Graph Characterization Distance geometry Convex Semidefinite and Linear programming Algebraic Complexity Computational Mathematics and Numerical Analysis Combinatorics
Content Type	Text
Resource Type	Article
Subject	Discrete Mathematics and Combinatorics Theoretical Computer Science Computational Theory and Mathematics Geometry and Topology

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

Characterizing 1-dof Henneberg-I graphs with efficient configuration spaces

Characterizing the Universal Rigidity of Generic Frameworks

Characterizing graphs with convex and connected configuration spaces

On the dual graph of Cohen-Macaulay algebras

Strong Isoperimetric Inequalities and Combinatorial Curvatures on Multiply Connected Planar Graphs

Two-distance transitive normal Cayley graphs

Tetravalent half-arc-transitive p-graphs

Cayley graphs on abelian groups

Configuration Spaces: Geometry, Combinatorics and Topology

Characterizing Graphs with Convex and Connected Cayley Configuration Spaces

Similar Documents

Characterizing 1-dof Henneberg-I graphs with efficient configuration spaces

Characterizing the Universal Rigidity of Generic Frameworks

Characterizing graphs with convex and connected configuration spaces

On the dual graph of Cohen-Macaulay algebras

Strong Isoperimetric Inequalities and Combinatorial Curvatures on Multiply Connected Planar Graphs

Two-distance transitive normal Cayley graphs

Tetravalent half-arc-transitive p-graphs

Cayley graphs on abelian groups

Configuration Spaces: Geometry, Combinatorics and Topology

Characterizing Graphs with Convex and Connected Cayley Configuration Spaces