Placing segments on parallel arcs
Research output: Chapters, Conference Papers, Creative and Literary Works › RGC 32 - Refereed conference paper (with host publication) › peer-review
Author(s)
Related Research Unit(s)
Detail(s)
| Original language | English |
|---|---|
| Title of host publication | Combinatorial Algorithms |
| Subtitle of host publication | 29th International Workshop, IWOCA 2018, Proceedings |
| Editors | Costas Iliopoulos, Hon Wai Leong, Wing-Kin Sung |
| Publisher | Springer International Publishing AG |
| Pages | 298-310 |
| ISBN (electronic) | 9783319946672 |
| ISBN (print) | 9783319946665 |
| Publication status | Published - 2018 |
Publication series
| Name | Lecture Notes in Computer Science |
|---|---|
| Volume | 10979 |
| ISSN (Print) | 0302-9743 |
| ISSN (electronic) | 1611-3349 |
Conference
| Title | 29th International Workshop on Combinatorial Algorithms, IWOCA 2018 |
|---|---|
| Place | Singapore |
| City | Singapore |
| Period | 16 - 19 July 2018 |
Link(s)
Abstract
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. Our algorithms have been implemented in JavaScript and made available at https://github.com/kalngyk/segmentplacer.
Research Area(s)
- Approximation algorithm, Segment placement, Visualization
Citation Format(s)
Placing segments on parallel arcs. / Ng, Yen Kaow; Jia, Wenlong; Li, Shuai Cheng.
Combinatorial Algorithms: 29th International Workshop, IWOCA 2018, Proceedings. ed. / Costas Iliopoulos; Hon Wai Leong; Wing-Kin Sung. Springer International Publishing AG, 2018. p. 298-310 (Lecture Notes in Computer Science; Vol. 10979).
Combinatorial Algorithms: 29th International Workshop, IWOCA 2018, Proceedings. ed. / Costas Iliopoulos; Hon Wai Leong; Wing-Kin Sung. Springer International Publishing AG, 2018. p. 298-310 (Lecture Notes in Computer Science; Vol. 10979).
Research output: Chapters, Conference Papers, Creative and Literary Works › RGC 32 - Refereed conference paper (with host publication) › peer-review
