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
Editorial actions: View Item 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:
  • 68-XX Computer science > 68Wxx Algorithms > 68W10 Parallel algorithms

  • 68-XX Computer science > 68Wxx Algorithms > 68W35 VLSI algorithms

  • 68-XX Computer science > 68Rxx Discrete mathematics in relation to computer science > 68R10 Graph theory

  • 68-XX Computer science > 68Qxx Theory of computing > 68Q25 Analysis of algorithms and problem complexity

    		•
    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