## 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