{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,8]],"date-time":"2024-09-08T02:05:16Z","timestamp":1725761116913},"publisher-location":"Cham","reference-count":30,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783319038407"},{"type":"electronic","value":"9783319038414"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2013]]},"DOI":"10.1007\/978-3-319-03841-4_40","type":"book-chapter","created":{"date-parts":[[2013,12,2]],"date-time":"2013-12-02T05:28:55Z","timestamp":1385962135000},"page":"460-471","source":"Crossref","is-referenced-by-count":9,"title":["Using ILP\/SAT to Determine Pathwidth, Visibility Representations, and other Grid-Based Graph Drawings"],"prefix":"10.1007","author":[{"given":"Therese","family":"Biedl","sequence":"first","affiliation":[]},{"given":"Thomas","family":"Bl\u00e4sius","sequence":"additional","affiliation":[]},{"given":"Benjamin","family":"Niedermann","sequence":"additional","affiliation":[]},{"given":"Martin","family":"N\u00f6llenburg","sequence":"additional","affiliation":[]},{"given":"Roman","family":"Prutkin","sequence":"additional","affiliation":[]},{"given":"Ignaz","family":"Rutter","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"40_CR1","unstructured":"Rome graphs, \n                    \n                      http:\/\/www.graphdrawing.org\/download\/rome-graphml.tgz"},{"key":"40_CR2","doi-asserted-by":"crossref","unstructured":"Biedl, T., Bl\u00e4sius, T., Niedermann, B., N\u00f6llenburg, M., Prutkin, R., Rutter, I.: A versatile ILP\/SAT formulation for pathwidth, optimum st-orientation, visibility representation, and other grid-based graph drawing problems. CoRR abs\/1308.6778 (2013)","DOI":"10.1007\/978-3-319-03841-4_40"},{"key":"40_CR3","unstructured":"Biere, A., Heule, M., van Maaren, H., Walsh, T. (eds.): Handbook of Satisfiability. IOS Press (2009)"},{"issue":"2","key":"40_CR4","doi-asserted-by":"publisher","first-page":"71","DOI":"10.1016\/j.comgeo.2005.02.001","volume":"32","author":"C. Binucci","year":"2005","unstructured":"Binucci, C., Didimo, W., Liotta, G., Nonato, M.: Orthogonal drawings of graphs with vertex and edge labels. Comput. Geom. Theory Appl.\u00a032(2), 71\u2013114 (2005)","journal-title":"Comput. Geom. Theory Appl."},{"issue":"2","key":"40_CR5","doi-asserted-by":"publisher","first-page":"238","DOI":"10.1006\/jagm.1995.1009","volume":"18","author":"H.L. Bodlaender","year":"1995","unstructured":"Bodlaender, H.L., Gilbert, J.R., Hafsteinsson, H., Kloks, T.: Approximating treewidth, pathwidth, frontsize, and shortest elimination tree. J. Algorithms\u00a018(2), 238\u2013255 (1995)","journal-title":"J. Algorithms"},{"issue":"2","key":"40_CR6","doi-asserted-by":"publisher","first-page":"358","DOI":"10.1006\/jagm.1996.0049","volume":"21","author":"H.L. Bodlaender","year":"1996","unstructured":"Bodlaender, H.L., Kloks, T.: Efficient and constructive algorithms for the pathwidth and treewidth of graphs. J. Algorithms\u00a021(2), 358\u2013402 (1996)","journal-title":"J. Algorithms"},{"key":"40_CR7","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"247","DOI":"10.1007\/3-540-45749-6_25","volume-title":"Algorithms - ESA 2002","author":"U. Brandes","year":"2002","unstructured":"Brandes, U.: Eager st-ordering. In: M\u00f6hring, R.H., Raman, R. (eds.) ESA 2002. LNCS, vol.\u00a02461, pp. 247\u2013256. Springer, Heidelberg (2002)"},{"issue":"2","key":"40_CR8","doi-asserted-by":"publisher","first-page":"373","DOI":"10.1016\/j.disopt.2007.05.006","volume":"5","author":"C. Buchheim","year":"2008","unstructured":"Buchheim, C., Chimani, M., Ebner, D., Gutwenger, C., J\u00fcnger, M., Klau, G.W., Mutzel, P., Weiskircher, R.: A branch-and-cut approach to the crossing number problem. Discrete Optimization\u00a05(2), 373\u2013388 (2008)","journal-title":"Discrete Optimization"},{"key":"40_CR9","doi-asserted-by":"crossref","unstructured":"Chen, D.S., Batson, R.G., Dang, Y.: Applied Integer Programming. Wiley (2010)","DOI":"10.1002\/9781118166000"},{"key":"40_CR10","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"284","DOI":"10.1007\/978-3-540-87744-8_24","volume-title":"Algorithms - ESA 2008","author":"M. Chimani","year":"2008","unstructured":"Chimani, M., Mutzel, P., Bomze, I.: A new approach to exact crossing minimization. In: Halperin, D., Mehlhorn, K. (eds.) ESA 2008. LNCS, vol.\u00a05193, pp. 284\u2013296. Springer, Heidelberg (2008)"},{"key":"40_CR11","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"248","DOI":"10.1007\/978-3-642-36763-2_22","volume-title":"Graph Drawing","author":"M. Chimani","year":"2013","unstructured":"Chimani, M., Zeranski, R.: Upward planarity testing via SAT. In: Didimo, W., Patrignani, M. (eds.) GD 2012. LNCS, vol.\u00a07704, pp. 248\u2013259. Springer, Heidelberg (2013)"},{"issue":"3","key":"40_CR12","doi-asserted-by":"publisher","first-page":"223","DOI":"10.1002\/jgt.3190060302","volume":"6","author":"P.Z. Chinn","year":"1982","unstructured":"Chinn, P.Z., Chv\u00e1talova, J., Dewdney, A.K., Gibbs, N.E.: The bandwidth problem for graphs and matrices\u2014a survey. J. Graph Theory\u00a06(3), 223\u2013254 (1982)","journal-title":"J. Graph Theory"},{"issue":"1","key":"40_CR13","doi-asserted-by":"publisher","first-page":"45","DOI":"10.7155\/jgaa.00136","volume":"11","author":"A.M. Dean","year":"2007","unstructured":"Dean, A.M., Evans, W., Gethner, E., Laison, J.D., Safari, M.A., Trotter, W.T.: Bar k-visibility graphs. J. Graph Algorithms Appl.\u00a011(1), 45\u201359 (2007)","journal-title":"J. Graph Algorithms Appl."},{"issue":"3","key":"40_CR14","doi-asserted-by":"publisher","first-page":"189","DOI":"10.1007\/s006070050002","volume":"62","author":"G.M. Corso Del","year":"1999","unstructured":"Del Corso, G.M., Manzini, G.: Finding exact solutions to the bandwidth minimization problem. Computing\u00a062(3), 189\u2013203 (1999)","journal-title":"Computing"},{"issue":"2","key":"40_CR15","doi-asserted-by":"publisher","first-page":"267","DOI":"10.1007\/s00453-007-9151-1","volume":"52","author":"V. Dujmovic","year":"2008","unstructured":"Dujmovic, V., Fellows, M.R., Kitching, M., Liotta, G., McCartin, C., Nishimura, N., Ragde, P., Rosamond, F.A., Whitesides, S., Wood, D.R.: On the parameterized complexity of layered graph drawing. Algorithmica\u00a052(2), 267\u2013292 (2008)","journal-title":"Algorithmica"},{"key":"40_CR16","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"502","DOI":"10.1007\/978-3-540-24605-3_37","volume-title":"Theory and Applications of Satisfiability Testing","author":"N. E\u00e9n","year":"2004","unstructured":"E\u00e9n, N., S\u00f6rensson, N.: An extensible SAT-solver. In: Giunchiglia, E., Tacchella, A. (eds.) SAT 2003. LNCS, vol.\u00a02919, pp. 502\u2013518. Springer, Heidelberg (2004)"},{"issue":"3","key":"40_CR17","doi-asserted-by":"publisher","first-page":"339","DOI":"10.1016\/0304-3975(76)90086-4","volume":"2","author":"S. Even","year":"1976","unstructured":"Even, S., Tarjan, R.E.: Computing an st-numbering. Theoret. Comput. Sci.\u00a02(3), 339\u2013344 (1976)","journal-title":"Theoret. Comput. Sci."},{"issue":"4","key":"40_CR18","doi-asserted-by":"publisher","first-page":"363","DOI":"10.7155\/jgaa.00075","volume":"7","author":"S. Felsner","year":"2003","unstructured":"Felsner, S., Liotta, G., Wismath, S.: Straight-line drawings on restricted integer grids in two and three dimensions. J. Graph Algorithms Appl.\u00a07(4), 363\u2013398 (2003)","journal-title":"J. Graph Algorithms Appl."},{"key":"40_CR19","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"238","DOI":"10.1007\/978-3-642-18469-7_22","volume-title":"Graph Drawing","author":"G. Gange","year":"2011","unstructured":"Gange, G., Stuckey, P.J., Marriott, K.: Optimal k-level planarization and crossing minimization. In: Brandes, U., Cornelsen, S. (eds.) GD 2010. LNCS, vol.\u00a06502, pp. 238\u2013249. Springer, Heidelberg (2011)"},{"key":"40_CR20","unstructured":"Gurobi Optimization, Inc.: Gurobi optimizer reference manual (2013)"},{"issue":"4","key":"40_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\u00a021(4), 549\u2013568 (1974)","journal-title":"J. ACM"},{"issue":"1","key":"40_CR22","doi-asserted-by":"publisher","first-page":"1","DOI":"10.7155\/jgaa.00001","volume":"1","author":"M. J\u00fcnger","year":"1997","unstructured":"J\u00fcnger, M., Mutzel, P.: 2-layer straightline crossing minimization: Performance of exact and heuristic algorithms. J. Graph Algorithms Appl.\u00a01(1), 1\u201325 (1997)","journal-title":"J. Graph Algorithms Appl."},{"issue":"3","key":"40_CR23","doi-asserted-by":"publisher","first-page":"233","DOI":"10.1016\/0166-218X(94)90143-0","volume":"52","author":"J. Kratochv\u00edl","year":"1994","unstructured":"Kratochv\u00edl, J.: A special planar satisfiability problem and a consequence of its NP-completeness. Discrete Appl. Math.\u00a052(3), 233\u2013252 (1994)","journal-title":"Discrete Appl. Math."},{"issue":"3","key":"40_CR24","doi-asserted-by":"publisher","first-page":"679","DOI":"10.1016\/S0304-3975(02)00031-2","volume":"292","author":"X. Lin","year":"2003","unstructured":"Lin, X., Eades, P.: Towards area requirements for drawing hierarchically planar graphs. Theoret. Comput. Sci.\u00a0292(3), 679\u2013695 (2003)","journal-title":"Theoret. Comput. Sci."},{"key":"40_CR25","doi-asserted-by":"publisher","first-page":"513","DOI":"10.1016\/j.ejor.2007.02.004","volume":"186","author":"R. Mart\u00ed","year":"2008","unstructured":"Mart\u00ed, R., Campos, V., Pi\u00f1ana, E.: A branch and bound algorithm for the matrix bandwidth minimization. Europ. J. of Operational Research\u00a0186, 513\u2013528 (2008)","journal-title":"Europ. J. of Operational Research"},{"issue":"5","key":"40_CR26","first-page":"626","volume":"17","author":"M. N\u00f6llenburg","year":"2011","unstructured":"N\u00f6llenburg, M., Wolff, A.: Drawing and labeling high-quality metro maps by mixed-integer programming. IEEE TVCG\u00a017(5), 626\u2013641 (2011)","journal-title":"IEEE TVCG"},{"issue":"2","key":"40_CR27","doi-asserted-by":"publisher","first-page":"337","DOI":"10.7155\/jgaa.00210","volume":"14","author":"C. Papamanthou","year":"2010","unstructured":"Papamanthou, C., G. Tollis, I.: Applications of parameterized st-orientations. J. Graph Algorithms Appl.\u00a014(2), 337\u2013365 (2010)","journal-title":"J. Graph Algorithms Appl."},{"issue":"7-9","key":"40_CR28","doi-asserted-by":"publisher","first-page":"995","DOI":"10.1016\/j.tcs.2009.11.006","volume":"411","author":"S. Sadasivam","year":"2010","unstructured":"Sadasivam, S., Zhang, H.: NP-completeness of st-orientations for plane graphs. Theoret. Comput. Sci.\u00a0411(7-9), 995\u20131003 (2010)","journal-title":"Theoret. Comput. Sci."},{"issue":"1","key":"40_CR29","doi-asserted-by":"publisher","first-page":"321","DOI":"10.1007\/BF02187705","volume":"1","author":"R. Tamassia","year":"1986","unstructured":"Tamassia, R., Tollis, I.: A unified approach to visibility representations of planar graphs. Discrete Comput. Geom.\u00a01(1), 321\u2013341 (1986)","journal-title":"Discrete Comput. Geom."},{"key":"40_CR30","first-page":"147","volume-title":"Proc. First Ann. Symp. Comput. Geom., SCG 1985","author":"S.K. Wismath","year":"1985","unstructured":"Wismath, S.K.: Characterizing bar line-of-sight graphs. In: Proc. First Ann. Symp. Comput. Geom., SCG 1985, pp. 147\u2013152. ACM, New York (1985)"}],"container-title":["Lecture Notes in Computer Science","Graph Drawing"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-03841-4_40","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,25]],"date-time":"2019-05-25T01:44:53Z","timestamp":1558748693000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-319-03841-4_40"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013]]},"ISBN":["9783319038407","9783319038414"],"references-count":30,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-03841-4_40","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2013]]}}}