A linear time algorithm to recognize clustered planar graphs and its parallelization
The author gives 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\) may be embedded into the plane such that no cluster has a hole. The algorithm is based on the decomposition of the graph into its 3-connected components. The major idea is that the clusters are weighted by their sizes and each edge is weighted by the weight of the cluster of minimum size that contains it. The result is an improvement to the \(O(n^2)\)-algorithm of Q.-W. Feng et al. For the entire collection see [Zbl 0889.00032].
- On embedding a cycle in a plane graph
- Clustered planarity = flat clustered planarity
- How to draw the minimum cuts of a planar graph
- C-planarity testing of embedded clustered graphs with bounded dual carving-width
- Relaxing the constraints of clustered planarity
- Completely connected clustered graphs
- Straight-Line Rectangular Drawings of Clustered Graphs
- Clustered Planarity: Clusters with Few Outgoing Edges
- Computing Maximum C-Planar Subgraphs
- Clustered Planarity: Embedded Clustered Graphs with Two-Component Clusters
- Beyond Clustered Planar Graphs
- Advances on testing C-planarity of embedded flat clustered graphs
- Straight-line rectangular drawings of clustered graphs
- Constrained planarity in practice -- engineering the synchronized planarity algorithm
- Drawing \(c\)-planar biconnected clustered graphs
- A new perspective on clustered planarity as a combinatorial embedding problem
This page was built for publication: A linear time algorithm to recognize clustered planar graphs and its parallelization
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3839007)
