✦ LIBER ✦

Drawing K2,n: A lower bound

✍ Scribed by Therese Biedl; Timothy M. Chan; Alejandro López-Ortiz

Book ID: 104136876
Publisher: Elsevier Science
Year: 2003
Tongue: English
Weight: 81 KB
Volume: 85
Category: Article
ISSN: 0020-0190
DOI: 10.1016/s0020-0190(02)00433-7

No coin nor oath required. For personal study only.

✦ Synopsis

We give a tradeoff theorem between the area and the aspect ratio required by any planar straight-line drawing of K 2,n on the integer lattice. In particular we show that if the drawing is contained in a rectangle of area O(n) then the rectangle must have aspect ratio (n), and conversely, if the aspect ratio is O(1) then the area must be (n 2 / log 2 n).

📜 SIMILAR VOLUMES

Lower bounds for complete {k; n}-ARCS

✍ Aiden A Bruen 📂 Article 📅 1982 🏛 Elsevier Science 🌐 English ⚖ 84 KB

Some lower bounds of the Ramsey numbers

Some lower bounds of the Ramsey numbers n(k, k)

✍ James P Burling; Steven W Reyner 📂 Article 📅 1972 🏛 Elsevier Science 🌐 English ⚖ 65 KB

A lower bound for n-diameters

✍ I. F. Sharygin 📂 Article 📅 1972 🏛 SP MAIK Nauka/Interperiodica 🌐 English ⚖ 217 KB

A New Lower Bound Theorem for Combinator

A New Lower Bound Theorem for Combinatorial 2k-Manifolds

✍ Eric Sparla 📂 Article 📅 1999 🏛 Springer Japan 🌐 English ⚖ 232 KB

A lower bound for the permanent on Un(k,

A lower bound for the permanent on Un(k, k)

✍ D.J Hartfiel; J.W Crosby 📂 Article 📅 1972 🏛 Elsevier Science 🌐 English ⚖ 239 KB

A matrix lower bound

✍ Joseph F. Grcar 📂 Article 📅 2010 🏛 Elsevier Science 🌐 English ⚖ 293 KB

Four essentially different interpretations of a lower bound for linear operators are shown to be equivalent for matrices (involving inequalities, convex sets, minimax problems, and quotient spaces). Properties stated by von Neumann in a restricted case are satisfied by the lower bound. Applications