Let G be a planar graph whose vertices are colored either red or blue and let S be a set of points having as many red (resp. blue) points as the red (resp. blue) vertices of G. A 2-colored point-set embedding of G on S is a planar drawing that maps each red (resp. blue) vertex of G to a red (resp. blue) point of S. We show that there exist partial 2-trees that are properly 2-colored (i.e., they are 2-colored with no two adjacent vertices have the same color), whose point-set embeddings may require linearly many bends on linearly many edges. For a contrast, we show that two bends per edge are sufficient for 2-colored point-set embedding of properly 2-colored outerplanar graphs. For separable point sets this bound reduces to one, which is worst-case optimal. If the 2-coloring of the outerplanar graph is not proper, three bends per edge are sufficient and one bend per edge (which is worst-case optimal) is sufficient for caterpillars.

2-colored point-set embeddings of partial 2-trees

Di Giacomo E.;Liotta G.
2021

Abstract

Let G be a planar graph whose vertices are colored either red or blue and let S be a set of points having as many red (resp. blue) points as the red (resp. blue) vertices of G. A 2-colored point-set embedding of G on S is a planar drawing that maps each red (resp. blue) vertex of G to a red (resp. blue) point of S. We show that there exist partial 2-trees that are properly 2-colored (i.e., they are 2-colored with no two adjacent vertices have the same color), whose point-set embeddings may require linearly many bends on linearly many edges. For a contrast, we show that two bends per edge are sufficient for 2-colored point-set embedding of properly 2-colored outerplanar graphs. For separable point sets this bound reduces to one, which is worst-case optimal. If the 2-coloring of the outerplanar graph is not proper, three bends per edge are sufficient and one bend per edge (which is worst-case optimal) is sufficient for caterpillars.
File in questo prodotto:
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11391/1532754
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 0
  • ???jsp.display-item.citation.isi??? 0
social impact