{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,14]],"date-time":"2025-10-14T11:23:59Z","timestamp":1760441039470},"publisher-location":"Berlin, Heidelberg","reference-count":31,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642258770"},{"type":"electronic","value":"9783642258787"}],"license":[{"start":{"date-parts":[[2012,1,1]],"date-time":"2012-01-01T00:00:00Z","timestamp":1325376000000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2012]]},"DOI":"10.1007\/978-3-642-25878-7_12","type":"book-chapter","created":{"date-parts":[[2011,12,15]],"date-time":"2011-12-15T02:23:04Z","timestamp":1323915784000},"page":"111-122","source":"Crossref","is-referenced-by-count":5,"title":["Accelerated Bend Minimization"],"prefix":"10.1007","author":[{"given":"Sabine","family":"Cornelsen","sequence":"first","affiliation":[]},{"given":"Andreas","family":"Karrenbauer","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"issue":"3","key":"12_CR1","doi-asserted-by":"publisher","first-page":"159","DOI":"10.1016\/S0925-7721(97)00026-6","volume":"9","author":"T.C. Biedl","year":"1998","unstructured":"Biedl, T.C., Kant, G.: A better heuristic for orthogonal graph drawings. Computational Geometry\u00a09(3), 159\u2013180 (1998)","journal-title":"Computational Geometry"},{"issue":"2","key":"12_CR2","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 Journal on Computing\u00a031(2), 601\u2013625 (2001)","journal-title":"SIAM Journal on Computing"},{"key":"12_CR3","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 Journal on Computing\u00a016, 421\u2013444 (1987)","journal-title":"SIAM Journal on Computing"},{"key":"12_CR4","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"254","DOI":"10.1007\/BFb0021809","volume-title":"Graph Drawing","author":"U. F\u00f6\u00dfmeier","year":"1996","unstructured":"F\u00f6\u00dfmeier, U., Kaufmann, M.: Drawing High Degree Graphs with Low Bend Numbers. In: Brandenburg, F.J. (ed.) GD 1995. LNCS, vol.\u00a01027, pp. 254\u2013266. Springer, Heidelberg (1996)"},{"unstructured":"Klau, G.W., Mutzel, P.: Quasi orthogonal drawing of planar graphs. Technical Report MPI-I-98-1-013, Max-Planck-Institut f\u00fcr Informatik, Saarbr\u00fccken, Germany (1998), http:\/\/data.mpi-sb.mpg.de\/internet\/reports.nsf","key":"12_CR5"},{"issue":"1","key":"12_CR6","doi-asserted-by":"publisher","first-page":"61","DOI":"10.1109\/21.87055","volume":"18","author":"R. Tamassia","year":"1988","unstructured":"Tamassia, R., Di Battista, G., Batini, C.: Automatic graph drawing and readability of diagrams. IEEE Transactions on Systems, Man and Cybernetics\u00a018(1), 61\u201379 (1988)","journal-title":"IEEE Transactions on Systems, Man and Cybernetics"},{"issue":"8","key":"12_CR7","doi-asserted-by":"publisher","first-page":"826","DOI":"10.1109\/12.868028","volume":"49","author":"P. Bertolazzi","year":"2000","unstructured":"Bertolazzi, P., Di Battista, G., Didimo, W.: Computing orthogonal drawings with the minimum number of bends. IEEE Transactions on Computers\u00a049(8), 826\u2013840 (2000)","journal-title":"IEEE Transactions on Computers"},{"issue":"2","key":"12_CR8","doi-asserted-by":"publisher","first-page":"117","DOI":"10.1016\/j.comgeo.2004.01.008","volume":"29","author":"U. Brandes","year":"2004","unstructured":"Brandes, U., Cornelsen, S., Fie\u00df, C., Wagner, D.: How to draw the minimum cuts of a planar graph. Computational Geometry: Theory and Applications\u00a029(2), 117\u2013133 (2004)","journal-title":"Computational Geometry: Theory and Applications"},{"unstructured":"L\u00fctke-H\u00fcttmann, D.: Knickminimales Zeichnen 4-planarer Clustergraphen. Master\u2019s thesis, Universit\u00e4t des Saarlandes (1999) (Diplomarbeit)","key":"12_CR9"},{"key":"12_CR10","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"89","DOI":"10.1007\/3-540-49381-6_11","volume-title":"Algorithms and Computation","author":"U. Brandes","year":"1998","unstructured":"Brandes, U., Wagner, D.: Dynamic Grid Embedding with Few Bends and Changes. In: Chwa, K.-Y., Ibarra, O.H. (eds.) ISAAC 1998. LNCS, vol.\u00a01533, pp. 89\u201398. Springer, Heidelberg (1998)"},{"key":"12_CR11","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/3-540-36151-0_1","volume-title":"Graph Drawing","author":"U. Brandes","year":"2002","unstructured":"Brandes, U., Eiglsperger, M., Kaufmann, M., Wagner, D.: Sketch-Driven Orthogonal Graph Drawing. In: Goodrich, M.T., Kobourov, S.G. (eds.) GD 2002. LNCS, vol.\u00a02528, pp. 1\u201311. Springer, Heidelberg (2002)"},{"unstructured":"Ahuja, R.K., Magnanti, T.L., Orlin, J.B.: Network Flows. Prentice-Hall (1993)","key":"12_CR12"},{"key":"12_CR13","volume-title":"Combinatorial Optimization: Polyhedra and Efficiency","author":"A. Schrijver","year":"2003","unstructured":"Schrijver, A.: Combinatorial Optimization: Polyhedra and Efficiency. Springer, Heidelberg (2003)"},{"issue":"4","key":"12_CR14","doi-asserted-by":"publisher","first-page":"373","DOI":"10.1007\/BF02579150","volume":"4","author":"N. Karmarkar","year":"1984","unstructured":"Karmarkar, N.: A new polynomial-time algorithm for linear programming. Combinatorica\u00a04(4), 373\u2013395 (1984)","journal-title":"Combinatorica"},{"key":"12_CR15","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"21","DOI":"10.1007\/3-540-52921-7_52","volume-title":"Algorithms","author":"H. Imai","year":"1990","unstructured":"Imai, H., Iwano, K.: Efficient Sequential and Parallel Algorithms for Planar Minimum Cost Flow. In: Asano, T., Imai, H., Ibaraki, T., Nishizeki, T. (eds.) SIGAL 1990. LNCS, vol.\u00a0450, pp. 21\u201330. Springer, Heidelberg (1990)"},{"key":"12_CR16","doi-asserted-by":"publisher","first-page":"3","DOI":"10.1006\/jcss.1997.1493","volume":"55","author":"M.R. Henzinger","year":"1997","unstructured":"Henzinger, M.R., Klein, P., Rao, S., Subramanian, S.: Faster shortest-path algorithms for planar graphs. Journal of Computer and System Sciences\u00a055, 3\u201323 (1997); Special Issue on Selected Papers from STOC 1994","journal-title":"Journal of Computer and System Sciences"},{"key":"12_CR17","doi-asserted-by":"publisher","first-page":"868","DOI":"10.1016\/j.jcss.2005.05.007","volume":"72","author":"J. Fakcharoenphol","year":"2006","unstructured":"Fakcharoenphol, J., Rao, S.: Planar graphs, negative weight edges, shortest paths, and near linear time. J. Comput. Syst. Sci.\u00a072, 868\u2013889 (2006)","journal-title":"J. Comput. Syst. Sci."},{"key":"12_CR18","doi-asserted-by":"publisher","first-page":"236","DOI":"10.1137\/1.9781611973068.27","volume-title":"Proceedings of the Twentieth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2009","author":"P. Klein","year":"2009","unstructured":"Klein, P., Mozes, S., Weimann, O.: Shortest paths in directed planar graphs with negative lengths: a linear-space O(n log2 n)-time algorithm. In: Proceedings of the Twentieth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2009, pp. 236\u2013245. SIAM, Philadelphia (2009)"},{"key":"12_CR19","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"206","DOI":"10.1007\/978-3-642-15781-3_18","volume-title":"Algorithms \u2013 ESA 2010","author":"S. Mozes","year":"2010","unstructured":"Mozes, S., Wulff-Nilsen, C.: Shortest Paths in Planar Graphs with Real Lengths in O(n log2 n \/ loglogn) Time. In: de Berg, M., Meyer, U. (eds.) ESA 2010. LNCS, vol.\u00a06347, pp. 206\u2013217. Springer, Heidelberg (2010)"},{"key":"12_CR20","doi-asserted-by":"publisher","first-page":"454","DOI":"10.1006\/jcss.1997.1538","volume":"55","author":"K. Weihe","year":"1997","unstructured":"Weihe, K.: Maximum (s,t)-flows in planar networks in O(V log V) time. J. Comput. Syst. Sci.\u00a055, 454\u2013475 (1997)","journal-title":"J. Comput. Syst. Sci."},{"doi-asserted-by":"crossref","unstructured":"Borradaile, G., Klein, P.: An O(n log n) algorithm for maximum st-flow in a directed planar graph. J. ACM\u00a056, 9:1\u20139:30 (2009)","key":"12_CR21","DOI":"10.1145\/1502793.1502798"},{"issue":"3","key":"12_CR22","doi-asserted-by":"publisher","first-page":"107","DOI":"10.1016\/0020-0190(81)90120-4","volume":"13","author":"R. Hassin","year":"1981","unstructured":"Hassin, R.: Maximum flow in (s,t) planar networks. Information Processing Letters\u00a013(3), 107 (1981)","journal-title":"Information Processing Letters"},{"key":"12_CR23","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.: Flow in planar graphs with multiple sources and sinks. SIAM J. Comput.\u00a024, 1002\u20131017 (1995)","journal-title":"SIAM J. Comput."},{"key":"12_CR24","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.C. (ed.) GD 1996. LNCS, vol.\u00a01190, pp. 201\u2013213. Springer, Heidelberg (1997)"},{"key":"12_CR25","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"515","DOI":"10.1007\/978-3-540-24595-7_55","volume-title":"Graph Drawing","author":"F.J. Brandenburg","year":"2004","unstructured":"Brandenburg, F.J., Eppstein, D., Goodrich, M.T., Kobourov, S.G., Liotta, G., Mutzel, P.: Selected Open Problems in Graph Drawing. In: Liotta, G. (ed.) GD 2003. LNCS, vol.\u00a02912, pp. 515\u2013539. Springer, Heidelberg (2004)"},{"issue":"4","key":"12_CR26","doi-asserted-by":"publisher","first-page":"265","DOI":"10.1016\/0022-0000(86)90030-9","volume":"32","author":"G.L. Miller","year":"1986","unstructured":"Miller, G.L.: Finding small simple cycle separators for 2-connected planar graphs. Journal of Computer and System Sciences\u00a032(4), 265\u2013279 (1986)","journal-title":"Journal of Computer and System Sciences"},{"doi-asserted-by":"crossref","unstructured":"Borradaile, G., Klein, P., Mozes, S., Nussbaum, Y., Wulff-Nilsen, C.: Multiple-source multiple-sink maximum flow in directed planar graphs in near-linear time. In: Proceedings of the 52nd Annual Symposium on Foundations of Computer Science, FOCS\u00a0 2011 (to appear, 2011)","key":"12_CR27","DOI":"10.1109\/FOCS.2011.73"},{"unstructured":"Di Battista, G., Eades, P., Tamassia, R., Tollis, I.G.: Graph Drawing: Algorithms for the Visualization of Graphs. Prentice-Hall (1999)","key":"12_CR28"},{"doi-asserted-by":"crossref","unstructured":"Ford, L.R., Fulkerson, D.R.: Flows in Networks. Princeton University Press (1962)","key":"12_CR29","DOI":"10.1515\/9781400875184"},{"key":"12_CR30","doi-asserted-by":"publisher","first-page":"269","DOI":"10.1007\/BF01386390","volume":"1","author":"E.W. Dijkstra","year":"1959","unstructured":"Dijkstra, E.W.: A note on two problems in connexion with graphs. Numerische Mathematik\u00a01, 269\u2013271 (1959)","journal-title":"Numerische Mathematik"},{"issue":"4","key":"12_CR31","doi-asserted-by":"publisher","first-page":"673","DOI":"10.1016\/j.dam.2008.08.002","volume":"157","author":"S. Tazari","year":"2009","unstructured":"Tazari, S., M\u00fcller-Hannemann, M.: Shortest paths in linear time on minor-closed graph classes, with an application to steiner tree approximation. Discrete Applied Mathematics\u00a0157(4), 673\u2013684 (2009)","journal-title":"Discrete Applied Mathematics"}],"container-title":["Lecture Notes in Computer Science","Graph Drawing"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-25878-7_12","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,6,20]],"date-time":"2019-06-20T23:29:34Z","timestamp":1561073374000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-25878-7_12"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012]]},"ISBN":["9783642258770","9783642258787"],"references-count":31,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-25878-7_12","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2012]]}}}