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(log2n) time using O(n+m) processors on a concurrent-read and concurrent-write (CRCW), parallel random access machine (PRAM) model, where n and m 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.