The Computational Complexity of the ChordLink Model

Authors

  • Philipp Kindermann
  • Jan Sauer
  • Alexander Wolff

DOI:

https://doi.org/10.7155/jgaa.00643

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].

Downloads

Download data is not yet available.

Downloads

Published

2023-11-01

How to Cite

Kindermann, P., Sauer, J., & Wolff, A. (2023). The Computational Complexity of the ChordLink Model. Journal of Graph Algorithms and Applications, 27(9), 759–767. https://doi.org/10.7155/jgaa.00643

Issue

Section

Articles

Categories