Schematic representation of large biconnected graphs

DOI10.7155/JGAA.00560MaRDI QIDQ4994348zbMATH OpenOpenAlexFDO

Authors Giuseppe Di Battista, Fabrizio Frati, Maurizio Patrignani, Marco Tais

Publication date 17 June 2021

Published in Journal of Graph Algorithms and Applications (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://arxiv.org/abs/2008.09414

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Graph representations (geometric and intersection representations, etc.) (05C62)

Abstract: Suppose that a biconnected graph is given, consisting of a large component plus several other smaller components, each separated from the main component by a separation pair. We investigate the existence and the computation time of schematic representations of the structure of such a graph where the main component is drawn as a disk, the vertices that take part in separation pairs are points on the boundary of the disk, and the small components are placed outside the disk and are represented as non-intersecting lunes connecting their separation pairs. We consider several drawing conventions for such schematic representations, according to different ways to account for the size of the small components. We map the problem of testing for the existence of such representations to the one of testing for the existence of suitably constrained $1$-page book-embeddings and propose several polynomial-time algorithms.

Recommendations

• scientific article; zbMATH DE number 2038697
• scientific article; zbMATH DE number 1693473
• scientific article; zbMATH DE number 3981211
• Planarity-preserving clustering and embedding for large planar graphs
• scientific article; zbMATH DE number 1500683

Cites work

• scientific article; zbMATH DE number 4049084 (Why is no real title available?)
• scientific article; zbMATH DE number 3290993 (Why is no real title available?)
• Characterizations of outerplanar graphs
• Linear algorithms to recognize outerplanar and maximal outerplanar graphs
• Networks
• One-Page Book Embedding under Vertex-Neighborhood Constraints
• Schematic Representation of Biconnected Graphs
• The book thickness of a graph

Cited in

(1)

• Schematic Representation of Biconnected Graphs

Describes a project that uses

Uses Software

• Algorithm 447
• SNAP

This page was built for publication: Schematic representation of large biconnected graphs

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