Home | Issues | About JGAA | Instructions for Authors |
DOI: 10.7155/jgaa.00643
The Computational Complexity of the ChordLink Model
Vol. 27, no. 9, pp. 759-767, 2023. Concise paper.
Abstract 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].
This work is licensed under the terms of the CC-BY license.
|
Submitted: June 2023.
Accepted: October 2023.
Final: November 2023.
Published: November 2023.
Communicated by
Giuseppe Liotta
|
Journal Supporters
|