Drawing K2,n: A lower bound

Therese Biedl, Timothy M. Chan, Alejandro López-Ortiz

Research output: Contribution to journalArticlepeer-review

Abstract

A tradeoff theorem between the area and the aspect ratio required by any planar straight-line drawing of K2,n on the integer lattice was presented. It was shown that if the drawing is contained in a rectangle of area O(n), then the rectangle must have aspect ratio ω(n). Also, if the aspect ratio is O(1), then the area must be ω(n2/log2n).

Original languageEnglish (US)
Pages (from-to)303-305
Number of pages3
JournalInformation Processing Letters
Volume85
Issue number6
DOIs
StatePublished - Mar 31 2003
Externally publishedYes

Keywords

  • Aspect ratio
  • Computational geometry
  • Graph drawing
  • Planar embeddings

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Signal Processing
  • Information Systems
  • Computer Science Applications

Fingerprint Dive into the research topics of 'Drawing K<sub>2,n</sub>: A lower bound'. Together they form a unique fingerprint.

Cite this