Rubber bands, convex embeddings and graph connectivity

DOI10.1007/BF02122557zbMath0674.05046WikidataQ56555114 ScholiaQ56555114MaRDI QIDQ1121282

Avi Wigderson, László Lovász, Nathan Linial

Publication date: 1988

Published in: Combinatorica (Search for Journal in Brave)

zbMATH Keywords

vertex connected graphs

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Convex sets in (n) dimensions (including convex hypersurfaces) (52A20) Connectivity (05C40)

Related Items

Directed \(s\)-\(t\) numberings, rubber bands, and testing digraph \(k\)-vertex connecitivity, Book review of: L. Lovász, Graphs and geometry, The geometry of graphs and some of its algorithmic applications, Greedy drawings of triangulations, From Tutte to Floater and Gotsman: on the resolution of planar straight-line drawings and morphs, Singular spaces of matrices and their application in combinatorics, Solution of the propeller conjecture in \(\mathbb R^3\), Tutte's barycenter method applied to isotopies, Connections between graphs and matrix spaces, Non-degeneracy of the harmonic structure on Sierpiński gaskets, Bounds and algorithms for geodetic hulls, An \(O(n+m)\) certifying triconnnectivity algorithm for Hamiltonian graphs, Certifying algorithms, Representations of graphs and networks (coding, layouts and embeddings), Finding densest \(k\)-connected subgraphs, Certifying 3-edge-connectivity, Unnamed Item, Computing vertex-disjoint paths in large graphs using MAOs, Orthogonal representations and connectivity of graphs, On Finding Directed Trees with Many Leaves, On a conjecture related to geometric routing, Discrete one-forms on meshes and applications to 3D mesh parameterization

Cites Work

• Unnamed Item
• Unnamed Item
• On computing the determinant in small parallel time using a small number of processors
• Rigidity and energy
• Computing an st-numbering
• Gammoids and transversal matroids
• Dynamic parallel memories
• Finding the Vertex Connectivity of Graphs
• Fast Probabilistic Algorithms for Verification of Polynomial Identities
• On the Asymptotic Complexity of Matrix Multiplication
• SYMMETRIZED FORM OF P. HALL'S THEOREM ON DISTINCT REPRESENTATIVES
• How to Draw a Graph