Placing Segments on Parallel Arcs

摘要

In this paper we consider the problem of arranging segments on parallel arcs drawn within a circular sector, to provide foundational work for the visualization of genomic regions in the study of pathogenic integration. The arcs as well as the start and end angles for each segment are pre-defined; our problem is to place each segment on an arc without having them overlap. There are no segments that span multiple arcs. For visualization purpose, the segments are to be easily distinguishable. To achieve that we consider various criteria that in a sense, place segments as far as possible from each other-for instance, maximizing the sum of inter-center distances between nearest segments. We show complexity results for some of the resultant problems, while providing approximation or heuristic solutions for others.