On Linear Area Embedding of Planar Graphs,

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)

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Sep 01, 1981
Accession Number
ADA109603

Entities

People

  • Danny Dolev
  • Howard Trickey

Organizations

  • Stanford University

Tags

Communities of Interest

  • Air Platforms

DTIC Thesaurus Topics

  • Algorithms
  • Cartesian Coordinates
  • Computer Science
  • Computers
  • Construction
  • Coordinate Systems
  • Crossings
  • Embedding
  • Graph Theory
  • Grids
  • Information Processing
  • Orientation (Direction)
  • Plastic Explosives
  • Simulations
  • Trees (Data Structures)
  • Triangles
  • Triangulation

Fields of Study

  • Mathematics

Readers

  • Graph Algorithms and Convex Optimization.