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: [img] Postscript
Download (706kB) | Preview
Export as: [error in script]
Editorial actions: View Item View Item (Login required)
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