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.
Original language | English (US) |
---|---|
Pages (from-to) | 114-140 |
Number of pages | 27 |
Journal | Theoretical Computer Science |
Volume | 846 |
DOIs | |
State | Published - Dec 18 2020 |
Externally published | Yes |
Keywords
- Graph drawing
- Point-set embedding
- Simultaneous embedding
ASJC Scopus subject areas
- Theoretical Computer Science
- General Computer Science