{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,27]],"date-time":"2025-03-27T06:02:38Z","timestamp":1743055358622,"version":"3.40.3"},"publisher-location":"Cham","reference-count":42,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783030398804"},{"type":"electronic","value":"9783030398811"}],"license":[{"start":{"date-parts":[[2020,1,1]],"date-time":"2020-01-01T00:00:00Z","timestamp":1577836800000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2020]]},"DOI":"10.1007\/978-3-030-39881-1_1","type":"book-chapter","created":{"date-parts":[[2020,1,27]],"date-time":"2020-01-27T03:02:33Z","timestamp":1580094153000},"page":"3-14","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Drawing Planar Graphs"],"prefix":"10.1007","author":[{"given":"Md. Saidur","family":"Rahman","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Md. Rezaul","family":"Karim","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2020,2,20]]},"reference":[{"key":"1_CR1","doi-asserted-by":"crossref","unstructured":"Angelini, P., et al.: Testing planarity of partially embedded graphs. In: Proceedings of the Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 202\u2013221. SIAM (2010)","DOI":"10.1137\/1.9781611973075.19"},{"issue":"1","key":"1_CR2","doi-asserted-by":"publisher","first-page":"5","DOI":"10.7155\/jgaa.00249","volume":"16","author":"P Angelini","year":"2012","unstructured":"Angelini, P., Colasante, E., Di Battista, G., Frati, F., Patrignani, M.: Monotone drawings of graphs. J. Graph Algorithms Appl. 16(1), 5\u201335 (2012)","journal-title":"J. Graph Algorithms Appl."},{"issue":"4","key":"1_CR3","doi-asserted-by":"publisher","first-page":"890","DOI":"10.1007\/s00453-009-9380-6","volume":"60","author":"P Angelini","year":"2011","unstructured":"Angelini, P., Di Battista, G., Patrignani, M.: Finding a minimum-depthembedding of a planar graph in O($$n^4$$) time. Algorithmica 60(4), 890\u2013937 (2011)","journal-title":"Algorithmica"},{"issue":"2","key":"1_CR4","doi-asserted-by":"publisher","first-page":"233","DOI":"10.1007\/s00453-013-9790-3","volume":"71","author":"P Angelini","year":"2015","unstructured":"Angelini, P., et al.: Monotone drawings of graphs with fixed embedding. Algorithmica 71(2), 233\u2013257 (2015)","journal-title":"Algorithmica"},{"issue":"1\u20134","key":"1_CR5","doi-asserted-by":"publisher","first-page":"93","DOI":"10.1007\/BF01840379","volume":"5","author":"D Bienstock","year":"1990","unstructured":"Bienstock, D., Monma, C.L.: On the complexity of embedding planar graphs to minimize certain distance measures. Algorithmica 5(1\u20134), 93\u2013109 (1990)","journal-title":"Algorithmica"},{"key":"1_CR6","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"25","DOI":"10.1007\/978-3-540-24595-7_3","volume-title":"Graph Drawing","author":"JM Boyer","year":"2004","unstructured":"Boyer, J.M., Cortese, P.F., Patrignani, M., Di Battista, G.: Stop minding your P\u2019s and Q\u2019s: implementing a fast and simple DFS-based planarity testing and embedding algorithm. In: Liotta, G. (ed.) GD 2003. LNCS, vol. 2912, pp. 25\u201336. Springer, Heidelberg (2004). \nhttps:\/\/doi.org\/10.1007\/978-3-540-24595-7_3"},{"issue":"3","key":"1_CR7","doi-asserted-by":"publisher","first-page":"421","DOI":"10.7155\/jgaa.00330","volume":"18","author":"FJ Brandenburg","year":"2014","unstructured":"Brandenburg, F.J.: 1-visibility representations of 1-planar graphs. J. Graph Algorithms Appl. 18(3), 421\u2013438 (2014)","journal-title":"J. Graph Algorithms Appl."},{"key":"1_CR8","unstructured":"Chang, Y.J., Yen, H.C.: On bend-minimized orthogonal drawings of planar 3-graphs. In: Proceedings of 33rd International Symposium on Computational Geometry (SoCG 2017). Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik (2017)"},{"key":"1_CR9","first-page":"153","volume":"173","author":"N Chiba","year":"1984","unstructured":"Chiba, N., Yamanouchi, T., Nishizeki, T.: Linear algorithms for convex drawings of planar graphs. Prog. Graph Theory 173, 153\u2013173 (1984)","journal-title":"Prog. Graph Theory"},{"issue":"1","key":"1_CR10","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 10(1), 41\u201351 (1990)","journal-title":"Combinatorica"},{"issue":"6","key":"1_CR11","doi-asserted-by":"publisher","first-page":"1764","DOI":"10.1137\/S0097539794262847","volume":"27","author":"G Battista Di","year":"1998","unstructured":"Di Battista, G., Liotta, G., Vargiu, F.: Spirality and optimal orthogonal drawings. SIAM J. Comput. 27(6), 1764\u20131811 (1998)","journal-title":"SIAM J. Comput."},{"issue":"4","key":"1_CR12","doi-asserted-by":"publisher","first-page":"302","DOI":"10.1007\/BF01961541","volume":"15","author":"G Battista Di","year":"1996","unstructured":"Di Battista, G., Tamassia, R.: On-line maintenance of triconnected components with SPQR-trees. Algorithmica 15(4), 302\u2013318 (1996)","journal-title":"Algorithmica"},{"key":"1_CR13","doi-asserted-by":"crossref","unstructured":"Didimo, W., Liotta, G., Ortali, G., Patrignani, M.: Optimal orthogonal drawings of planar 3-graphs in linear time. arXiv preprint, \narXiv:1910.11782\n\n (2019)","DOI":"10.1137\/1.9781611975994.49"},{"key":"1_CR14","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"481","DOI":"10.1007\/978-3-030-04414-5_34","volume-title":"Graph Drawing and Network Visualization","author":"W Didimo","year":"2018","unstructured":"Didimo, W., Liotta, G., Patrignani, M.: Bend-minimum orthogonal drawings in quadratic time. In: Biedl, T., Kerren, A. (eds.) GD 2018. LNCS, vol. 11282, pp. 481\u2013494. Springer, Cham (2018). \nhttps:\/\/doi.org\/10.1007\/978-3-030-04414-5_34"},{"key":"1_CR15","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"201","DOI":"10.1007\/3-540-62495-3_49","volume-title":"Graph Drawing","author":"A Garg","year":"1997","unstructured":"Garg, A., Tamassia, R.: A new minimum cost flow algorithm with applications to graph drawing. In: North, S. (ed.) GD 1996. LNCS, vol. 1190, pp. 201\u2013216. Springer, Heidelberg (1997). \nhttps:\/\/doi.org\/10.1007\/3-540-62495-3_49"},{"issue":"2","key":"1_CR16","doi-asserted-by":"publisher","first-page":"601","DOI":"10.1137\/S0097539794277123","volume":"31","author":"A Garg","year":"2001","unstructured":"Garg, A., Tamassia, R.: On the computational complexity of upward and rectilinear planarity testing. SIAM J. Comput. 31(2), 601\u2013625 (2001)","journal-title":"SIAM J. Comput."},{"key":"1_CR17","doi-asserted-by":"publisher","first-page":"143","DOI":"10.1016\/j.endm.2008.06.029","volume":"31","author":"B Haeupler","year":"2008","unstructured":"Haeupler, B., Tarjan, R.E.: Planarity algorithms via PQ-trees. Electron. Notes Discret. Math. 31, 143\u2013149 (2008)","journal-title":"Electron. Notes Discret. Math."},{"key":"1_CR18","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"254","DOI":"10.1007\/978-3-030-26176-4_21","volume-title":"Computing and Combinatorics","author":"MM Hasan","year":"2019","unstructured":"Hasan, M.M., Rahman, M.S.: No-bend orthogonal drawings and no-bend orthogonally convex drawings of planar graphs (extended abstract). In: Du, D.-Z., Duan, Z., Tian, C. (eds.) COCOON 2019. LNCS, vol. 11653, pp. 254\u2013265. Springer, Cham (2019). \nhttps:\/\/doi.org\/10.1007\/978-3-030-26176-4_21"},{"issue":"6","key":"1_CR19","doi-asserted-by":"publisher","first-page":"629","DOI":"10.7155\/jgaa.00309","volume":"17","author":"MM Hasan","year":"2013","unstructured":"Hasan, M.M., Rahman, M.S., Karim, M.R.: Box-rectangular drawings of planar graphs. J. Graph Algorithms Appl. 17(6), 629\u2013646 (2013)","journal-title":"J. Graph Algorithms Appl."},{"key":"1_CR20","unstructured":"Hong, S., Tokuyama, T.: Algorithmics for beyond planar graphs. In: NII Shonan Meeting Seminar, no. 27, pp. 51\u201363 (2016)"},{"issue":"4","key":"1_CR21","doi-asserted-by":"publisher","first-page":"549","DOI":"10.1145\/321850.321852","volume":"21","author":"J Hopcroft","year":"1974","unstructured":"Hopcroft, J., Tarjan, R.: Efficient planarity testing. J. ACM (JACM) 21(4), 549\u2013568 (1974)","journal-title":"J. ACM (JACM)"},{"issue":"2","key":"1_CR22","doi-asserted-by":"publisher","first-page":"59","DOI":"10.7155\/jgaa.00285","volume":"17","author":"M Hossain","year":"2013","unstructured":"Hossain, M., Mondal, D., Rahman, M., Salma, S.: Universal line-sets for drawing planar 3-trees. J. Graph Algorithms Appl. 17(2), 59\u201379 (2013)","journal-title":"J. Graph Algorithms Appl."},{"key":"1_CR23","doi-asserted-by":"publisher","first-page":"149","DOI":"10.1016\/j.tcs.2015.09.004","volume":"607","author":"MI Hossain","year":"2015","unstructured":"Hossain, M.I., Rahman, M.S.: Good spanning trees in graph drawing. Theor. Comput. Sci. 607, 149\u2013165 (2015)","journal-title":"Theor. Comput. Sci."},{"issue":"02","key":"1_CR24","doi-asserted-by":"publisher","first-page":"1550007","DOI":"10.1142\/S179383091550007X","volume":"7","author":"MI Hossain","year":"2015","unstructured":"Hossain, M.I., Rahman, M.S.: Straight-line monotone grid drawings of series-parallel graphs. Discrete Math. Algorithms Appl. 7(02), 1550007 (2015)","journal-title":"Discrete Math. Algorithms Appl."},{"issue":"2","key":"1_CR25","doi-asserted-by":"publisher","first-page":"233","DOI":"10.1007\/BF01940648","volume":"16","author":"K Mehlhorn","year":"1996","unstructured":"Mehlhorn, K., Mutzel, P.: On the embedding phase of the hopcroft and tarjan planarity testing algorithm. Algorithmica 16(2), 233\u2013242 (1996)","journal-title":"Algorithmica"},{"key":"1_CR26","doi-asserted-by":"publisher","DOI":"10.1142\/5648","volume-title":"Planar Graph Drawing","author":"T Nishizeki","year":"2004","unstructured":"Nishizeki, T., Rahman, M.S.: Planar Graph Drawing, vol. 12. World Scientific Publishing Company, Singapore (2004)"},{"key":"1_CR27","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-49475-3","volume-title":"Basic Graph Theory","author":"MS Rahman","year":"2017","unstructured":"Rahman, M.S.: Basic Graph Theory. Springer, Cham (2017). \nhttps:\/\/doi.org\/10.1007\/978-3-319-49475-3"},{"issue":"1","key":"1_CR28","doi-asserted-by":"publisher","first-page":"23","DOI":"10.1093\/ietisy\/E88-D.1.23","volume":"88","author":"MS Rahman","year":"2005","unstructured":"Rahman, M.S., Egi, N., Nishizeki, T.: No-bend orthogonal drawings of subdivisions of planar triconnected cubic graphs. IEICE Trans. Inform. Syst. 88(1), 23\u201330 (2005)","journal-title":"IEICE Trans. Inform. Syst."},{"issue":"3","key":"1_CR29","doi-asserted-by":"publisher","first-page":"203","DOI":"10.1016\/S0925-7721(98)00003-0","volume":"10","author":"MS Rahman","year":"1998","unstructured":"Rahman, M.S., Nakano, S., Nishizeki, T.: Rectangular grid drawings of plane graphs. Comput. Geom. 10(3), 203\u2013220 (1998)","journal-title":"Comput. Geom."},{"key":"1_CR30","doi-asserted-by":"publisher","first-page":"31","DOI":"10.7155\/jgaa.00017","volume":"3","author":"MS Rahman","year":"1999","unstructured":"Rahman, M.S., Nakano, S., Nishizeki, T.: A linear algorithm for bend-optimal orthogonal drawings of triconnected cubic plane graphs. J. Graph Algorithms Appl. 3, 31\u201362 (1999)","journal-title":"J. Graph Algorithms Appl."},{"issue":"3","key":"1_CR31","doi-asserted-by":"publisher","first-page":"121","DOI":"10.1016\/S0925-7721(01)00061-X","volume":"21","author":"MS Rahman","year":"2002","unstructured":"Rahman, M.S., Nakano, S., Nishizeki, T.: Rectangular drawings of plane graphs without designated corners. Comput. Geom. 21(3), 121\u2013138 (2002)","journal-title":"Comput. Geom."},{"key":"1_CR32","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"367","DOI":"10.1007\/3-540-36379-3_32","volume-title":"Graph-Theoretic Concepts in Computer Science","author":"MS Rahman","year":"2002","unstructured":"Rahman, M.S., Nishizeki, T.: Bend-minimum orthogonal drawings of plane 3-graphs. In: Goos, G., Hartmanis, J., van Leeuwen, J., Ku\u010dera, L. (eds.) WG 2002. LNCS, vol. 2573, pp. 367\u2013378. Springer, Heidelberg (2002). \nhttps:\/\/doi.org\/10.1007\/3-540-36379-3_32"},{"issue":"1","key":"1_CR33","doi-asserted-by":"publisher","first-page":"62","DOI":"10.1016\/S0196-6774(03)00126-3","volume":"50","author":"MS Rahman","year":"2004","unstructured":"Rahman, M.S., Nishizeki, T., Ghosh, S.: Rectangular drawings of planar graphs. J. Algorithms 50(1), 62\u201378 (2004)","journal-title":"J. Algorithms"},{"key":"1_CR34","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"408","DOI":"10.1007\/978-3-642-00219-9_40","volume-title":"Graph Drawing","author":"MAH Samee","year":"2009","unstructured":"Samee, M.A.H., Alam, M.J., Adnan, M.A., Rahman, M.S.: Minimum segment drawings of series-parallel graphs with the maximum degree three. In: Tollis, I.G., Patrignani, M. (eds.) GD 2008. LNCS, vol. 5417, pp. 408\u2013419. Springer, Heidelberg (2009). \nhttps:\/\/doi.org\/10.1007\/978-3-642-00219-9_40"},{"key":"1_CR35","unstructured":"Samee, M.A.H., Rahman, M.S.: Upward planar drawings of series-parallel digraphs with maximum degree three. In: Proceedings of WALCOM 2007, pp. 28\u201345. Bangladesh Academy of Sciences (2007)"},{"key":"1_CR36","unstructured":"Schnyder, W.: Embedding planar graphs on the grid. In: Proceedings of the First Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 138\u2013148. Society for Industrial and Applied Mathematics (1990)"},{"issue":"1","key":"1_CR37","first-page":"179","volume":"223","author":"WK Shih","year":"1999","unstructured":"Shih, W.K., Hsu, W.L.: A new planarity test. Theor. Comput. Sci. 223(1), 179\u2013192 (1999)","journal-title":"Theor. Comput. Sci."},{"key":"1_CR38","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"62","DOI":"10.1007\/978-3-319-04126-1_6","volume-title":"Applied Algorithms","author":"S Sultana","year":"2014","unstructured":"Sultana, S., Rahman, M.S., Roy, A., Tairin, S.: Bar 1-visibility drawings of 1-planar graphs. In: Gupta, P., Zaroliagis, C. (eds.) ICAA 2014. LNCS, vol. 8321, pp. 62\u201376. Springer, Cham (2014). \nhttps:\/\/doi.org\/10.1007\/978-3-319-04126-1_6"},{"issue":"3","key":"1_CR39","doi-asserted-by":"publisher","first-page":"421","DOI":"10.1137\/0216030","volume":"16","author":"R Tamassia","year":"1987","unstructured":"Tamassia, R.: On embedding a graph in the grid with the minimum number of bends. SIAM J. Comput. 16(3), 421\u2013444 (1987)","journal-title":"SIAM J. Comput."},{"issue":"2","key":"1_CR40","doi-asserted-by":"publisher","first-page":"244","DOI":"10.1016\/0095-8956(80)90083-0","volume":"29","author":"C Thomassen","year":"1980","unstructured":"Thomassen, C.: Planarity and duality of finite and infinite graphs. J. Comb. Theory Ser. B 29(2), 244\u2013271 (1980)","journal-title":"J. Comb. Theory Ser. B"},{"key":"1_CR41","volume-title":"Progress in Graph Theory","author":"C Thomassen","year":"1984","unstructured":"Thomassen, C.: Plane representations of graphs. In: Bondy, J.A., Murty, U.S.R. (eds.) Progress in Graph Theory. Academic Press, New York (1984)"},{"issue":"1","key":"1_CR42","doi-asserted-by":"publisher","first-page":"304","DOI":"10.1112\/plms\/s3-10.1.304","volume":"3","author":"WT Tutte","year":"1960","unstructured":"Tutte, W.T.: Convex representations of graphs. Proc. London Math. Soc. 3(1), 304\u2013320 (1960)","journal-title":"Proc. London Math. Soc."}],"container-title":["Lecture Notes in Computer Science","WALCOM: Algorithms and Computation"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-030-39881-1_1","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,2,19]],"date-time":"2020-02-19T19:04:54Z","timestamp":1582139094000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-030-39881-1_1"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020]]},"ISBN":["9783030398804","9783030398811"],"references-count":42,"URL":"https:\/\/doi.org\/10.1007\/978-3-030-39881-1_1","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2020]]},"assertion":[{"value":"20 February 2020","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"WALCOM","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Workshop on Algorithms and Computation","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Singapore","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Singapore","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2020","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"31 March 2020","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2 April 2020","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"14","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"walcom2020","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/www.comp.nus.edu.sg\/~walcom20\/","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}}]}}