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. 213226] and the algorithm of Lengauer [Hierarchical Planarity Testing Algorithm, Journal of the ACM 36 (1989), pp. 474509].
Actions:
Download: 
Postscript
Download (706kB)  Preview 

Editorial actions:  View Item (Login required) 
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:  zpr98325 

Depositing User:  Archive Admin 
Date Deposited:  02 Apr 2001 00:00 
Last Modified:  19 Dec 2011 09:45 
URI:  http://earchive.informatik.unikoeln.de/id/eprint/325 