@inproceedings{ed44b1a777934356b67afbd563063e25,
title = "Contracting planar graphs efficiently in parallel",
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.",
author = "Martin F{\"u}rer and Balaji Raghavachari",
note = "Funding Information: t This work was supported in part by the NSF under grant CCR-8805978. Publisher Copyright: {\textcopyright} Springer-Verlag Berlin Heidelberg 1991.; 11th Conference on Foundations of Software Technology and Theoretical Computer Science, FST and TCS, 1991 ; Conference date: 17-12-1991 Through 19-12-1991",
year = "1991",
doi = "10.1007/3-540-54967-6_78",
language = "English (US)",
isbn = "9783540549673",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
publisher = "Springer Verlag",
pages = "319--335",
editor = "Somenath Biswas and Nori, {Kesav V.}",
booktitle = "Foundations of Software Technology and Theoretical Computer Science - 11th Conference, Proceedings",
address = "Germany",
}