On the curve complexity of 3-colored point-set embeddings

Di Giacomo, Emilio, Gasieniec, Leszek ORCID: 0000-0003-1809-9814, Liotta, Giuseppe and Navarra, Alfredo (2020) On the curve complexity of 3-colored point-set embeddings. Theoretical Computer Science, 846. pp. 114-140.

Text
journal_3coloredPSE.pdf - Author Accepted Manuscript
Download (1MB) | Preview

Official URL: http://dx.doi.org/10.1016/j.tcs.2020.09.027

Abstract

We establish new results on the curve complexity of k-colored point-set embeddings when k=3. We show that there exist 3-colored caterpillars with only three independent edges whose 3-colored point-set embeddings may require [Formula presented] bends on [Formula presented] edges. This settles an open problem by Badent et al. [5] about the curve complexity of point set embeddings of k-colored trees and it extends a lower bound by Pach and Wenger [35] to the case that the graph only has O(1) independent edges. Concerning upper bounds, we prove that any 3-colored path admits a 3-colored point-set embedding with curve complexity at most 4. In addition, we introduce a variant of the k-colored simultaneous embeddability problem and study its relationship with the k-colored point-set embeddability problem.

Item Type:	Article
Uncontrolled Keywords:	Graph drawing, Point-set embedding, Simultaneous embedding
Depositing User:	Symplectic Admin
Date Deposited:	07 Dec 2020 08:50
Last Modified:	18 Jan 2023 23:19
DOI:	10.1016/j.tcs.2020.09.027
Related URLs:	Author Publisher
URI:	https://livrepository.liverpool.ac.uk/id/eprint/3109200