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.
Users
Please
log in to take part in the discussion (add own reviews or comments).