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: |
Download (706kB) | Preview |
---|---|
Editorial actions: | ![]() |
Content information:
Item Type: | Paper (Technical Report) |
---|---|
Citations: | 43 (Google Scholar) | 21 (Web of Science) |
Uncontrolled Keywords: | graph algorithms graph drawing hierarchical clustering parallel algorithms planar graphs |
Subjects: |
|
Divisions: | Institute of Computer Science |
Related URLs: |
Deposit Information:
ZAIK Number: | zpr98-325 |
---|---|
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 |