Planar Embedding of Planar Graphs,

Abstract

Planar embedding with minimal area of graphs on an integer grid is an interesting problem in VLSI (Very Large Scale Integrated) theory. Valiant gave an algorithm to construct a planar embeddding for trees in linear area; he also proved that there are planar graphs that require quadratic area. We fill in a spectrum between Valiant's results by showing that an N-node planar graphs has a planar embedding with area 0(NF), where F is a bound on the path length from any node to the exterior face. In particular, an outerplanar graph can be embedded without crossovers in linear area. This bound is tight, up to constant factors: for any N and F, there exist graphs requiring omega(NF) area for planar embedding. Also, finding a minimal embedding area is shown to be Nu-complete for forests, and hence for more general types of graphs. (author)

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Feb 01, 1983
Accession Number
ADA132538

Entities

People

  • Danny Dolev
  • Frank Thomson Leighton
  • Howard Trickey

Organizations

  • Massachusetts Institute of Technology

Tags

Communities of Interest

  • Air Platforms

DTIC Thesaurus Topics

  • Air Force
  • Algorithms
  • Aspect Ratio
  • Computer Science
  • Computers
  • Contracts
  • Embedding
  • Massachusetts
  • Mathematics
  • Polynomials
  • Separators
  • Spectra
  • Topology
  • Universities

Readers

  • Graph Algorithms and Convex Optimization.