𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Rubber bands, convex embeddings and graph connectivity

✍ Scribed by N. Linial; L. Lovász; A. Wigderson

Publisher
Springer-Verlag
Year
1988
Tongue
English
Weight
660 KB
Volume
8
Category
Article
ISSN
0209-9683

No coin nor oath required. For personal study only.

📜 SIMILAR VOLUMES

On convex embeddings of planar 3-connect
On convex embeddings of planar 3-connected graphs
✍ Kelmans, Alexander 📂 Article 📅 2000 🏛 John Wiley and Sons 🌐 English ⚖ 167 KB 👁 2 views

A well-known Tutte's theorem claims that every 3-connected planar graph has a convex embedding into the plane. Tutte's arguments also show that, moreover, for every nonseparating cycle C of a 3-connected graph G, there exists a convex embedding of G such that C is a boundary of the outer face in thi

A connection between a convex programmin
A connection between a convex programming problem and the LYM property on perfect graphs
✍ Victor K. Wei 📂 Article 📅 1988 🏛 John Wiley and Sons 🌐 English ⚖ 772 KB

We derive three equivalent conditions on a perfect graph concerning the optimal solution of a convex programming problem, the length-width inequality, and the simultaneous vertex covering by cliques and anticliques. By combining proof techniques including Lagrangian dual, Dilworth's Theorem, and Kuh