Accession Number:

ADA109603

Title:

On Linear Area Embedding of Planar Graphs,

Descriptive Note:

Corporate Author:

STANFORD UNIV CA DEPT OF COMPUTER SCIENCE

Personal Author(s):

Report Date:

1981-09-01

Pagination or Media Count:

22.0

Abstract:

Planar embedding with minimal area of graphs on an integer grid is one of the major issues in VLSI. Valiant V gave an algorithm to construct a planar embedding for trees in linear area he also proved that there are planar graphs that require quadratic area. We give an algorithm to embed outerplanar graphs in linear area. We extend this algorithm to work for every planar graph that has the following property for every vertex there exists a path of length less than K to the exterior face, where K is a constant. Finally, finding a minimal embedding area is shown to be NP-complete for forests, and hence more general types of graphs. Author

Subject Categories:

  • Electrical and Electronic Equipment
  • Theoretical Mathematics

Distribution Statement:

APPROVED FOR PUBLIC RELEASE