Contracting planar graphs efficiently in parallel

Martin Fürer, Balaji Raghavachari

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

We describe a new technique for contracting planar graphs which generalizes the tree contraction technique introduced by Miller and Reif. Our algorithm contracts a given planar graph in O(log n) rounds to one with a constant number of vertices. We use this technique to give an efficient NC solution to the following problem. It is known that a planar graph with n ≥ 3 vertices has a straight-line embedding on an n — 2 by n — 2 grid. We show that such an embedding is computable in O(log2 n log* n) time using O(n) processors on a CREW PRAM.

Original languageEnglish (US)
Title of host publicationFoundations of Software Technology and Theoretical Computer Science - 11th Conference, Proceedings
EditorsSomenath Biswas, Kesav V. Nori
PublisherSpringer Verlag
Pages319-335
Number of pages17
ISBN (Print)9783540549673
DOIs
StatePublished - 1991
Event11th Conference on Foundations of Software Technology and Theoretical Computer Science, FST and TCS, 1991 - New Delhi, India
Duration: Dec 17 1991Dec 19 1991

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume560 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Other

Other11th Conference on Foundations of Software Technology and Theoretical Computer Science, FST and TCS, 1991
Country/TerritoryIndia
CityNew Delhi
Period12/17/9112/19/91

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • General Computer Science

Cite this