{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,2]],"date-time":"2026-02-02T21:41:15Z","timestamp":1770068475280,"version":"3.49.0"},"publisher-location":"Berlin, Heidelberg","reference-count":34,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783642114397","type":"print"},{"value":"9783642114403","type":"electronic"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2010]]},"DOI":"10.1007\/978-3-642-11440-3_4","type":"book-chapter","created":{"date-parts":[[2010,2,2]],"date-time":"2010-02-02T11:03:36Z","timestamp":1265108616000},"page":"35-46","source":"Crossref","is-referenced-by-count":6,"title":["The Hamiltonian Augmentation Problem and Its Applications to Graph Drawing"],"prefix":"10.1007","author":[{"given":"Emilio","family":"Di Giacomo","sequence":"first","affiliation":[]},{"given":"Giuseppe","family":"Liotta","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"issue":"2-3","key":"4_CR1","doi-asserted-by":"publisher","first-page":"141","DOI":"10.1016\/S0166-218X(99)00042-6","volume":"93","author":"M. Abellanas","year":"1999","unstructured":"Abellanas, M., Garcia-Lopez, J., Hern\u00e1ndez-Pe\u00f1ver, G., Noy, M., Ramos, P.A.: Bipartite embeddings of trees in the plane. Discrete Applied Mathematics\u00a093(2-3), 141\u2013148 (1999)","journal-title":"Discrete Applied Mathematics"},{"key":"4_CR2","doi-asserted-by":"publisher","first-page":"101","DOI":"10.1016\/0012-365X(90)90276-N","volume":"84","author":"J. Akiyama","year":"1990","unstructured":"Akiyama, J., Urrutia, J.: Simple alternating path problem. Discrete Mathematics\u00a084, 101\u2013103 (1990)","journal-title":"Discrete Mathematics"},{"issue":"2-3","key":"4_CR3","doi-asserted-by":"publisher","first-page":"129","DOI":"10.1016\/j.tcs.2008.08.004","volume":"408","author":"M. Badent","year":"2008","unstructured":"Badent, M., Di Giacomo, E., Liotta, G.: Drawing colored graphs on colored points. Theoretical Computer Science\u00a0408(2-3), 129\u2013142 (2008)","journal-title":"Theoretical Computer Science"},{"issue":"2","key":"4_CR4","doi-asserted-by":"publisher","first-page":"117","DOI":"10.1016\/j.comgeo.2006.05.006","volume":"36","author":"P. Bra\u00df","year":"2007","unstructured":"Bra\u00df, P., Cenek, E., Duncan, C.A., Efrat, A., Erten, C., Ismailescu, D., Kobourov, S.G., Lubiw, A., Mitchell, J.S.B.: On simultaneous planar graph embeddings. Comput. Geom.\u00a036(2), 117\u2013130 (2007)","journal-title":"Comput. Geom."},{"key":"4_CR5","doi-asserted-by":"publisher","first-page":"210","DOI":"10.1137\/0214017","volume":"14","author":"N. Chiba","year":"1985","unstructured":"Chiba, N., Nishizeki, T.: Arboricity and subgraph listing algorithms. SIAM Journal on Computing\u00a014, 210\u2013223 (1985)","journal-title":"SIAM Journal on Computing"},{"key":"4_CR6","doi-asserted-by":"publisher","first-page":"189","DOI":"10.1016\/0196-6774(89)90012-6","volume":"10","author":"N. Chiba","year":"1989","unstructured":"Chiba, N., Nishizeki, T.: The hamiltonian cycle problem is linear-time solvable for 4-connected planar graphs. Journal of Algorithms\u00a010, 189\u2013211 (1989)","journal-title":"Journal of Algorithms"},{"issue":"4","key":"4_CR7","doi-asserted-by":"publisher","first-page":"83","DOI":"10.1145\/74074.74088","volume":"20","author":"M. Chrobak","year":"1989","unstructured":"Chrobak, M., Karloff, H.: A lower bound on the size of universal sets for planar graphs. SIGACT News\u00a020(4), 83\u201386 (1989)","journal-title":"SIGACT News"},{"key":"4_CR8","doi-asserted-by":"publisher","first-page":"41","DOI":"10.1007\/BF02122694","volume":"10","author":"H. Fraysseix de","year":"1990","unstructured":"de Fraysseix, H., Pach, J., Pollack, R.: How to draw a planar graph on a grid. Combinatorica\u00a010, 41\u201351 (1990)","journal-title":"Combinatorica"},{"issue":"1","key":"4_CR9","doi-asserted-by":"publisher","first-page":"109","DOI":"10.1016\/j.jda.2006.12.007","volume":"6","author":"E. Giacomo Di","year":"2008","unstructured":"Di Giacomo, E., Didimo, W., Liotta, G.: Radial drawings of graphs: Geometric constraints and trade-offs. Journal of Discrete Algorithms\u00a06(1), 109\u2013124 (2008)","journal-title":"Journal of Discrete Algorithms"},{"issue":"1","key":"4_CR10","doi-asserted-by":"crossref","first-page":"29","DOI":"10.7155\/jgaa.00158","volume":"12","author":"E. Giacomo Di","year":"2008","unstructured":"Di Giacomo, E., Didimo, W., Liotta, G., Meijer, H., Trotta, F., Wismath, S.K.: k-colored point-set embeddability of outerplanar graphs. Journal of Graph Algorithms and Applications\u00a012(1), 29\u201349 (2008)","journal-title":"Journal of Graph Algorithms and Applications"},{"key":"4_CR11","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/j.comgeo.2004.04.002","volume":"30","author":"E. Giacomo Di","year":"2005","unstructured":"Di Giacomo, E., Didimo, W., Liotta, G., Wismath, S.K.: Curve-constrained drawings of planar graphs. Computational Geometry\u00a030, 1\u201323 (2005)","journal-title":"Computational Geometry"},{"key":"4_CR12","unstructured":"Di Giacomo, E., Liotta, G., Trotta, F.: Drawing colored graphs with constrained vertex positions and few bends per edge. Algorithmica (to appear)"},{"issue":"5","key":"4_CR13","first-page":"1071","volume":"17","author":"E. Giacomo Di","year":"2006","unstructured":"Di Giacomo, E., Liotta, G., Trotta, F.: On embedding a graph on two sets of points. IJFCS, Special Issue on Graph Drawing\u00a017(5), 1071\u20131094 (2006)","journal-title":"IJFCS, Special Issue on Graph Drawing"},{"issue":"2","key":"4_CR14","doi-asserted-by":"publisher","first-page":"139","DOI":"10.1142\/S0218195907002276","volume":"17","author":"E. Giacomo Di","year":"2007","unstructured":"Di Giacomo, E., Liotta, G.: Simultaneous embedding of outerplanar graphs, paths, and cycles. International Journal of Computational Geometry and Applications\u00a017(2), 139\u2013160 (2007)","journal-title":"International Journal of Computational Geometry and Applications"},{"issue":"3","key":"4_CR15","doi-asserted-by":"publisher","first-page":"337","DOI":"10.1137\/S0895480195280319","volume":"12","author":"H. Enomoto","year":"1999","unstructured":"Enomoto, H., Miyauchi, M.S.: Embedding graphs into a three page book with O(m logn) crossings of edges over the spine. SIAM J. Discrete Math.\u00a012(3), 337\u2013341 (1999)","journal-title":"SIAM J. Discrete Math."},{"issue":"3","key":"4_CR16","doi-asserted-by":"crossref","first-page":"347","DOI":"10.7155\/jgaa.00113","volume":"9","author":"C. Erten","year":"2005","unstructured":"Erten, C., Kobourov, S.G.: Simultaneous embedding of planar graphs with few bends. Journal of Graph Algorithms and Applications\u00a09(3), 347\u2013364 (2005)","journal-title":"Journal of Graph Algorithms and Applications"},{"key":"4_CR17","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"345","DOI":"10.1007\/978-3-540-77537-9_34","volume-title":"Graph Drawing","author":"H. Everett","year":"2008","unstructured":"Everett, H., Lazard, S., Liotta, G., Wismath, S.K.: Universal sets of n points for 1-bend drawings of planar graphs with n vertices. In: Hong, S.-H., Nishizeki, T., Quan, W. (eds.) GD 2007. LNCS, vol.\u00a04875, pp. 345\u2013351. Springer, Heidelberg (2008)"},{"key":"4_CR18","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"172","DOI":"10.1007\/978-3-540-77120-3_17","volume-title":"Algorithms and Computation","author":"F. Giordano","year":"2007","unstructured":"Giordano, F., Liotta, G., Mchedlidze, T., Symvonis, A.: Computing upward topological book embeddings of upward planar digraphs. In: Tokuyama, T. (ed.) ISAAC 2007. LNCS, vol.\u00a04835, pp. 172\u2013183. Springer, Heidelberg (2007)"},{"key":"4_CR19","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"242","DOI":"10.1007\/978-3-642-00219-9_23","volume-title":"Graph Drawing","author":"F. Giordano","year":"2009","unstructured":"Giordano, F., Liotta, G., Whitesides, S.: Embeddability problems for upward planar digraphs. In: Tollis, I.G., Patrignani, M. (eds.) GD 2008. LNCS, vol.\u00a05417, pp. 242\u2013253. Springer, Heidelberg (2009)"},{"issue":"2","key":"4_CR20","doi-asserted-by":"publisher","first-page":"165","DOI":"10.2307\/2323956","volume":"98","author":"P. Gritzmann","year":"1991","unstructured":"Gritzmann, P., Mohar, B., Pach, J., Pollack, R.: Embedding a planar triangulation with vertices at specified points. Amer. Math. Monthly\u00a098(2), 165\u2013166 (1991)","journal-title":"Amer. Math. Monthly"},{"key":"4_CR21","doi-asserted-by":"publisher","first-page":"219","DOI":"10.1016\/0020-0255(91)90052-V","volume":"54","author":"J.H. Halton","year":"1991","unstructured":"Halton, J.H.: On the thickness of graphs of given degree. Information Sciences\u00a054, 219\u2013238 (1991)","journal-title":"Information Sciences"},{"key":"4_CR22","doi-asserted-by":"publisher","first-page":"167","DOI":"10.1016\/S0166-218X(99)00191-2","volume":"101","author":"A. Kaneko","year":"2000","unstructured":"Kaneko, A., Kano, M.: Straight line embeddings of rooted star forests in the plane. Discrete Applied Mathematics\u00a0101, 167\u2013175 (2000)","journal-title":"Discrete Applied Mathematics"},{"key":"4_CR23","series-title":"Algorithms and Combinatories","doi-asserted-by":"crossref","first-page":"551","DOI":"10.1007\/978-3-642-55566-4_25","volume-title":"Discrete & Computational Geometry","author":"A. Kaneko","year":"2003","unstructured":"Kaneko, A., Kano, M.: Discrete geometry on red and blue points in the plane - a survey. In: Aronov, B., Basu, S., Pach, J., Sharir, M. (eds.) Discrete & Computational Geometry. Algorithms and Combinatories, vol.\u00a025, pp. 551\u2013570. Springer, Heidelberg (2003)"},{"key":"4_CR24","doi-asserted-by":"crossref","unstructured":"Kaneko, A., Kano, M., Suzuki, K.: Path coverings of two sets of points in the plane. In: Pach, J. (ed.) Towards a Theory of Geometric Graphs. Contemporary Mathematics, vol.\u00a0342. American Mathematical Society (2004)","DOI":"10.1090\/conm\/342\/06134"},{"key":"4_CR25","doi-asserted-by":"crossref","first-page":"73","DOI":"10.1142\/S021819590000005X","volume":"10","author":"A. Kaneko","year":"2000","unstructured":"Kaneko, A., Kano, M., Yoshimoto, K.: Alternating hamilton cycles with minimum number of crossing in the plane. International Journal of Computational Geometry & Application\u00a010, 73\u201378 (2000)","journal-title":"International Journal of Computational Geometry & Application"},{"issue":"4","key":"4_CR26","doi-asserted-by":"publisher","first-page":"603","DOI":"10.1007\/PL00009441","volume":"21","author":"A. Kaneko","year":"1999","unstructured":"Kaneko, A., Kano, M.: Straight-line embeddings of two rooted trees in the plane. Discrete & Computational Geometry\u00a021(4), 603\u2013613 (1999)","journal-title":"Discrete & Computational Geometry"},{"key":"4_CR27","unstructured":"Kaneko, A., Kano, M., Tokunaga, S.: Straight-line embeddings of three rooted trees in the plane. In: Canadian Conference on Computational Geometry, CCCG 1998 (1998)"},{"issue":"1","key":"4_CR28","doi-asserted-by":"crossref","first-page":"115","DOI":"10.7155\/jgaa.00046","volume":"6","author":"M. Kaufmann","year":"2002","unstructured":"Kaufmann, M., Wiese, R.: Embedding vertices at points: Few bends suffice for planar graphs. Journal of Graph Algorithms and Applications\u00a06(1), 115\u2013129 (2002)","journal-title":"Journal of Graph Algorithms and Applications"},{"issue":"2","key":"4_CR29","doi-asserted-by":"publisher","first-page":"95","DOI":"10.1016\/j.ipl.2004.06.009","volume":"92","author":"M. Kurowski","year":"2004","unstructured":"Kurowski, M.: A 1.235 lower bound on the number of points needed to draw all n-vertex planar graphs. Inf. Process. Lett.\u00a092(2), 95\u201398 (2004)","journal-title":"Inf. Process. Lett."},{"key":"4_CR30","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"250","DOI":"10.1007\/978-3-642-00202-1_22","volume-title":"WALCOM: Algorithms and Computation","author":"T. Mchedlidze","year":"2009","unstructured":"Mchedlidze, T., Symvonis, A.: Crossing-optimal acyclic hamiltonian path completion and its application to upward topological book embeddings. In: Das, S., Uehara, R. (eds.) WALCOM 2009. LNCS, vol.\u00a05431, pp. 250\u2013261. Springer, Heidelberg (2009)"},{"key":"4_CR31","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"76","DOI":"10.1007\/978-3-642-02882-3_9","volume-title":"COCOON 2009","author":"T. Mchedlidze","year":"2009","unstructured":"Mchedlidze, T., Symvonis, A.: Crossing-optimal acyclic hp-completion for outerplanar t-digraphs. In: Ngo, H.Q. (ed.) COCOON 2009. LNCS, vol.\u00a05609, pp. 76\u201385. Springer, Heidelberg (2009)"},{"key":"4_CR32","doi-asserted-by":"publisher","first-page":"717","DOI":"10.1007\/PL00007258","volume":"17","author":"J. Pach","year":"2001","unstructured":"Pach, J., Wenger, R.: Embedding planar graphs at fixed vertex locations. Graph and Combinatorics\u00a017, 717\u2013728 (2001)","journal-title":"Graph and Combinatorics"},{"key":"4_CR33","unstructured":"Schnyder, W.: Embedding planar graphs on the grid. In: Proc. 1st ACM-SIAM Sympos. Discrete Algorithms (SODA 1990), pp. 138\u2013148 (1990)"},{"key":"4_CR34","volume-title":"Graph Drawing and Applications","author":"K. Sugiyama","year":"2002","unstructured":"Sugiyama, K.: Graph Drawing and Applications. World Scientific, Singapore (2002)"}],"container-title":["Lecture Notes in Computer Science","WALCOM: Algorithms and Computation"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-11440-3_4","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,5,27]],"date-time":"2020-05-27T04:07:47Z","timestamp":1590552467000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-11440-3_4"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010]]},"ISBN":["9783642114397","9783642114403"],"references-count":34,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-11440-3_4","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2010]]}}}