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.

DI BATTISTA, G., Frati, F., Patrignani, M., Tais, M. (2021). Schematic Representation of Large Biconnected Graphs. JOURNAL OF GRAPH ALGORITHMS AND APPLICATIONS, 25(1), 311-352 [10.7155/JGAA.00560].

Schematic Representation of Large Biconnected Graphs

Giuseppe Di Battista;Fabrizio Frati;Maurizio Patrignani;
2021-01-01

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.
DI BATTISTA, G., Frati, F., Patrignani, M., Tais, M. (2021). Schematic Representation of Large Biconnected Graphs. JOURNAL OF GRAPH ALGORITHMS AND APPLICATIONS, 25(1), 311-352 [10.7155/JGAA.00560].
File in questo prodotto:
File Dimensione Formato  
Published.pdf

accesso aperto

Tipologia: Versione Editoriale (PDF)
Licenza: DRM non definito
Dimensione 1.34 MB
Formato Adobe PDF
1.34 MB Adobe PDF Visualizza/Apri

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11590/387997
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 1
  • ???jsp.display-item.citation.isi??? ND
social impact