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

Personal Author(s) : Liotta, G. ; Tamassia, R. ; Tollis, I. G. ; Vocca, P.

PDF Url : ADA318524

Report Date : SEP 1996

Pagination or Media Count : 14

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.

Descriptors :   *GRAPHS, ALGORITHMS, RESOLUTION, COMPUTER GRAPHICS, HEURISTIC METHODS, AREA COVERAGE, ENGINEERING DRAWINGS, LINES(GEOMETRY).

Subject Categories : Numerical Mathematics

Distribution Statement : APPROVED FOR PUBLIC RELEASE