
Accession Number : ADA132538
Title : Planar Embedding of Planar Graphs,
Corporate Author : MASSACHUSETTS INST OF TECH CAMBRIDGE LAB FOR COMPUTER SCIENCE
Personal Author(s) : Dolev,Danny ; Leighton,Frank Thomson ; Trickey,Howard
PDF Url : ADA132538
Report Date : Feb 1983
Pagination or Media Count : 10
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 Nnode 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 Nucomplete for forests, and hence for more general types of graphs. (author)
Descriptors : *Computer graphics, Algorithms, Problem solving, Planar structures, Graphs, Theorems, Control theory
Subject Categories : Theoretical Mathematics
Distribution Statement : APPROVED FOR PUBLIC RELEASE