Algorithms - ESA 2003

DOI10.1007/b13632zbMath1266.05162OpenAlexW1827234103WikidataQ60299159 ScholiaQ60299159MaRDI QIDQ5897236

Alex R. Berg, Tibor Jordán

Publication date: 3 March 2010

Published in: Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/b13632

zbMATH Keywords

algorithmbipartite graphsscene analysisgraph families\(M\)-connected componentd-sharp subgraphsd-tight bipartite graphsedge countsglobally rigid componentparallel drawingredundantly rigid componentrigid component

Mathematics Subject Classification ID

Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph algorithms (graph-theoretic aspects) (05C85) Machine vision and scene understanding (68T45) Graph representations (geometric and intersection representations, etc.) (05C62)

Related Items (42)

A characterisation of the generic rigidity of 2-dimensional point-line frameworks ⋮ The Steiner Problem for Count Matroids ⋮ Sparse Graphs and an Augmentation Problem ⋮ Frameworks with Coordinated Edge Motions ⋮ Enumerating non-crossing minimally rigid frameworks ⋮ Source location with rigidity and tree packing requirements ⋮ New upper bounds for the number of embeddings of minimally rigid graphs ⋮ Good orientations of unions of edge‐disjoint spanning trees ⋮ A necessary condition for generic rigidity of bar‐and‐joint frameworks in d‐space ⋮ Exploring the rigidity of planar configurations of points and rods ⋮ Cycle-based formulations in distance geometry ⋮ Augmenting the rigidity of a graph in \(\mathbb R^{2}\) ⋮ Global rigidity of direction-length frameworks ⋮ Globally rigid augmentation of minimally rigid graphs in \(\mathbb{R}^2\) ⋮ Operations preserving the global rigidity of graphs and frameworks in the plane ⋮ Necessary conditions for the generic global rigidity of frameworks on surfaces ⋮ Equivalent realisations of a rigid graph ⋮ Minimum Cost Globally Rigid Subgraphs ⋮ Rigid cylindrical frameworks with two coincident points ⋮ Fast enumeration algorithms for non-crossing geometric graphs ⋮ Enumerating constrained non-crossing minimally rigid frameworks ⋮ Rigidity for sticky discs ⋮ Pebble game algorithms and sparse graphs ⋮ Efficient algorithms for the \(d\)-dimensional rigidity matroid of sparse graphs ⋮ A rooted-forest partition with uniform vertex demand ⋮ Globally rigid circuits of the direction-length rigidity matroid ⋮ Bounded direction-length frameworks ⋮ Rigidity, global rigidity, and graph decomposition ⋮ Unnamed Item ⋮ Rigid two-dimensional frameworks with three collinear points ⋮ Connected rigidity matroids and unique realizations of graphs ⋮ Mixed volume techniques for embeddings of Laman graphs ⋮ Rigid tensegrity labelings of graphs ⋮ Sparse hypergraphs and pebble game algorithms ⋮ Sparsity-certifying graph decompositions ⋮ Rigid realizations of graphs on small grids ⋮ Global rigidity of generic frameworks on the cylinder ⋮ Globally Linked Pairs of Vertices in Rigid Frameworks ⋮ Rigid two-dimensional frameworks with two coincident points ⋮ Rigid block and hole graphs with a single block ⋮ Sparse graphs and an augmentation problem ⋮ Gain-sparsity and symmetry-forced rigidity in the plane

This page was built for publication: Algorithms - ESA 2003