Geodesic
The Computational Complexity of the ChordLink Model
Journal of Graph Algorithms and Applications, Tome 27 (2023) no. 9, pp. 759-767.

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

In order to visualize well-clustered graphs with many intra-cluster but few inter-cluster edges, hybrid approaches have been proposed. For example, ChordLink draws the clusters as chord diagrams and embeds these into a node-link diagram that represents the overall structure of the clustered graph. The ChordLink approach consists of four steps; node replication, node permutation, node merging, and chord insertion. In this paper, we focus on the optimization problems defined by two of these steps. We show that the decision version of the problem defined by node permutation is NP-complete and present an efficient algorithm for a special case. For chord insertion, we show that it is NP-complete to decide whether a crossing-free placement of the chords exists. Moreover, it is APX-hard to minimize the number of crossings among the chords. Our results answer an open question posed by Angori, Didimo, Montecchiani, Pagliuca, and Tappini, who introduced ChordLink [TVCG 2021]. 
@article{JGAA_2023_27_9_a0,
     author = {Philipp Kindermann and Jan Sauer and Alexander Wolff},
     title = {The {Computational} {Complexity} of the {ChordLink} {Model}},
     journal = {Journal of Graph Algorithms and Applications},
     pages = {759--767},
     publisher = {mathdoc},
     volume = {27},
     number = {9},
     year = {2023},
     doi = {10.7155/jgaa.00643},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00643/}
}
TY  - JOUR
AU  - Philipp Kindermann
AU  - Jan Sauer
AU  - Alexander Wolff
TI  - The Computational Complexity of the ChordLink Model
JO  - Journal of Graph Algorithms and Applications
PY  - 2023
SP  - 759
EP  - 767
VL  - 27
IS  - 9
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00643/
DO  - 10.7155/jgaa.00643
LA  - en
ID  - JGAA_2023_27_9_a0
ER  - 
%0 Journal Article
%A Philipp Kindermann
%A Jan Sauer
%A Alexander Wolff
%T The Computational Complexity of the ChordLink Model
%J Journal of Graph Algorithms and Applications
%D 2023
%P 759-767
%V 27
%N 9
%I mathdoc
%U http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00643/
%R 10.7155/jgaa.00643
%G en
%F JGAA_2023_27_9_a0
Philipp Kindermann; Jan Sauer; Alexander Wolff. The Computational Complexity of the ChordLink Model. Journal of Graph Algorithms and Applications, Tome 27 (2023) no. 9, pp. 759-767. doi : 10.7155/jgaa.00643. http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00643/

Cité par Sources :