Parallel recognition algorithms for chordal_planar graphs and planar k-trees

摘要

This paper presents parallel algorithms for recognizing chordal-planar graphs and planar k-trees. Both the algorithms run in O(log(2) n) time using O(n + m) processors on a concurrent-read and concurrent-write (CRCW), parallel random access machine (PRAM) model, where n and in are, respectively, the number of nodes and edges in the graph. The novelty of our chordal-planar graph recognition algorithm lies in that it is based on an elegant structural characterization of chordal-planar graphs proposed in this paper. Moreover, it is simpler than separately testing chordality and planarity. Our planar k-trees recognition algorithm is based on a new characterization of k-trees presented in this paper. (c) 2005 Elsevier Inc. All rights reserved.