Rubber bands, convex embeddings and graph connectivity
From MaRDI portal
Publication:1121282
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)
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
