Accession Number:

ADA318524

Title:

Area Requirement of Gabriel Drawings.

Descriptive Note:

Technical rept.,

Corporate Author:

BROWN UNIV PROVIDENCE RI CENTER FOR COMPUTER AND INFORMATION SCIENCES

Report Date:

1996-09-01

Pagination or Media Count:

14.0

Abstract:

In this paper we investigate the area requirement of proximity drawings and we prove an exponential lower bound. Namely, our main contribution is to show the existence of a class of Gabriel-drawable graphs that require exponential area for any Gabriel drawing and any resolution rule. Also, we extend the result to an infinite class of proximity drawings.

Subject Categories:

  • Numerical Mathematics

Distribution Statement:

APPROVED FOR PUBLIC RELEASE