Geodesic
Schematic Representation of Large Biconnected Graphs
Journal of Graph Algorithms and Applications, Tome 25 (2021) no. 1, pp. 311-352.

Voir la notice de l'article provenant de la source Journal of Graph Algorythms and Applications website

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. 
@article{JGAA_2021_25_1_a13,
     author = {Giuseppe Di Battista and Fabrizio Frati and Maurizio Patrignani and Marco Tais},
     title = {Schematic {Representation} of {Large} {Biconnected} {Graphs}},
     journal = {Journal of Graph Algorithms and Applications},
     pages = {311--352},
     publisher = {mathdoc},
     volume = {25},
     number = {1},
     year = {2021},
     doi = {10.7155/jgaa.00560},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00560/}
}
TY  - JOUR
AU  - Giuseppe Di Battista
AU  - Fabrizio Frati
AU  - Maurizio Patrignani
AU  - Marco Tais
TI  - Schematic Representation of Large Biconnected Graphs
JO  - Journal of Graph Algorithms and Applications
PY  - 2021
SP  - 311
EP  - 352
VL  - 25
IS  - 1
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00560/
DO  - 10.7155/jgaa.00560
LA  - en
ID  - JGAA_2021_25_1_a13
ER  - 
%0 Journal Article
%A Giuseppe Di Battista
%A Fabrizio Frati
%A Maurizio Patrignani
%A Marco Tais
%T Schematic Representation of Large Biconnected Graphs
%J Journal of Graph Algorithms and Applications
%D 2021
%P 311-352
%V 25
%N 1
%I mathdoc
%U http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00560/
%R 10.7155/jgaa.00560
%G en
%F JGAA_2021_25_1_a13
Giuseppe Di Battista; Fabrizio Frati; Maurizio Patrignani; Marco Tais. Schematic Representation of Large Biconnected Graphs. Journal of Graph Algorithms and Applications, Tome 25 (2021) no. 1, pp. 311-352. doi : 10.7155/jgaa.00560. http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00560/

Cité par Sources :