Area Requirement of Gabriel Drawings.

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.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Sep 01, 1996
Accession Number
ADA318524

Entities

People

  • G. Liotta
  • I. G. Tollis
  • P. Vocca
  • R. Tamassia

Organizations

  • Brown University

Tags

DTIC Thesaurus Topics

  • Abstracts
  • Algorithms
  • Classification
  • Computer Science
  • Computer Vision
  • Computers
  • Geographic Information Systems
  • Geometry
  • Information Systems
  • Military Research
  • Notation
  • Pattern Recognition
  • Recognition
  • Three Dimensional
  • Triangles
  • Universities

Fields of Study

  • Mathematics

Readers

  • Graph Algorithms and Convex Optimization.
  • Systems Analysis and Design