{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,22]],"date-time":"2026-01-22T10:47:49Z","timestamp":1769078869844,"version":"3.49.0"},"reference-count":22,"publisher":"World Scientific Pub Co Pte Lt","issue":"05","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Int. J. Found. Comput. Sci."],"published-print":{"date-parts":[[2006,10]]},"abstract":"<jats:p>Let R and B be two sets of points such that the points of R are colored red and the points of B are colored blue. Let G be a planar graph such that |R| vertices of G are red and |B| vertices of G are blue. A bichromatic point-set embedding of G on R \u222a B is a crossing-free drawing of G such that each blue vertex is mapped to a point of B, each red vertex is mapped to a point of R, and each edge is a polygonal curve. We study the curve complexity of bichromatic point-set embeddings; i.e., the number of bends per edge that are necessary and sufficient to compute such drawings. We show that O(n) bends are sometimes necessary. We also prove that two bends per edge suffice if G is a 2-colored caterpillar and that for properly 2-colored caterpillars, properly 2-colored wreaths, 2-colored paths, and 2-colored cycles the number of bends per edge can be reduced to one, which is worst-case optimal.<\/jats:p>","DOI":"10.1142\/s0129054106004273","type":"journal-article","created":{"date-parts":[[2006,9,18]],"date-time":"2006-09-18T12:04:43Z","timestamp":1158581083000},"page":"1071-1094","source":"Crossref","is-referenced-by-count":20,"title":["ON EMBEDDING A GRAPH ON TWO SETS OF POINTS"],"prefix":"10.1142","volume":"17","author":[{"given":"EMILIO","family":"DI GIACOMO","sequence":"first","affiliation":[{"name":"Dipartimento di Ingegneria Elettronica e dell'Informazione, Universit\u00e0 degli Studi di Perugia, Via G. Duranti, 93, Perugia, 06125, Italy"}]},{"given":"GIUSEPPE","family":"LIOTTA","sequence":"additional","affiliation":[{"name":"Dipartimento di Ingegneria Elettronica e dell'Informazione, Universit\u00e0 degli Studi di Perugia, Via G. Duranti, 93, Perugia, 06125, Italy"}]},{"given":"FRANCESCO","family":"TROTTA","sequence":"additional","affiliation":[{"name":"Dipartimento di Ingegneria Elettronica e dell'Informazione, Universit\u00e0 degli Studi di Perugia, Via G. Duranti, 93, Perugia, 06125, Italy"}]}],"member":"219","published-online":{"date-parts":[[2011,11,20]]},"reference":[{"key":"rf1","doi-asserted-by":"publisher","DOI":"10.1016\/S0166-218X(99)00042-6"},{"key":"rf2","doi-asserted-by":"publisher","DOI":"10.1016\/0012-365X(90)90276-N"},{"key":"rf4","doi-asserted-by":"publisher","DOI":"10.7155\/jgaa.00006"},{"key":"rf5","volume-title":"Graph Drawing","author":"Di Battista G.","year":"1999"},{"key":"rf8","first-page":"155","volume":"7","author":"Dujmovi\u0107 V.","journal-title":"Discrete Mathematics and Theoretical Computer Science"},{"key":"rf9","doi-asserted-by":"publisher","DOI":"10.1137\/S0895480195280319"},{"key":"rf10","doi-asserted-by":"publisher","DOI":"10.1016\/S0166-218X(99)00044-X"},{"key":"rf11","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0255(91)90052-V"},{"key":"rf12","doi-asserted-by":"publisher","DOI":"10.1007\/BF02573994"},{"key":"rf13","doi-asserted-by":"publisher","DOI":"10.1007\/PL00009441"},{"key":"rf14","doi-asserted-by":"publisher","DOI":"10.1016\/S0166-218X(99)00191-2"},{"key":"rf15","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-55566-4_25"},{"key":"rf16","doi-asserted-by":"publisher","DOI":"10.1090\/conm\/342\/06134"},{"key":"rf18","doi-asserted-by":"crossref","first-page":"73","DOI":"10.1142\/S021819590000005X","volume":"10","author":"Kaneko A.","journal-title":"International Journal of Computational Geometry & Application"},{"key":"rf19","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-44969-8"},{"key":"rf20","doi-asserted-by":"publisher","DOI":"10.7155\/jgaa.00046"},{"key":"rf21","first-page":"521","volume":"77","author":"Miyauchi M. S.","journal-title":"IEICE Trans. Fundamentals"},{"key":"rf22","first-page":"1732","volume":"83","author":"Miyauchi M. S.","journal-title":"IEICE Trans. Fundamentals"},{"key":"rf23","series-title":"Annals of Discrete Mathematics","volume-title":"Planar Graphs: Theory and Algorithms","volume":"32","author":"Nishizeki T.","year":"1988"},{"key":"rf24","doi-asserted-by":"crossref","unstructured":"J.\u00a0Path and J.\u00a0T\u00f6r\u0151csik, Planar Graphs, DIMACS Series in Discrete Mathematics and Theoretical Computer Science\u00a09, ed. W. T.\u00a0Trotter (American Mathematical Society, 1993)\u00a0pp. 131\u2013137.","DOI":"10.1090\/dimacs\/009\/11"},{"key":"rf25","doi-asserted-by":"publisher","DOI":"10.1007\/PL00007258"},{"key":"rf26","doi-asserted-by":"publisher","DOI":"10.1016\/0012-365X(95)00201-7"}],"container-title":["International Journal of Foundations of Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S0129054106004273","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,4,18]],"date-time":"2020-04-18T07:23:24Z","timestamp":1587194604000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/abs\/10.1142\/S0129054106004273"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2006,10]]},"references-count":22,"journal-issue":{"issue":"05","published-online":{"date-parts":[[2011,11,20]]},"published-print":{"date-parts":[[2006,10]]}},"alternative-id":["10.1142\/S0129054106004273"],"URL":"https:\/\/doi.org\/10.1142\/s0129054106004273","relation":{},"ISSN":["0129-0541","1793-6373"],"issn-type":[{"value":"0129-0541","type":"print"},{"value":"1793-6373","type":"electronic"}],"subject":[],"published":{"date-parts":[[2006,10]]}}}