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 (blue) points as the red (blue) vertices of G. A 2-colored point-set embedding of G on S is a planar drawing that maps each red (blue) vertex of G to a red (blue) point of S. We show that there exist properly 2-colored graphs (i.e., 2-colored graphs with no adjacent vertices having the same color) having treewidth two 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 (blue) points as the red (blue) vertices of G. A 2-colored point-set embedding of G on S is a planar drawing that maps each red (blue) vertex of G to a red (blue) point of S. We show that there exist properly 2-colored graphs (i.e., 2-colored graphs with no adjacent vertices having the same color) having treewidth two 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.
2021
978-3-030-68210-1
978-3-030-68211-8
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/1490988
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 1
  • ???jsp.display-item.citation.isi??? ND
social impact