Planar grid embedding in linear time

The authors consider the problem of constructing a planar grid embedding for G, where G is a planar graph with n vertices, which maps vertices to distinct grid points and edges to nonintersecting grid paths. A new algorithm is presented that runs in O(n) time and produces grid embeddings with the fo...

Full description

Saved in:
Bibliographic Details
Published in:IEEE transactions on circuits and systems 1989-09, Vol.36 (9), p.1230-1234
Main Authors: Tamassia, R., Tollis, I.G.
Format: Article
Language:English
Subjects:
Chaos
Circuit analysis
Circuit theory
Combinatorics
Combinatorics. Ordered structures
Differential equations
Eigenvalues and eigenfunctions
Exact sciences and technology
Graph theory
Graphics
Jacobian matrices
Mathematics
Nonlinear systems
Piecewise linear techniques
Sciences and techniques of general use
Vectors
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:The authors consider the problem of constructing a planar grid embedding for G, where G is a planar graph with n vertices, which maps vertices to distinct grid points and edges to nonintersecting grid paths. A new algorithm is presented that runs in O(n) time and produces grid embeddings with the following properties: (1) the total number of bends is at most 2.4n+2; (2) the number of bends along each edge is at most 4; (3) the length of every edge is O(n); and (4) the area of the embedding is O(n/sup 2/).< >
ISSN:0098-4094
1558-1276
DOI:10.1109/31.34669