{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,12,22]],"date-time":"2025-12-22T04:30:37Z","timestamp":1766377837281},"publisher-location":"Berlin, Heidelberg","reference-count":136,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540208310"},{"type":"electronic","value":"9783540245957"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2004]]},"DOI":"10.1007\/978-3-540-24595-7_55","type":"book-chapter","created":{"date-parts":[[2010,7,29]],"date-time":"2010-07-29T08:46:01Z","timestamp":1280393161000},"page":"515-539","source":"Crossref","is-referenced-by-count":30,"title":["Selected Open Problems in Graph Drawing"],"prefix":"10.1007","author":[{"given":"Franz","family":"Brandenburg","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"David","family":"Eppstein","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Michael T.","family":"Goodrich","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Stephen","family":"Kobourov","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Giuseppe","family":"Liotta","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Petra","family":"Mutzel","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"55_CR1","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"147","DOI":"10.1007\/3-540-58950-3_366","volume-title":"Graph Drawing","author":"J. Abello","year":"1995","unstructured":"Abello, J., Kumar, K.: Visibility graphs and oriented matroids. In: Tamassia, R., Tollis, I.G. (eds.) GD 1994. LNCS, vol.\u00a0894, pp. 147\u2013158. Springer, Heidelberg (1995)"},{"key":"55_CR2","doi-asserted-by":"publisher","first-page":"339","DOI":"10.1007\/BF02712872","volume":"16","author":"O. Aichholzer","year":"1996","unstructured":"Aichholzer, O., Aurenhammer, F., Chen, S.-W., Katoh, N., Taschwer, M., Rote, G., Xu, Y.-F.: Triangulations intersect nicely. Discrete Comput. Geom.\u00a016, 339\u2013359 (1996)","journal-title":"Discrete Comput. Geom."},{"key":"55_CR3","first-page":"19","volume-title":"Proceedings of the 18th ACM Symposium on Computational Geometry","author":"O. Aichholzer","year":"2002","unstructured":"Aichholzer, O., Aurenhammer, F., Krasser, H.: On the crossing number of complete graphs. In: Proceedings of the 18th ACM Symposium on Computational Geometry, pp. 19\u201324. ACM Press, New York (2002)"},{"key":"55_CR4","doi-asserted-by":"publisher","first-page":"127","DOI":"10.1007\/BF01215345","volume":"14","author":"B. Aronov","year":"1994","unstructured":"Aronov, B., Erd\u0151s, P., Goddard, W., Kleitman, D.J., Klugerman, M., Pach, J., Schulman, L.J.: Crossing families. Combinatorica\u00a014, 127\u2013134 (1994)","journal-title":"Combinatorica"},{"key":"55_CR5","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"130","DOI":"10.1007\/3-540-36151-0_13","volume-title":"Graph Drawing","author":"W. Barth","year":"2002","unstructured":"Barth, W., J\u00fcnger, M., Mutzel, P.: Simple and efficient cross counting. In: Goodrich, M.T., Kobourov, S.G. (eds.) GD 2002. LNCS, vol.\u00a02528, pp. 130\u2013141. Springer, Heidelberg (2002)"},{"key":"55_CR6","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"331","DOI":"10.1007\/3-540-63307-3_72","volume-title":"Algorithms and Data Structures","author":"P. Bertolazzi","year":"1997","unstructured":"Bertolazzi, P., Di Battista, G., Didimo, W.: Computing orthogonal drawings with the minimum number of bends. In: Rau-Chaplin, A., Dehne, F., Sack, J.-R., Tamassia, R. (eds.) WADS 1997. LNCS, vol.\u00a01272, pp. 331\u2013344. Springer, Heidelberg (1997)"},{"key":"55_CR7","doi-asserted-by":"publisher","first-page":"263","DOI":"10.1016\/0020-0190(87)90173-6","volume":"25","author":"S. Bhatt","year":"1987","unstructured":"Bhatt, S., Cosmadakis, S.: The complexity of minimizing wire lengths in VLSI layouts. Inform. Process. Lett.\u00a025, 263\u2013267 (1987)","journal-title":"Inform. Process. Lett."},{"key":"55_CR8","doi-asserted-by":"publisher","first-page":"300","DOI":"10.1016\/0022-0000(84)90071-0","volume":"28","author":"S.N. Bhatt","year":"1984","unstructured":"Bhatt, S.N., Leighton, F.T.: A framework for solving VLSI graph layout problems. J. Comput. Syst. Sci.\u00a028, 300\u2013343 (1984)","journal-title":"J. Comput. Syst. Sci."},{"key":"55_CR9","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"54","DOI":"10.1007\/3-540-36151-0_6","volume-title":"Graph Drawing","author":"T. Biedl","year":"2002","unstructured":"Biedl, T.: Drawing outer-planar graphs in O(n log n) area. In: Goodrich, M. (ed.) GD 2002. LNCS, vol.\u00a02528, pp. 54\u201365. Springer, Heidelberg (2002)"},{"key":"55_CR10","doi-asserted-by":"publisher","first-page":"333","DOI":"10.1002\/jgt.3190170308","volume":"17","author":"D. Bienstock","year":"1993","unstructured":"Bienstock, D., Dean, N.: Bounds for rectilinear crossing numbers. J. Graph Theory\u00a017, 333 (1993)","journal-title":"J. Graph Theory"},{"key":"55_CR11","unstructured":"Blankenship, R., Oporowski, B.: Book embeddings of graphs and minor-closed classes. In: Thirty-Second Southeastern Internat. Conf. Combinatorics, Graph Theory and Computing, Baton Rouge. Dept. of Mathematics, p. 30. Louisiana State University (2001), http:\/\/www.math.lsu.edu\/~conf_se\/program.pdf"},{"issue":"3","key":"55_CR12","doi-asserted-by":"publisher","first-page":"303","DOI":"10.1016\/S0925-7721(01)00069-4","volume":"23","author":"P. Bose","year":"2002","unstructured":"Bose, P.: On embedding an outer-planar graph in a point set. Comput. Geom.\u00a023(3), 303\u2013312 (2002)","journal-title":"Comput. Geom."},{"key":"55_CR13","doi-asserted-by":"publisher","first-page":"83","DOI":"10.1007\/BF02086609","volume":"16","author":"P. Bose","year":"1996","unstructured":"Bose, P., Lenhart, W., Liotta, G.: Characterizing proximity trees. Algorithmica\u00a016, 83\u2013110 (1996)","journal-title":"Algorithmica"},{"issue":"2","key":"55_CR14","doi-asserted-by":"publisher","first-page":"191","DOI":"10.1007\/PL00009495","volume":"23","author":"G. Cairns","year":"2000","unstructured":"Cairns, G., Nikolayevsky, Y.: Bounds for generalized thrackles. Discrete Comput. Geom.\u00a023(2), 191\u2013206 (2000)","journal-title":"Discrete Comput. Geom."},{"issue":"2","key":"55_CR15","doi-asserted-by":"publisher","first-page":"97","DOI":"10.1016\/S0020-0190(97)00098-7","volume":"63","author":"T. Calamoneri","year":"1997","unstructured":"Calamoneri, T., Sterbini, A.: 3D straight-line grid drawing of 4-colorable graphs. Inform. Process. Lett.\u00a063(2), 97\u2013102 (1997)","journal-title":"Inform. Process. Lett."},{"key":"55_CR16","unstructured":"Calinescu, G., Fernandes, C.G., Finkler, U., Karloff, H.: A better approximation algorithm for finding planar subgraphs. In: Proc. 7th ACM-SIAM Symp. on Discrete Algorithms (SODA), pp. 16\u201325 (1996)"},{"key":"55_CR17","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/s00453-002-0937-x","volume":"34","author":"T. Chan","year":"2001","unstructured":"Chan, T.: A near-linear area bound for drawing binary trees. Algorithmica\u00a034, 1\u201313 (2001)","journal-title":"Algorithmica"},{"key":"55_CR18","series-title":"Lecture Notes in Computer Science","first-page":"63","volume-title":"Graph Drawing","author":"T.M. Chan","year":"1997","unstructured":"Chan, T.M., Goodrich, M.T., Kosaraju, S.R., Tamassia, R.: Optimizing area and aspect ratio in straight-line orthogonal tree drawings. In: North, S.C. (ed.) GD 1996. LNCS, vol.\u00a01190, pp. 63\u201375. Springer, Heidelberg (1997)"},{"key":"55_CR19","doi-asserted-by":"publisher","first-page":"156","DOI":"10.1016\/0022-0000(86)90025-5","volume":"32","author":"B. Chazelle","year":"1986","unstructured":"Chazelle, B.: Reporting and counting segment intersections. J. Comput. Syst. Sci.\u00a032, 156\u2013182 (1986)","journal-title":"J. Comput. Syst. Sci."},{"key":"55_CR20","doi-asserted-by":"publisher","first-page":"485","DOI":"10.1007\/BF02574703","volume":"6","author":"B. Chazelle","year":"1991","unstructured":"Chazelle, B.: Triangulating a simple polygon in linear time. Discrete Comput. Geom.\u00a06, 485\u2013524 (1991)","journal-title":"Discrete Comput. Geom."},{"issue":"2","key":"55_CR21","doi-asserted-by":"publisher","first-page":"135","DOI":"10.1145\/357337.357340","volume":"3","author":"B. Chazelle","year":"1984","unstructured":"Chazelle, B., Incerpi, J.: Triangulation and shape-complexity. ACM Trans. Graph.\u00a03(2), 135\u2013152 (1984)","journal-title":"ACM Trans. Graph."},{"issue":"1-2","key":"55_CR22","doi-asserted-by":"publisher","first-page":"459","DOI":"10.1016\/S0304-3975(00)00318-2","volume":"262","author":"S.-W. Cheng","year":"2001","unstructured":"Cheng, S.-W., Xu, Y.-F.: On \u03b2-skeleton as a subgraph of the minimum weight triangulation. Theoretical Computer Science\u00a0262(1-2), 459\u2013471 (2001)","journal-title":"Theoretical Computer Science"},{"key":"55_CR23","doi-asserted-by":"crossref","unstructured":"Chrobak, M., Goodrich, M.T., Tamassia, R.: Convex drawings of graphs in two and three dimensions. In: Proc. 12th Annu. ACM Sympos. Comput. Geom., pp. 319\u2013328 (1996)","DOI":"10.1145\/237218.237401"},{"key":"55_CR24","doi-asserted-by":"crossref","first-page":"29","DOI":"10.1016\/S0925-7721(98)00016-9","volume":"11","author":"M. Chrobak","year":"1998","unstructured":"Chrobak, M., Ichi Nakano, S.: Minimum-width grid drawings of plane graphs. Comput. Geom. Theory Appl.\u00a011, 29\u201354 (1998)","journal-title":"Comput. Geom. Theory Appl."},{"issue":"3","key":"55_CR25","doi-asserted-by":"publisher","first-page":"211","DOI":"10.1142\/S0218195997000144","volume":"7","author":"M. Chrobak","year":"1997","unstructured":"Chrobak, M., Kant, G.: Convex grid drawings of 3-connected planar graphs. Internat. J. Comput. Geom. Appl.\u00a07(3), 211\u2013223 (1997)","journal-title":"Internat. J. Comput. Geom. Appl."},{"key":"55_CR26","doi-asserted-by":"crossref","unstructured":"Chrobak, M., Karloff, H.: A lower bound on the size of universal sets for planar graphs. SIGACT News\u00a020 (1989)","DOI":"10.1145\/74074.74088"},{"key":"55_CR27","doi-asserted-by":"publisher","first-page":"199","DOI":"10.1007\/BF02522826","volume":"17","author":"R.F. Cohen","year":"1997","unstructured":"Cohen, R.F., Eades, P., Lin, T., Ruskey, F.: Three-dimensional graph drawing. Algorithmica\u00a017, 199\u2013208 (1997)","journal-title":"Algorithmica"},{"key":"55_CR28","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"239","DOI":"10.1007\/BFb0054325","volume-title":"LATIN\u201998: Theoretical Informatics","author":"E. Dahlhaus","year":"1998","unstructured":"Dahlhaus, E.: Linear time algorithm to recognize clustered planar graphs and its parallelization. In: Lucchesi, C.L., Moura, A.V. (eds.) LATIN 1998. LNCS, vol.\u00a01380, pp. 239\u2013248. Springer, Heidelberg (1998)"},{"issue":"1","key":"55_CR29","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(1), 41\u201351 (1990)","journal-title":"Combinatorica"},{"key":"55_CR30","doi-asserted-by":"crossref","first-page":"187","DOI":"10.1016\/S0925-7721(98)00039-X","volume":"11","author":"O. Devillers","year":"1998","unstructured":"Devillers, O., Liotta, G., Preparata, F.P., Tamassia, R.: Checking the convexity of polytopes and the planarity of subdivisions. Comput. Geom. Theory Appl.\u00a011, 187\u2013208 (1998)","journal-title":"Comput. Geom. Theory Appl."},{"key":"55_CR31","volume-title":"Graph Drawing","author":"G. Battista Di","year":"1999","unstructured":"Di Battista, G., Eades, P., Tamassia, R., Tollis, I.G.: Graph Drawing. Prentice Hall, Upper Saddle River (1999)"},{"key":"55_CR32","doi-asserted-by":"crossref","first-page":"303","DOI":"10.1016\/S0925-7721(96)00005-3","volume":"7","author":"G. Battista Di","year":"1997","unstructured":"Di Battista, G., Garg, A., Liotta, G., Tamassia, R., Tassinari, E., Vargiu, F.: An experimental comparison of four graph drawing algorithms. Comput. Geom. Theory Appl.\u00a07, 303\u2013325 (1997)","journal-title":"Comput. Geom. Theory Appl."},{"key":"55_CR33","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"72","DOI":"10.1007\/3-540-37623-2_6","volume-title":"Graph Drawing","author":"G. Battista Di","year":"1999","unstructured":"Di Battista, G., Liotta, G.: Upward planarity checking: Faces are more than polygons. In: Whitesides, S.H. (ed.) GD 1998. LNCS, vol.\u00a01547, pp. 72\u201386. Springer, Heidelberg (1999)"},{"key":"55_CR34","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"272","DOI":"10.1007\/3-540-44541-2_26","volume-title":"Graph Drawing","author":"G. Battista Di","year":"2001","unstructured":"Di Battista, G., Liotta, G., Lubiw, A., Whitesides, S.: Orthogonal drawings of cycles in 3D space. In: Marks, J. (ed.) GD 2000. LNCS, vol.\u00a01984, pp. 272\u2013283. Springer, Heidelberg (2001)"},{"issue":"2","key":"55_CR35","doi-asserted-by":"publisher","first-page":"897","DOI":"10.1016\/S0304-3975(01)00408-X","volume":"289","author":"G. Battista Di","year":"2002","unstructured":"Di Battista, G., Liotta, G., Lubiw, A., Whitesides, S.: Embedding problems for paths with direction constrained edges. Theoretical Computer Science\u00a0289(2), 897\u2013917 (2002)","journal-title":"Theoretical Computer Science"},{"issue":"6","key":"55_CR36","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 orhogonal drawings. SIAM J. Comput.\u00a027(6), 1764\u20131811 (1998)","journal-title":"SIAM J. Comput."},{"issue":"3","key":"55_CR37","doi-asserted-by":"publisher","first-page":"349","DOI":"10.1137\/S0895480194264010","volume":"9","author":"G. Battista Di","year":"1996","unstructured":"Di Battista, G., Vismara, L.: Angles of planar triangular graphs. SIAM J. Discrete Math.\u00a09(3), 349\u2013359 (1996)","journal-title":"SIAM J. Discrete Math."},{"key":"55_CR38","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"238","DOI":"10.1007\/978-3-540-24595-7_22","volume-title":"Graph Drawing","author":"E. Giacomo Di","year":"2004","unstructured":"Di Giacomo, E.: Drawing series-parallel graphs on restricted integer 3D grids. In: Liotta, G. (ed.) GD 2003. LNCS, vol.\u00a02912, pp. 238\u2013246. Springer, Heidelberg (2004)"},{"key":"55_CR39","unstructured":"Di Giacomo, E., Liotta, G., Meijer, H.: 3D straight-line drawings of k-trees. Technical Report TR-2003-473, Queen\u2019s University, School of Computing (2003)"},{"key":"55_CR40","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"142","DOI":"10.1007\/3-540-36151-0_14","volume-title":"Graph Drawing","author":"E. Giacomo Di","year":"2002","unstructured":"Di Giacomo, E., Liotta, G., Patrignani, M.: Orthogonal 3D shapes of theta graphs. In: Goodrich, M. (ed.) GD 2002. LNCS, vol.\u00a02528, pp. 142\u2013149. Springer, Heidelberg (2002)"},{"key":"55_CR41","unstructured":"Di Giacomo, E., Liotta, G., Wismath, S.: Drawing series-parallel graphs on a box. In: 14th Canadian Conference On Computational Geometry, CCCG 2002 (2002)"},{"key":"55_CR42","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"214","DOI":"10.1007\/978-3-540-24595-7_20","volume-title":"Graph Drawing","author":"E. Giacomo Di","year":"2004","unstructured":"Di Giacomo, E., Meijer, H.: Track drawings of graphs with constant queue number. In: Liotta, G. (ed.) GD 2003. LNCS, vol.\u00a02912, pp. 214\u2013225. Springer, Heidelberg (2004)"},{"key":"55_CR43","doi-asserted-by":"publisher","first-page":"289","DOI":"10.1007\/PL00009320","volume":"18","author":"M. Dickerson","year":"1997","unstructured":"Dickerson, M., Keil, J., Montague, M.: A large subgraph of the minimum weight triangulation. Discrete and Computational Geometry\u00a018, 289\u2013304 (1997)","journal-title":"Discrete and Computational Geometry"},{"key":"55_CR44","doi-asserted-by":"crossref","unstructured":"Dickerson, M.T., Montague, M.H.: A (usually?) connected subgraph of the minimum weight triangulation. In: Proc. 12th Annu. ACM Sympos. Comput. Geom., pp. 204\u2013213 (1996)","DOI":"10.1145\/237218.237364"},{"key":"55_CR45","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"96","DOI":"10.1007\/3-540-45848-4_8","volume-title":"Graph Drawing","author":"H. Dijdjev","year":"2002","unstructured":"Dijdjev, H., Vr\u0165o, I.: An improved lower bound for crossing numbers. In: Mutzel, P., J\u00fcnger, M., Leipert, S. (eds.) GD 2001. LNCS, vol.\u00a02265, p. 96. Springer, Heidelberg (2002) (to appear)"},{"issue":"6","key":"55_CR46","doi-asserted-by":"publisher","first-page":"283","DOI":"10.1016\/0020-0190(90)90210-O","volume":"33","author":"M.B. Dillencourt","year":"1990","unstructured":"Dillencourt, M.B.: Realizability of Delaunay triangulations. Inform. Process. Lett.\u00a033(6), 283\u2013287 (1990)","journal-title":"Inform. Process. Lett."},{"issue":"3","key":"55_CR47","doi-asserted-by":"crossref","first-page":"5","DOI":"10.7155\/jgaa.00023","volume":"4","author":"M.B. Dillencourt","year":"2000","unstructured":"Dillencourt, M.B., Eppstein, D., Hirschberg, D.S.: Geometric thickness of complete graphs. J. Graph Algorithms & Applications\u00a04(3), 5\u201317 (2000)","journal-title":"J. Graph Algorithms & Applications"},{"key":"55_CR48","unstructured":"Dillencourt, M.B., Smith, W.D.: Graph-theoretical conditions for inscribability and Delaunay realizability. In: Proc. 6th Canad. Conf. Comput. Geom., pp. 287\u2013292 (1994)"},{"key":"55_CR49","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"488","DOI":"10.1007\/3-540-44676-1_41","volume-title":"Algorithms - ESA 2001","author":"V. Dujmovi\u0107","year":"2001","unstructured":"Dujmovi\u0107, V., Fellows, M., Hallett, M., Kitching, M., Liotta, G., McCartin, C., Nishimura, N., Radge, P., Rosamond, F., Suderman, M., Whitesides, S., Wood, D.: On the parameterized complexity of layered graph drawing. In: Meyer auf der Heide, F. (ed.) ESA 2001. LNCS, vol.\u00a02161, pp. 488\u2013499. Springer, Heidelberg (2001)"},{"key":"55_CR50","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"42","DOI":"10.1007\/3-540-36151-0_5","volume-title":"Graph Drawing","author":"V. Dujmovi\u0107","year":"2002","unstructured":"Dujmovi\u0107, V., Morin, P., Wood, D.: Pathwidth and three-dimensional straight line grid drawings of graphs. In: Goodrich, M.T., Kobourov, S.G. (eds.) GD 2002. LNCS, vol.\u00a02528, pp. 42\u201353. Springer, Heidelberg (2002)"},{"key":"55_CR51","unstructured":"Dujmovi\u0107, V., Wood, D.R.: Tree-partitions of k-trees with applications in graph layout. Technical Report 02-03, Dept. Comput. Sci., Carleton Univ., Ottawa, Canada (2002)"},{"key":"55_CR52","unstructured":"Dujmovi\u0107, V., Wood, D.R.: On linear layouts of graphs. Technical Report 03-05, Dept. Comput. Sci., Carleton Univ., Ottawa, Canada (2003)"},{"key":"55_CR53","unstructured":"Dujmovi\u0107, V., Wood, D.R.: Stacks, queues and tracks: Layouts of graphs subdivisions. Technical Report 03-07, Dept. Comput. Sci., Carleton Univ., Ottawa, Canada (2003)"},{"key":"55_CR54","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"190","DOI":"10.1007\/978-3-540-24595-7_18","volume-title":"Graph Drawing","author":"V. Dujmovi\u0107","year":"2004","unstructured":"Dujmovi\u0107, V., Wood, D.R.: Three-dimensional grid drawings with subquadratic volume. In: Liotta, G. (ed.) GD 2003. LNCS, vol.\u00a02912, pp. 190\u2013201. Springer, Heidelberg (2004); These processing"},{"key":"55_CR55","unstructured":"Dujmovi\u0107, V., Wood, D.R.: Track layouts of graphs. Technical Report 03-06, Dept. Comput. Sci., Carleton Univ., Ottawa, Canada (2003)"},{"key":"55_CR56","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"205","DOI":"10.1007\/978-3-540-39890-5_18","volume-title":"Graph-Theoretic Concepts in Computer Science","author":"V. Dujmovi\u0107","year":"2003","unstructured":"Dujmovi\u0107, V., Wood, D.R.: Tree-partitions of k-trees with application in graph layout. In: Bodlaender, H.L. (ed.) WG 2003. LNCS, vol.\u00a02880, pp. 205\u2013217. Springer, Heidelberg (2003) (to appear)"},{"key":"55_CR57","doi-asserted-by":"publisher","first-page":"60","DOI":"10.1007\/BF02086608","volume":"16","author":"P. Eades","year":"1996","unstructured":"Eades, P., Whitesides, S.: The realization problem for Euclidean minimum spanning trees is NP-hard. Algorithmica\u00a016, 60\u201382 (1996); (Di Battista, G., Tamassia, R.(ed.) special issue on Graph Drawing)","journal-title":"Algorithmica"},{"key":"55_CR58","unstructured":"Edler, B.: Effiziente Algorithmen f\u00fcr fl\u00e4chenminimale Layouts von B\u00e4umen. Diplomarbeit, Universit\u00e4t Passau (1999)"},{"key":"55_CR59","doi-asserted-by":"publisher","first-page":"191","DOI":"10.1007\/BF02263430","volume":"31","author":"H. ElGindy","year":"1983","unstructured":"ElGindy, H., Avis, D., Toussaint, G.T.: Applications of a two-dimensional hidden-line algorithm to other geometric problems. Computing\u00a031, 191\u2013202 (1983)","journal-title":"Computing"},{"key":"55_CR60","doi-asserted-by":"publisher","first-page":"296","DOI":"10.1145\/335305.335340","volume-title":"Proceedings of the 32nd ACM Symposium on Theory of Computing (STOC 2000)","author":"G. Even","year":"2000","unstructured":"Even, G., Guha, S., Schieber, B.: Improved approximations of crossings in graph drawing and VLSI layout area. In: Proceedings of the 32nd ACM Symposium on Theory of Computing (STOC 2000), pp. 296\u2013305. ACM Press, New York (2000)"},{"key":"55_CR61","unstructured":"Everett, H.: Visibility graph recognition. Report 231\/90, Dept. Comput. Sci., Univ. Toronto, Toronto, ON. Ph.D. Thesis (1990)"},{"issue":"1","key":"55_CR62","doi-asserted-by":"publisher","first-page":"19","DOI":"10.1023\/A:1010604726900","volume":"18","author":"S. Felsner","year":"2001","unstructured":"Felsner, S.: Convex drawings of planar graphs and the order dimension of 3-polytopes. Order\u00a018(1), 19\u201337 (2001)","journal-title":"Order"},{"key":"55_CR63","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"328","DOI":"10.1007\/3-540-45848-4_26","volume-title":"Graph Drawing","author":"S. Felsner","year":"2002","unstructured":"Felsner, S., Liotta, G., Wismath, S.: Straight line drawings on restricted integer grids in two and three dimensions. In: Mutzel, P., J\u00fcnger, M., Leipert, S. (eds.) GD 2001. LNCS, vol.\u00a02265, pp. 328\u2013342. Springer, Heidelberg (2002)"},{"key":"55_CR64","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"213","DOI":"10.1007\/3-540-60313-1_145","volume-title":"Algorithms - ESA \u201995","author":"Q.-W. Feng","year":"1995","unstructured":"Feng, Q.-W., Cohen, R.F., Eades, P.: Planarity for clustered graphs. In: Spirakis, P.G. (ed.) ESA 1995. LNCS, vol.\u00a0979, pp. 213\u2013226. Springer, Heidelberg (1995)"},{"key":"55_CR65","volume-title":"Computers and Intractability: A Guide to the Theory of NP-Completeness","author":"M.R. Garey","year":"1979","unstructured":"Garey, M.R., Johnson, D.S.: Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman, New York (1979)"},{"key":"55_CR66","doi-asserted-by":"publisher","first-page":"175","DOI":"10.1016\/0020-0190(78)90062-5","volume":"7","author":"M.R. Garey","year":"1978","unstructured":"Garey, M.R., Johnson, D.S., Preparata, F.P., Tarjan, R.E.: Triangulating a simple polygon. Inform. Process. Lett.\u00a07, 175\u2013179 (1978)","journal-title":"Inform. Process. Lett."},{"issue":"1-2","key":"55_CR67","doi-asserted-by":"crossref","first-page":"43","DOI":"10.1016\/S0925-7721(97)00016-3","volume":"9","author":"A. Garg","year":"1998","unstructured":"Garg, A.: New results on drawing angle graphs. Comput. Geom. Theory Appl.\u00a09(1-2), 43\u201382 (1998)","journal-title":"Comput. Geom. Theory Appl."},{"key":"55_CR68","doi-asserted-by":"publisher","first-page":"333","DOI":"10.1142\/S0218195996000228","volume":"6","author":"A. Garg","year":"1996","unstructured":"Garg, A., Goodrich, M.T., Tamassia, R.: Planar upward tree drawings with optimal area. Internat. J. Comput. Geom. Appl.\u00a06, 333\u2013356 (1996)","journal-title":"Internat. J. Comput. Geom. Appl."},{"key":"55_CR69","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"38","DOI":"10.1007\/3-540-46648-7_4","volume-title":"Graph Drawing","author":"A. Garg","year":"1999","unstructured":"Garg, A., Liotta, G.: Almost bend-optimal planar orthogonal drawings of biconnected degree-3 planar graphs in quadratic time. In: Kratochv\u00edl, J. (ed.) GD 1999. LNCS, vol.\u00a01731, p. 38. Springer, Heidelberg (1999)"},{"key":"55_CR70","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"320","DOI":"10.1007\/3-540-36151-0_30","volume-title":"Graph Drawing","author":"A. Garg","year":"2002","unstructured":"Garg, A., Rusu, A.: Straight-line drawings of binary trees with linear area and good aspect ratio. In: Goodrich, M. (ed.) GD 2002. LNCS, vol.\u00a02528, pp. 320\u2013331. Springer, Heidelberg (2002)"},{"key":"55_CR71","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"129","DOI":"10.1007\/978-3-540-24595-7_12","volume-title":"Graph Drawing","author":"A. Garg","year":"2004","unstructured":"Garg, A., Rusu, A.: Area-efficient drawings of outerplanar graphs. In: Liotta, G. (ed.) GD 2003. LNCS, vol.\u00a02912, pp. 129\u2013134. Springer, Heidelberg (2004); These proceedings"},{"key":"55_CR72","series-title":"Lecture Notes in Computer Science","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, Springer, Heidelberg (1997)"},{"issue":"2","key":"55_CR73","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.\u00a031(2), 601\u2013625 (2001)","journal-title":"SIAM J. Comput."},{"key":"55_CR74","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"12","DOI":"10.1007\/3-540-61680-2_43","volume-title":"Algorithms - ESA \u201996","author":"A. Garg","year":"1996","unstructured":"Garg, A., Tamassia, R., Vocca, P.: Drawing with colors. In: D\u00edaz, J. (ed.) ESA 1996. LNCS, vol.\u00a01136, pp. 12\u201326. Springer, Heidelberg (1996)"},{"key":"55_CR75","doi-asserted-by":"publisher","first-page":"143","DOI":"10.1007\/BF02770871","volume":"17","author":"S.K. Ghosh","year":"1997","unstructured":"Ghosh, S.K.: On recognizing and characterizing visibility graphs of simple polygons. Discrete Comput. Geom.\u00a017, 143\u2013162 (1997)","journal-title":"Discrete Comput. Geom."},{"key":"55_CR76","doi-asserted-by":"publisher","first-page":"167","DOI":"10.1016\/0020-0190(89)90118-X","volume":"31","author":"A. Gregori","year":"1989","unstructured":"Gregori, A.: Unit length embedding of binary trees on a square grid. Inform. Process. Lett.\u00a031, 167\u2013172 (1989)","journal-title":"Process. Lett."},{"key":"55_CR77","first-page":"231","volume-title":"Proceedings of the 32nd ACM Symposium on Theory of Computing (STOC 2000)","author":"M. Grohe","year":"2000","unstructured":"Grohe, M.: Computing crossing numbers in quadratic time. In: Proceedings of the 32nd ACM Symposium on Theory of Computing (STOC 2000), pp. 231\u2013236. ACM Press, New York (2000)"},{"key":"55_CR78","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"220","DOI":"10.1007\/3-540-36151-0_21","volume-title":"Graph Drawing","author":"C. Gutwenger","year":"2002","unstructured":"Gutwenger, C., J\u00fcnger, M., Leipert, S., Mutzel, P., Percan, M., Weiskircher, R.: Advances in c-planarity testing of clustered graphs. In: Goodrich, M.T., Kobourov, S.G. (eds.) GD 2002. LNCS, vol.\u00a02528, pp. 220\u2013325. Springer, Heidelberg (2002)"},{"key":"55_CR79","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"13","DOI":"10.1007\/978-3-540-24595-7_2","volume-title":"Graph Drawing","author":"C. Gutwenger","year":"2004","unstructured":"Gutwenger, C., Mutzel, P.: An experimental study of crossing minimization heuristics. In: Liotta, G. (ed.) GD 2003. LNCS, vol.\u00a02912, pp. 13\u201324. Springer, Heidelberg (2004); These proceedings"},{"key":"55_CR80","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"259","DOI":"10.1007\/978-3-540-24595-7_24","volume-title":"Graph Drawing","author":"C. Gutwenger","year":"2004","unstructured":"Gutwenger, C., Mutzel, P.: Graph embedding with minimum depth and maximum external face. In: Liotta, G. (ed.) GD 2003. LNCS, vol.\u00a02912, pp. 259\u2013272. Springer, Heidelberg (2004)"},{"key":"55_CR81","first-page":"246","volume-title":"Proc. Ninth Annual ACM-SIAM Symp. Discrete Algorithms (SODA 2001)","author":"C. Gutwenger","year":"2001","unstructured":"Gutwenger, C., Mutzel, P., Weiskircher, R.: Inserting an edge into a planar graph. In: Proc. Ninth Annual ACM-SIAM Symp. Discrete Algorithms (SODA 2001), Washington, DC, pp. 246\u2013255. ACM Press, New York (2001)"},{"key":"55_CR82","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"205","DOI":"10.1007\/3-540-46648-7_21","volume-title":"Graph Drawing","author":"P. Healy","year":"1999","unstructured":"Healy, P., Kuusik, A.: The vertex-exchange graph: a new concept for multi-level crossing minimization. In: Kratochv\u00edl, J. (ed.) GD 1999. LNCS, vol.\u00a01731, pp. 205\u2013216. Springer, Heidelberg (1999)"},{"key":"55_CR83","doi-asserted-by":"publisher","first-page":"52","DOI":"10.1016\/S0019-9958(85)80044-9","volume":"64","author":"S. Hertel","year":"1985","unstructured":"Hertel, S., Mehlhorn, K.: Fast triangulation of the plane with respect to simple polygons. Inform. Control\u00a064, 52\u201376 (1985)","journal-title":"Inform. Control"},{"issue":"9","key":"55_CR84","doi-asserted-by":"publisher","first-page":"1502","DOI":"10.1109\/5.163414","volume":"80","author":"J.W. Jaromczyk","year":"1992","unstructured":"Jaromczyk, J.W., Toussaint, G.T.: Relative neighborhood graphs and their relatives. Proc. IEEE\u00a080(9), 1502\u20131517 (1992)","journal-title":"Proc. IEEE"},{"key":"55_CR85","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"13","DOI":"10.1007\/3-540-63938-1_46","volume-title":"Graph Drawing","author":"M. J\u00fcnger","year":"1997","unstructured":"J\u00fcnger, M., Lee, E., Mutzel, P., Odenthal, T.: A polyhedral approach to the multi-layer crossing number problem. In: DiBattista, G. (ed.) GD 1997. LNCS, vol.\u00a01353, pp. 13\u201324. Springer, Heidelberg (1997)"},{"key":"55_CR86","unstructured":"Kant, G.: A new method for planar graph drawings on a grid. In: Proc. 33rd Annu. IEEE Sympos. Found. Comput. Sci., pp. 101\u2013110 (1992)"},{"key":"55_CR87","doi-asserted-by":"publisher","first-page":"4","DOI":"10.1007\/BF02086606","volume":"16","author":"G. Kant","year":"1996","unstructured":"Kant, G.: Drawing planar graphs using the canonical ordering. Algorithmica\u00a016, 4\u201332 (1996); (Di Battista, G., Tamassia, R. (ed.) special issue on Graph Drawing)","journal-title":"Algorithmica"},{"issue":"1","key":"55_CR88","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"},{"key":"55_CR89","doi-asserted-by":"crossref","first-page":"13","DOI":"10.1016\/0925-7721(94)90014-0","volume":"4","author":"M. Keil","year":"1994","unstructured":"Keil, M.: Computing a subgraph of the minimum weight triangulation. Comput. Geom. Theory Appl.\u00a04, 13\u201326 (1994)","journal-title":"Comput. Geom. Theory Appl."},{"issue":"3","key":"55_CR90","doi-asserted-by":"publisher","first-page":"127","DOI":"10.1016\/0020-0190(80)90062-9","volume":"10","author":"D.G. Kirkpatrick","year":"1980","unstructured":"Kirkpatrick, D.G.: A note on Delaunay and optimal triangulations. Inform. Process. Lett.\u00a010(3), 127\u2013128 (1980)","journal-title":"Inform. Process. Lett."},{"key":"55_CR91","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"37","DOI":"10.1007\/3-540-44541-2_5","volume-title":"Graph Drawing","author":"G.W. Klau","year":"2001","unstructured":"Klau, G.W., Klein, K., Mutzel, P.: An experimental comparison of orthogonal compaction algorithms. In: Marks, J. (ed.) GD 2000. LNCS, vol.\u00a01984, pp. 37\u201351. Springer, Heidelberg (2001)"},{"key":"55_CR92","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"304","DOI":"10.1007\/3-540-48777-8_23","volume-title":"Integer Programming and Combinatorial Optimization","author":"G.W. Klau","year":"1999","unstructured":"Klau, G.W., Mutzel, P.: Optimal compaction of orthogonal grid drawings. In: Cornu\u00e9jols, G., Burkard, R.E., Woeginger, G.J. (eds.) IPCO 1999. LNCS, vol.\u00a01610, pp. 304\u2013319. Springer, Heidelberg (1999)"},{"key":"55_CR93","doi-asserted-by":"crossref","unstructured":"Leighton, F.T.: New lower bound techniques for VLSI. In: Proc. 22nd Annu. IEEE Sympos. Found. Comput. Sci., pp. 1\u201312 (1981)","DOI":"10.1109\/SFCS.1981.22"},{"issue":"6","key":"55_CR94","doi-asserted-by":"publisher","first-page":"787","DOI":"10.1145\/331524.331526","volume":"46","author":"F.T. Leighton","year":"1999","unstructured":"Leighton, F.T., Rao, S.: Multicommodity max-flow min-cut theorems and their use in designing approximation algorithms. Journal of the ACM\u00a046(6), 787\u2013832 (1999)","journal-title":"Journal of the ACM"},{"issue":"5","key":"55_CR95","doi-asserted-by":"publisher","first-page":"253","DOI":"10.1016\/0020-0190(96)00012-9","volume":"57","author":"W. Lenhart","year":"1996","unstructured":"Lenhart, W., Liotta, G.: Drawing outerplanar minimum weight triangulations. Inform. Process. Lett.\u00a057(5), 253\u2013260 (1996)","journal-title":"Inform. Process. Lett."},{"key":"55_CR96","series-title":"Lecture Notes in Computer Science","volume-title":"Graph Drawing","author":"W. Lenhart","year":"1997","unstructured":"Lenhart, W., Liotta, G.: Proximity drawings of outerplanar graphs. In: North, S.C. (ed.) GD 1996. LNCS, vol.\u00a01190, Springer, Heidelberg (1997)"},{"key":"55_CR97","doi-asserted-by":"publisher","first-page":"261","DOI":"10.1016\/S0304-3975(00)00383-2","volume":"270","author":"W. Lenhart","year":"2002","unstructured":"Lenhart, W., Liotta, G.: The drawability problem for minimum weight triangulations. Theoret. Comp. Sci.\u00a0270, 261\u2013286 (2002)","journal-title":"Theoret. Comp. Sci."},{"key":"55_CR98","doi-asserted-by":"publisher","first-page":"129","DOI":"10.1016\/0020-0190(95)00200-6","volume":"57","author":"C. Levcopoulos","year":"1996","unstructured":"Levcopoulos, C., Krznaric, D.: Tight lower bounds for minimum weight triangulation heuristic. Inform. Process. Lett.\u00a057, 129\u2013135 (1996)","journal-title":"Inform. Process. Lett."},{"key":"55_CR99","doi-asserted-by":"publisher","first-page":"285","DOI":"10.1007\/PL00009216","volume":"21","author":"C. Levcopoulos","year":"1998","unstructured":"Levcopoulos, C., Krznaric, D.: A linear-time approximation schema for minimum weight triangulation of convex polygons. Algorithmica\u00a021, 285\u2013311 (1998)","journal-title":"Algorithmica"},{"issue":"4","key":"55_CR100","doi-asserted-by":"publisher","first-page":"646","DOI":"10.1137\/0608053","volume":"8","author":"A. Lingas","year":"1987","unstructured":"Lingas, A.: A new heuristic for minimum weight triangulation. SIAM J. Algebraic Discrete Methods\u00a08(4), 646\u2013658 (1987)","journal-title":"SIAM J. Algebraic Discrete Methods"},{"key":"55_CR101","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"239","DOI":"10.1007\/3-540-60220-8_66","volume-title":"Algorithms and Data Structures","author":"G. Liotta","year":"1995","unstructured":"Liotta, G., Di Battista, G.: Computing proximity drawings of trees in the 3-dimensional space. In: Sack, J.-R., Akl, S.G., Dehne, F., Santoro, N. (eds.) WADS 1995. LNCS, vol.\u00a0955, pp. 239\u2013250. Springer, Heidelberg (1995)"},{"issue":"1","key":"55_CR102","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/S0925-7721(97)00018-7","volume":"10","author":"G. Liotta","year":"1998","unstructured":"Liotta, G., Lubiw, A., Meijer, H., Whitesides, S.H.: The rectangle of influence drawability problem. Comput. Geom. Theory Appl.\u00a010(1), 1\u201322 (1998)","journal-title":"Comput. Geom. Theory Appl."},{"key":"55_CR103","doi-asserted-by":"crossref","unstructured":"Liotta, G., Meijer, H.: Voronoi drawings of trees. Comput. Geom. Theory Appl. (2003) (to appear)","DOI":"10.1016\/S0925-7721(02)00137-2"},{"key":"55_CR104","doi-asserted-by":"crossref","unstructured":"Lovasz, L., Vesztergombi, K., Wagner, U., Welzl, E.: Convex quadrilaterals and k-sets. Contemporary Mathematics (2003)","DOI":"10.1090\/conm\/342\/06138"},{"key":"55_CR105","unstructured":"Lubiw, A., Sleumer, N.: Maximal outerplanar graphs are relative neighborhood graphs. In: Proc. 5th Canad. Conf. Comput. Geom., pp. 198\u2013203 (1993)"},{"key":"55_CR106","doi-asserted-by":"crossref","unstructured":"Malitz, S., Papakostas, A.: On the angular resolution of planar graphs. In: Proc. 24th Annu. ACM Sympos. Theory Comput., pp. 527\u2013538 (1992)","DOI":"10.1145\/129712.129764"},{"key":"55_CR107","doi-asserted-by":"publisher","first-page":"31","DOI":"10.1016\/0020-0190(79)90104-2","volume":"9","author":"G.K. Manacher","year":"1979","unstructured":"Manacher, G.K., Zobrist, A.L.: Neither the greedy nor the Delaunay triangulation of a planar point set approximates the optimal triangulation. Inform. Process. Lett.\u00a09, 31\u201334 (1979)","journal-title":"Inform. Process. Lett."},{"issue":"9","key":"55_CR108","doi-asserted-by":"publisher","first-page":"9","DOI":"10.1017\/S030500410006028X","volume":"93","author":"A. Mansfield","year":"1983","unstructured":"Mansfield, A.: Determining the thickness of a graph is NP-hard. Math. Proc. Cambridge Philos. Soc.\u00a093(9), 9\u201323 (1983)","journal-title":"Math. Proc. Cambridge Philos. Soc."},{"key":"55_CR109","doi-asserted-by":"crossref","first-page":"85","DOI":"10.1016\/S0925-7721(98)00036-4","volume":"12","author":"K. Mehlhorn","year":"1999","unstructured":"Mehlhorn, K., N\u00e4her, T.S.S., Schirra, S., Seel, M., Seidel, R., Uhrig, C.: Checking geometric programs or verification of geometric structures. Comput. Geom. Theory Appl.\u00a012, 85\u2013113 (1999)","journal-title":"Comput. Geom. Theory Appl."},{"key":"55_CR110","doi-asserted-by":"publisher","first-page":"265","DOI":"10.1007\/BF02293049","volume":"8","author":"C. Monma","year":"1992","unstructured":"Monma, C., Suri, S.: Transitions in geometric minimum spanning trees. Discrete Comput. Geom.\u00a08, 265\u2013293 (1992)","journal-title":"Discrete Comput. Geom."},{"key":"55_CR111","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"95","DOI":"10.1007\/3-540-44968-X_10","volume-title":"Computing and Combinatorics","author":"P. Mutzel","year":"2000","unstructured":"Mutzel, P., Weiskircher, R.: Computing optimal embeddings for planar graphs. In: Du, D.-Z., Eades, P., Sharma, A.K., Lin, X., Estivill-Castro, V. (eds.) COCOON 2000. LNCS, vol.\u00a01858, pp. 95\u2013104. Springer, Heidelberg (2000)"},{"key":"55_CR112","doi-asserted-by":"publisher","first-page":"111","DOI":"10.1007\/BF02086610","volume":"16","author":"J. Pach","year":"1996","unstructured":"Pach, J., Shahrokhi, F., Szegedy, M.: Applications of the crossing number. Algorithmica\u00a016, 111\u2013117 (1996) (Di Battista, G., Tamassia, R.(ed.) special issue on Graph Drawing)","journal-title":"Algorithmica"},{"key":"55_CR113","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"47","DOI":"10.1007\/3-540-63938-1_49","volume-title":"Graph Drawing","author":"J. Pach","year":"1997","unstructured":"Pach, J., Thiele, T., T\u00f3th, G.: Three-dimensional grid drawings of graphs. In: DiBattista, G. (ed.) GD 1997. LNCS, vol.\u00a01353, pp. 47\u201351. Springer, Heidelberg (1997)"},{"key":"55_CR114","doi-asserted-by":"publisher","first-page":"427","DOI":"10.1007\/BF01215922","volume":"17","author":"J. Pach","year":"1997","unstructured":"Pach, J., T\u00f3th, G.: Graphs drawn with few crossings per edge. Combinatorica\u00a017, 427\u2013439 (1997)","journal-title":"Combinatorica"},{"key":"55_CR115","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"356","DOI":"10.1007\/3-540-45253-2_33","volume-title":"Algorithms - ESA 2000","author":"M. Pizzonia","year":"2000","unstructured":"Pizzonia, M., Tamassia, R.: Minimum depth graph embedding. In: Paterson, M. (ed.) ESA 2000. LNCS, vol.\u00a01879, pp. 356\u2013367. Springer, Heidelberg (2000)"},{"key":"55_CR116","volume-title":"Computational Geometry: An Introduction","author":"F.P. Preparata","year":"1990","unstructured":"Preparata, F.P., Shamos, M.I.: Computational Geometry: An Introduction, 3rd edn. Springer, Heidelberg (October 1990)","edition":"3"},{"key":"55_CR117","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"387","DOI":"10.1007\/978-3-540-24595-7_36","volume-title":"Graph Drawing","author":"S. Rahman","year":"2004","unstructured":"Rahman, S., Egi, N., Nishizeki, T.: No-bend orthogonal drawings of subdivisions of planar triconnected cubic graphs. In: Liotta, G. (ed.) GD 2003. LNCS, vol.\u00a02912, pp. 387\u2013392. Springer, Heidelberg (2004)"},{"key":"55_CR118","doi-asserted-by":"publisher","first-page":"35","DOI":"10.1016\/0020-0190(92)90129-J","volume":"42","author":"D. Rappaport","year":"1992","unstructured":"Rappaport, D., Meijer, H.: Computing the minimum weight triangulation of a set of linearly ordered points. Information Processing Letters\u00a042, 35\u201338 (1992)","journal-title":"Information Processing Letters"},{"key":"55_CR119","doi-asserted-by":"crossref","unstructured":"Richter, R., Thomassen, C.: Relations between crossing numbers of complete and complete bipartite graphs (February 1997)","DOI":"10.2307\/2974980"},{"issue":"4","key":"55_CR120","doi-asserted-by":"publisher","first-page":"343","DOI":"10.1007\/BF02187706","volume":"1","author":"P. Rosenstiehl","year":"1986","unstructured":"Rosenstiehl, P., Tarjan, R.E.: Rectilinear planar layouts and bipolar orientations of planar graphs. Discrete Comput. Geom.\u00a01(4), 343\u2013353 (1986)","journal-title":"Discrete Comput. Geom."},{"issue":"10","key":"55_CR121","doi-asserted-by":"publisher","first-page":"939","DOI":"10.2307\/2975158","volume":"101","author":"E.R. Scheinerman","year":"1994","unstructured":"Scheinerman, E.R., Wilf, H.S.: The rectilinear crossing number of a complete graph and Sylvester\u2019s \u201cfour point problem\u201d of geometric probability. Amer. Math. Monthly\u00a0101(10), 939\u2013943 (1994)","journal-title":"Amer. Math. Monthly"},{"key":"55_CR122","doi-asserted-by":"publisher","first-page":"323","DOI":"10.1007\/BF00353652","volume":"5","author":"W. Schnyder","year":"1989","unstructured":"Schnyder, W.: Planar graphs and poset dimension. Order\u00a05, 323\u2013343 (1989)","journal-title":"Order"},{"key":"55_CR123","unstructured":"Schnyder, W.: Embedding planar graphs on the grid. In: Proc. 1st ACM-SIAM Sympos. Discrete Algorithms, pp. 138\u2013148 (1990)"},{"issue":"5","key":"55_CR124","first-page":"502","volume":"13","author":"W. Schnyder","year":"1992","unstructured":"Schnyder, W., Trotter, W.T.: Convex embeddings of 3-connected plane graphs. Abstracts of the AMS\u00a013(5), 502 (1992)","journal-title":"Abstracts of the AMS"},{"key":"55_CR125","doi-asserted-by":"crossref","first-page":"175","DOI":"10.1016\/S0925-7721(99)00053-X","volume":"15","author":"C.-S. Shin","year":"2000","unstructured":"Shin, C.-S., Kim, S.K., Chwa, K.-Y.: Area-efficient algorithms for straight-line tree drawings. Comput. Geom. Theory Appl.\u00a015, 175\u2013202 (2000)","journal-title":"Comput. Geom. Theory Appl."},{"issue":"2","key":"55_CR126","doi-asserted-by":"publisher","first-page":"109","DOI":"10.1109\/TSMC.1981.4308636","volume":"SMC-11","author":"K. Sugiyama","year":"1981","unstructured":"Sugiyama, K., Tagawa, S., Toda, M.: Methods for visual understanding of hierarchical systems. IEEE Trans. Syst. Man Cybern.\u00a0SMC-11(2), 109\u2013125 (1981)","journal-title":"IEEE Trans. Syst. Man Cybern."},{"key":"55_CR127","doi-asserted-by":"publisher","first-page":"83","DOI":"10.1016\/0167-9260(94)90021-3","volume":"17","author":"O. S\u00fdkora","year":"1994","unstructured":"S\u00fdkora, O., Vr\u0165o, I.: On VLSI layouts of the star graph and related networks. The VLSI Journal\u00a017, 83\u201393 (1994)","journal-title":"The VLSI Journal"},{"issue":"3","key":"55_CR128","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":"55_CR129","doi-asserted-by":"publisher","first-page":"280","DOI":"10.1007\/BF01905693","volume":"7","author":"G. Toussaint","year":"1991","unstructured":"Toussaint, G.: Efficient triangulation of simple polygons. Visual Comput.\u00a07, 280\u2013295 (1991)","journal-title":"Visual Comput."},{"key":"55_CR130","doi-asserted-by":"publisher","first-page":"355","DOI":"10.1137\/0214027","volume":"14","author":"G. Vijayan","year":"1985","unstructured":"Vijayan, G., Wigderson, A.: Rectilinear graphs and their embeddings. SIAM J. Comput.\u00a014, 355\u2013372 (1985)","journal-title":"SIAM J. Comput."},{"key":"55_CR131","doi-asserted-by":"crossref","unstructured":"Vijayan, V.: Geometry of planar graphs with angles. In: Proc. 2nd Annu. ACM Sympos. Comput. Geom., pp. 116\u2013124 (1986)","DOI":"10.1145\/10515.10528"},{"key":"55_CR132","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"59","DOI":"10.1007\/3-540-46648-7_6","volume-title":"Graph Drawing","author":"V. Waddle","year":"1999","unstructured":"Waddle, V., Malhotra, A.: An E log E line crossing algorithm for levelled graphs. In: Kratochv\u00edl, J. (ed.) GD 1999. LNCS, vol.\u00a01731, pp. 59\u201370. Springer, Heidelberg (1999)"},{"key":"55_CR133","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"163","DOI":"10.1007\/3-540-46521-9_14","volume-title":"Algorithms and Complexity","author":"C.A. Wang","year":"2000","unstructured":"Wang, C.A., Chin, F.Y., Yang, B.: Triangulations without minimum weight drawing. In: Bongiovanni, G., Petreschi, R., Gambosi, G. (eds.) CIAC 2000. LNCS, vol.\u00a01767, pp. 163\u2013173. Springer, Heidelberg (2000)"},{"issue":"1","key":"55_CR134","first-page":"60","volume":"4","author":"T.C. Woo","year":"1985","unstructured":"Woo, T.C., Shin, S.Y.: A linear time algorithm for triangulating a point-visible polygon. ACM Trans. Graph.\u00a04(1), 60\u201370 (1985)","journal-title":"ACM Trans. Graph."},{"key":"55_CR135","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"348","DOI":"10.1007\/3-540-36206-1_31","volume-title":"FST TCS 2002: Foundations of Software Technology and Theoretical Computer Science","author":"D.R. Wood","year":"2002","unstructured":"Wood, D.R.: Queue layouts, tree-width, and three-dimensional graph drawing. In: Agrawal, M., Seth, A.K. (eds.) FSTTCS 2002. LNCS, vol.\u00a02556, pp. 348\u2013359. Springer, Heidelberg (2002)"},{"key":"55_CR136","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"493","DOI":"10.1007\/978-3-540-45078-8_43","volume-title":"Algorithms and Data Structures","author":"H. Zhang","year":"2003","unstructured":"Zhang, H., He, X.: Compact visibility representations and straight-line grid embedding of plane graphs. In: Dehne, F., Sack, J.-R., Smid, M. (eds.) WADS 2003. LNCS, vol.\u00a02748, pp. 493\u2013504. Springer, Heidelberg (2003)"}],"container-title":["Lecture Notes in Computer Science","Graph Drawing"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-24595-7_55","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,31]],"date-time":"2019-05-31T23:53:10Z","timestamp":1559346790000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-24595-7_55"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2004]]},"ISBN":["9783540208310","9783540245957"],"references-count":136,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-24595-7_55","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2004]]}}}