{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,27]],"date-time":"2025-03-27T06:14:08Z","timestamp":1743056048013,"version":"3.40.3"},"publisher-location":"Berlin, Heidelberg","reference-count":27,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540241317"},{"type":"electronic","value":"9783540305514"}],"license":[{"start":{"date-parts":[[2004,1,1]],"date-time":"2004-01-01T00:00:00Z","timestamp":1072915200000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2004]]},"DOI":"10.1007\/978-3-540-30551-4_60","type":"book-chapter","created":{"date-parts":[[2010,7,13]],"date-time":"2010-07-13T18:15:37Z","timestamp":1279044937000},"page":"693-704","source":"Crossref","is-referenced-by-count":0,"title":["Inner Rectangular Drawings of Plane Graphs"],"prefix":"10.1007","author":[{"given":"Kazuyuki","family":"Miura","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Hiroki","family":"Haga","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Takao","family":"Nishizeki","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"60_CR1","volume-title":"Network Flows: Theory, Algorithms, and Applications","author":"R.K. Ahuja","year":"1993","unstructured":"Ahuja, R.K., Magnanti, T.L., Orlin, J.B.: Network Flows: Theory, Algorithms, and Applications. Prentice Hall, Englewood Cliffs (1993)"},{"key":"60_CR2","doi-asserted-by":"publisher","first-page":"247","DOI":"10.1007\/BF01762117","volume":"3","author":"J. Bhasker","year":"1988","unstructured":"Bhasker, J., Sahni, S.: A linear algorithm to find a rectangular dual of a planar triangulated graph. Algorithmica\u00a03, 247\u2013278 (1988)","journal-title":"Algorithmica"},{"key":"60_CR3","volume-title":"Graph Drawing: Algorithms for the Visualization of Graphs","author":"G. Di Battista","year":"1999","unstructured":"Di Battista, G., Eades, P., Tamassia, R., Tollis, G.: Graph Drawing: Algorithms for the Visualization of Graphs. Prentice Hall, Englewood Cliffs (1999)"},{"key":"60_CR4","doi-asserted-by":"publisher","first-page":"507","DOI":"10.1137\/0204043","volume":"4","author":"S. Even","year":"1975","unstructured":"Even, S., Tarjan, R.E.: Network flow and testing graph connectivity. SIAM J. Computing\u00a04, 507\u2013518 (1975)","journal-title":"SIAM J. Computing"},{"key":"60_CR5","doi-asserted-by":"crossref","unstructured":"Feder, T., Motowani, R.: Clique partitions, graph compression and speeding-up algorithms. Proc. 23rd Ann. ACM Symp. on Theory of Computing, 123\u2013133 (1991)","DOI":"10.1145\/103418.103424"},{"key":"60_CR6","volume-title":"Prentice Hall-CNew Jersey","author":"R.L. Francis","year":"1974","unstructured":"Francis, R.L., White, J.A.: Facility Layout and Location. In: Prentice Hall-CNew Jersey, Prentice-Hall, CNew Jersey (1974)"},{"key":"60_CR7","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","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.C. (ed.) GD 1996. LNCS, vol.\u00a01190, pp. 201\u2013206. Springer, Heidelberg (1997)"},{"issue":"6","key":"60_CR8","doi-asserted-by":"publisher","first-page":"1218","DOI":"10.1137\/0222072","volume":"22","author":"X. He","year":"1993","unstructured":"He, X.: On finding the rectangular duals of planar triangulated graphs. SIAM J. Comput.\u00a022(6), 1218\u20131226 (1993)","journal-title":"SIAM J. Comput."},{"key":"60_CR9","unstructured":"Hochbaum, D.S.: Faster pseudoflow-based algorithms for the bipartite matching and the closure problems. In: Abstract, CORS\/SCRO-INFORMS Joint Int. Meeting, Banff, Canada, May 16-19, p. 46 (2004)"},{"key":"60_CR10","unstructured":"Hochbaum, D.S., Chandran, B.G.: Further below the flow decomposition barrier of maximum flow for bipartite matching and maximum closure. In: Working paper (2004)"},{"key":"60_CR11","doi-asserted-by":"publisher","first-page":"225","DOI":"10.1137\/0202019","volume":"2","author":"J.E. Hopcroft","year":"1973","unstructured":"Hopcroft, J.E., Karp, R.M.: An n\n                        5\/2 algorithm for maximum matching in bipartite graphs. SIAM J. Comput.\u00a02, 225\u2013231 (1973)","journal-title":"SIAM J. Comput."},{"key":"60_CR12","doi-asserted-by":"publisher","first-page":"175","DOI":"10.1016\/S0304-3975(95)00257-X","volume":"172","author":"G. Kant","year":"1997","unstructured":"Kant, G., He, X.: Regular edge-labeling of 4-connected plane graphs and its applications in graph drawing problems. Theoret. Comput. Sci.\u00a0172, 175\u2013193 (1997)","journal-title":"Theoret. Comput. Sci."},{"key":"60_CR13","doi-asserted-by":"crossref","unstructured":"Kozminski, K., Kinnen, E.: An algorithm for finding a rectangular dual of a planar graph for use in area planning for VLSI integrated circuits. In: Proc. of 21st DAC, Albuquerque, pp. 655\u2013656 (1984)","DOI":"10.1109\/DAC.1984.1585872"},{"key":"60_CR14","doi-asserted-by":"publisher","first-page":"467","DOI":"10.1007\/BF01840399","volume":"5","author":"Y.-T. Lai","year":"1990","unstructured":"Lai, Y.-T., LeinwandC, S.M.: A theory of rectangular dual graphs. Algorithmica\u00a05, 467\u2013483 (1990)","journal-title":"Algorithmica"},{"key":"60_CR15","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-322-92106-2","volume-title":"Combinatorial Algorithms for Integrated Circuit Layout","author":"T. LengauerC","year":"1990","unstructured":"LengauerC, T.: Combinatorial Algorithms for Integrated Circuit Layout. Wiley, Chichester (1990)"},{"issue":"5","key":"60_CR16","doi-asserted-by":"publisher","first-page":"1002","DOI":"10.1137\/S0097539789162997","volume":"24","author":"G.L. Miller","year":"1995","unstructured":"Miller, G.L., Naor, J.S.: Flows in planar graphs with multiple sources and sinks. SIAM J. Computing\u00a024(5), 1002\u20131017 (1995)","journal-title":"SIAM J. Computing"},{"key":"60_CR17","doi-asserted-by":"crossref","unstructured":"Micali, S., Vazirani, V.V.: An O\n                        $(\\sqrt{|{\\it V}|}\\cdot|{\\it E|})$ algorithm for finding maximum matching in general graphs. In: Proc. 21st Annual Symposium on Foundations of Computer Science, pp. 17\u201327 (1980)","DOI":"10.1109\/SFCS.1980.12"},{"key":"60_CR18","series-title":"Lect. Notes in Computer Science","doi-asserted-by":"publisher","first-page":"256","DOI":"10.1007\/3-540-36151-0_24","volume-title":"Proc. Graph Drawing 2002","author":"K. Miura","year":"2002","unstructured":"Miura, K., Miyazawa, A., Nishizeki, T.: Extended rectangular drawing of plane graphs with designated corners. In: Proc. Graph Drawing 2002. Lect. Notes in Computer Science, vol.\u00a02528, pp. 256\u2013267. Springer, Heidelberg (2002)"},{"key":"60_CR19","volume-title":"Combinatorial Optinization","author":"C.H. Papadimitriou","year":"1982","unstructured":"Papadimitriou, C.H., Steiglitz, K.: Combinatorial Optinization. Prentice Hall, Englewood Cliffs (1982)"},{"key":"60_CR20","doi-asserted-by":"publisher","first-page":"121","DOI":"10.1016\/S0925-7721(01)00061-X","volume":"21","author":"M.S. Rahman","year":"2002","unstructured":"Rahman, M.S., Nakano, S., Nishizeki, T.: Rectangular drawings of plane graphs without designated corners. Computational Geometry\u00a021, 121\u2013138 (2002)","journal-title":"Computational Geometry"},{"issue":"3","key":"60_CR21","doi-asserted-by":"crossref","first-page":"203","DOI":"10.1016\/S0925-7721(98)00003-0","volume":"10","author":"M.S. Rahman","year":"1998","unstructured":"Rahman, M.S., Nakano, S., Nishizeki, T.: Rectangular grid drawings of plane graphs. Comp. Geom. Theo. Appl.\u00a010(3), 203\u2013220 (1998)","journal-title":"Comp. Geom. Theo. Appl."},{"key":"60_CR22","doi-asserted-by":"crossref","DOI":"10.1142\/4109","volume-title":"VLSI Physical Design Automation","author":"S.M. Sait","year":"1999","unstructured":"Sait, S.M., Youssef, H.: VLSI Physical Design Automation. World Scientific, Singapore (1999)"},{"key":"60_CR23","doi-asserted-by":"publisher","first-page":"429","DOI":"10.1007\/BF01891831","volume":"10","author":"Y. Sun","year":"1993","unstructured":"Sun, Y., Sarrafzadeh, M.: Floorplanning by graph dualization: L-shape modules. Algorithmica\u00a010, 429\u2013456 (1993)","journal-title":"Algorithmica"},{"issue":"3","key":"60_CR24","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.\u00a016(3), 421\u2013444 (1987)","journal-title":"SIAM J. Comput."},{"key":"60_CR25","first-page":"43","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, pp. 43\u201369. Academic Press Canada, Canada (1984)"},{"key":"60_CR26","doi-asserted-by":"publisher","first-page":"347","DOI":"10.4153\/CJM-1954-033-3","volume":"6","author":"W.T. Tutte","year":"1954","unstructured":"Tutte, W.T.: A short proof of the factor theorem for finite graphs. Canad. J. Math.\u00a06, 347\u2013352 (1954)","journal-title":"Canad. J. Math."},{"issue":"3","key":"60_CR27","doi-asserted-by":"publisher","first-page":"500","DOI":"10.1137\/0222035","volume":"22","author":"K. Yeap","year":"1993","unstructured":"Yeap, K., Sarrafzadeh, M.: Floor-planning by graph dualization: 2-concave rectilinear modules. SIAM J. Comput\u00a022(3), 500\u2013526 (1993)","journal-title":"SIAM J. Comput"}],"container-title":["Lecture Notes in Computer Science","Algorithms and Computation"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-30551-4_60","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,1,19]],"date-time":"2023-01-19T23:04:31Z","timestamp":1674169471000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-540-30551-4_60"}},"subtitle":["(Extended Abstract)"],"short-title":[],"issued":{"date-parts":[[2004]]},"ISBN":["9783540241317","9783540305514"],"references-count":27,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-30551-4_60","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2004]]}}}