# A Linear Time Algorithm to Recognize Clustered Planar Graphs and its Parallelization

Dahlhaus, Elias
(1998)
*A Linear Time Algorithm to Recognize Clustered Planar Graphs and its Parallelization.*

Technical Report
, 18 p.

## Abstract

We develop a linear time algorithm for the following problem: Given a graph G and a hierarchical clustering of the vertices, such that all clusters induce connected subgraphs, determine whether G can be embedded into the plane, such that no cluster has a hole. This is an improvement to the quadratic time algorithm of Q.W. Feng et al. [Planarity for Clustered Graphs, ESA Åœ96, Springer LNCS 979, pp. 213-226] and the algorithm of Lengauer [Hierarchical Planarity Testing Algorithm, Journal of the ACM 36 (1989), pp. 474-509].

Actions:

Download: |
Postscript
Download (706kB) | Preview |
---|---|

Export as: | [error in script] |

Editorial actions: |
View Item (Login required) |

Content information:

Deposit Information:

ZAIK Number: | [error in script] |
---|---|

Depositing User: | Archive Admin |

Date Deposited: | 02 Apr 2001 00:00 |

Last Modified: | 19 Dec 2011 09:45 |

URI: | http://e-archive.informatik.uni-koeln.de/id/eprint/325 |