Completely connected clustered graphs

DOI10.1016/J.JDA.2005.06.002MaRDI QIDQ2458931zbMATH OpenOpenAlexFDO

Authors Sabine Cornelsen, Dorothea Wagner

Publication date 5 November 2007

Published in Journal of Discrete Algorithms (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.jda.2005.06.002

zbMATH Keywords

planar drawing

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Graph representations (geometric and intersection representations, etc.) (05C62)

Review text

A clustered graph \((G,T,r)\) consists of a graph \(G=(V,E)\), a tree \(T\), and an inner vertex \(r\) of \(T\) such that the set of leaves of \(T\) is exactly \(V\). A clustered graph is said to be completely connected if every cluster, and also each complement of a cluster, induces a connected subgraph. A \(c\)-planar drawing of a clustered graph \((G,T,r)\) consists of a plane drawing of \(G\) and an inclusion representation of the rooted tree \((T,r)\) such that each edge crosses the boundary of the drawing of an inner vertex of \(T\) at most once. The authors' main result is that a completely connected clustered graph \((G,T,r)\) has a \(c\)-planar drawing if and only if \(G\) is planar. They also study the connection between the root \(r\) of \(T\) and the choice of the outer face for \(G\).

Recommendations

• Completely connected clustered graphs.
• scientific article; zbMATH DE number 1974122
• Drawing \(c\)-planar biconnected clustered graphs
• A new perspective on clustered planarity as a combinatorial embedding problem
• Graph Drawing

Cites work

• Completely connected clustered graphs.
• Drawing Clustered Graphs on an Orthogonal Grid
• Graph Drawing
• Graph drawing. 10th international symposium, GD 2002, Irvine, CA, USA, August 26--28, 2002. Revised papers
• How to draw the minimum cuts of a planar graph
• scientific article; zbMATH DE number 2084266 (Why is no real title available?)
• scientific article; zbMATH DE number 1189242 (Why is no real title available?)
• scientific article; zbMATH DE number 177556 (Why is no real title available?)
• scientific article; zbMATH DE number 1974122 (Why is no real title available?)
• scientific article; zbMATH DE number 1974123 (Why is no real title available?)
• Planarity for clustered graphs
• Straight-line drawing algorithms for hierarchical graphs and clustered graphs

Cited in

(15)

• Clustered planarity = flat clustered planarity
• Simpler algorithms for testing two-page book embedding of partitioned graphs
• C-planarity testing of embedded clustered graphs with bounded dual carving-width
• Relaxing the constraints of clustered planarity
• Straight-Line Rectangular Drawings of Clustered Graphs
• Clustered Planarity: Clusters with Few Outgoing Edges
• Computing Maximum C-Planar Subgraphs
• Beyond Clustered Planar Graphs
• Advances on testing C-planarity of embedded flat clustered graphs
• Completely connected 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
• Convex drawings of hierarchical planar graphs and clustered planar graphs

This page was built for publication: Completely connected clustered graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2458931)