{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,16]],"date-time":"2024-09-16T17:15:12Z","timestamp":1726506912818},"publisher-location":"Berlin, Heidelberg","reference-count":30,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540589501"},{"type":"electronic","value":"9783540491552"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1995]]},"DOI":"10.1007\/3-540-58950-3_384","type":"book-chapter","created":{"date-parts":[[2012,2,26]],"date-time":"2012-02-26T16:54:53Z","timestamp":1330275293000},"page":"286-297","source":"Crossref","is-referenced-by-count":49,"title":["On the computational complexity of upward and rectilinear planarity testing"],"prefix":"10.1007","author":[{"given":"Ashim","family":"Garg","sequence":"first","affiliation":[]},{"given":"Roberto","family":"Tamassia","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2005,6,1]]},"reference":[{"key":"34_CR1","doi-asserted-by":"crossref","unstructured":"P. Bertolazzi and G. Di Battista. On upward drawing testing of triconnected digraphs. In Proc. 7th Annu. ACM Sympos. Comput. Geom., pp. 272\u2013280, 1991.","DOI":"10.1145\/109648.109679"},{"key":"34_CR2","doi-asserted-by":"crossref","unstructured":"P. Bertolazzi, G. Di Battista, G. Liotta, and C. Mannino. Upward drawings of triconnected digraphs. Algorithmica, to appear.","DOI":"10.1007\/BF01188716"},{"key":"34_CR3","first-page":"37","volume":"726","author":"P. Bertolazzi","year":"1993","unstructured":"P. Bertolazzi, G. Di Battista, C. Mannino, and R. Tamassia. Optimal upward planarity testing of single-source digraphs. In Proc. European Symposium on Algorithms, LNCS vol. 726, pp. 37\u201348. Springer-Verlag, 1993.","journal-title":"Proc. European Symposium on Algorithms, LNCS"},{"key":"34_CR4","first-page":"24","volume":"855","author":"T. Biedl","year":"1994","unstructured":"T. Biedl and G. Kant. A better heuristic for orthogonal graph drawings. In Proc. European Symp. on Algorithms, LNCS vol. 855, pp. 24\u201335. Springer-Verlag, 1994.","journal-title":"Proc. European Symp. on Algorithms, LNCS"},{"key":"34_CR5","unstructured":"G. Di Battista, P. Eades, R. Tamassia, and I. G. Tollis. Algorithms for drawing graphs: an annotated bibliography. Comput. Geom. Theory Appl., to appear. Preprint available by ftp from ftp.cs.brown.edu:pub\/papers\/compgeo\/."},{"key":"34_CR6","doi-asserted-by":"crossref","first-page":"151","DOI":"10.1007\/3-540-57155-8_244","volume":"709","author":"G. Battista Di","year":"1993","unstructured":"G. Di Battista, G. Liotta, and F. Vargiu. Spirality of orthogonal representations and optimal drawings of series-parallel graphs and 3-planar graphs. In Proc. Workshop Algorithms Data Struct, LNCS vol. 709, pp. 151\u2013162. Springer-Verlag, 1993.","journal-title":"Proc. Workshop Algorithms Data Struct, LNCS"},{"key":"34_CR7","doi-asserted-by":"crossref","first-page":"317","DOI":"10.1016\/0020-0190(90)90045-Y","volume":"36","author":"G. Battista Di","year":"1990","unstructured":"G. Di Battista, W. P. Liu, and I. Rival. Bipartite graphs upward drawings and planarity. Inform. Process. Lett., 36:317\u2013322, 1990.","journal-title":"Inform. Process. Lett."},{"key":"34_CR8","doi-asserted-by":"crossref","first-page":"175","DOI":"10.1016\/0304-3975(88)90123-5","volume":"61","author":"G. Battista Di","year":"1988","unstructured":"G. Di Battista and R. Tamassia. Algorithms for plane representations of acyclic digraphs. Theoret. Comput. Sci., 61:175\u2013198, 1988.","journal-title":"Theoret. Comput. Sci."},{"key":"34_CR9","unstructured":"S. Even and G. Granot. Rectilinear planar drawings with few bends in each edge. Technical Report 797, Computer Science Dept., Technion\u201d, 1994."},{"key":"34_CR10","volume-title":"Computers and Intractability: A Guide to the Theory of NP-Completeness","author":"M. R. Garey","year":"1979","unstructured":"M. R. Garey and D. S. Johnson. Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman, New York, NY, 1979."},{"key":"34_CR11","volume-title":"Report CS-94-10","author":"A. Garg","year":"1994","unstructured":"A. Garg and R. Tamassia. On the computational complexity of upward and rectilinear planarity testing. Report CS-94-10, Comput. Sci. Dept., Brown Univ., Providence, RI, 1994."},{"key":"34_CR12","unstructured":"M. D. Hutton and A. Lubiw. Upward planar drawing of single source acyclic digraphs. In Proc. 2nd ACM-SIAM Sympos. Discrete Algorithms, pp. 203\u2013211, 1991."},{"key":"34_CR13","doi-asserted-by":"crossref","unstructured":"G. Kant. Drawing planar graphs using the lmc-ordering. In Proc. 33th Annu. IEEE Sympos. Found. Comput. Sci., pp. 101\u2013110, 1992.","DOI":"10.1109\/SFCS.1992.267814"},{"key":"34_CR14","doi-asserted-by":"crossref","first-page":"197","DOI":"10.1016\/0012-365X(87)90008-2","volume":"63","author":"D. Kelly","year":"1987","unstructured":"D. Kelly. Fundamentals of planar ordered sets. Discrete Math., 63:197\u2013216, 1987.","journal-title":"Discrete Math."},{"issue":"3","key":"34_CR15","doi-asserted-by":"crossref","first-page":"636","DOI":"10.4153\/CJM-1975-074-0","volume":"27","author":"D. Kelly","year":"1975","unstructured":"D. Kelly and I. Rival. Planar lattices. Canad. J. Math., 27(3):636\u2013665, 1975.","journal-title":"Canad. J. Math."},{"key":"34_CR16","first-page":"215","volume-title":"Theory of Graphs: Internat. Symposium (Rome 1966)","author":"A. Lempel","year":"1967","unstructured":"A. Lempel, S. Even, and I. Cederbaum. An algorithm for planarity testing of graphs. In Theory of Graphs: Internat. Symposium (Rome 1966), pp. 215\u2013232, New York, 1967. Gordon and Breach."},{"key":"34_CR17","unstructured":"Y. Liu, P. Marchioro, and R. Petreschi. A single bend embedding algorithm for cubic graphs. Manuscript, 1994."},{"key":"34_CR18","unstructured":"Y. Liu, P. Marchioro, R. Petreschi, and B. Simeone. Theoretical results on at most 1-bend embeddability of graphs. Technical report, Dipartimento di Statistica, Univ. di Roma \u201cLa Sapienza\u201d, 1990."},{"key":"34_CR19","doi-asserted-by":"crossref","first-page":"187","DOI":"10.1007\/BF02006104","volume":"7","author":"Y. Liu","year":"1991","unstructured":"Y. Liu, A. Morgana, and B. Simeone. General theoretical results on rectilinear embeddability of graphs. Acta Math. Appl. Sinica, 7:187\u2013192, 1991.","journal-title":"Acta Math. Appl. Sinica"},{"key":"34_CR20","unstructured":"Y. Liu, A. Morgana, and B. Simeone. A linear algorithm for 3-bend embeddings of planar graphs in the grid. Manuscript, 1993."},{"key":"34_CR21","doi-asserted-by":"crossref","unstructured":"A. Papakostas. Upward planarity testing of outerplanar dags. In Proc. Graph Drawing '94, 1994.","DOI":"10.1007\/3-540-58950-3_385"},{"key":"34_CR22","doi-asserted-by":"crossref","first-page":"30","DOI":"10.1016\/0095-8956(76)90024-1","volume":"21","author":"C. Platt","year":"1976","unstructured":"C. Platt. Planar lattices and planar graphs. J. Combin. Theory Ser. B, 21:30\u201339, 1976.","journal-title":"J. Combin. Theory Ser. B"},{"key":"34_CR23","doi-asserted-by":"crossref","unstructured":"I. Rival. Reading, drawing, and order. In I. G. Rosenberg and G. Sabidussi, editors, Algebras and Orders, pp. 359\u2013404. Kluwer Academic Publishers, 1993.","DOI":"10.1007\/978-94-017-0697-1_9"},{"key":"34_CR24","unstructured":"Y. Shiloach. Arrangements of Planar Graphs on the Planar Lattice. PhD thesis, Weizmann Institute of Science, 1976."},{"key":"34_CR25","doi-asserted-by":"crossref","first-page":"181","DOI":"10.1002\/net.3230140202","volume":"14","author":"J. A. Storer","year":"1984","unstructured":"J. A. Storer. On minimal node-cost planar embeddings. Networks, 14:181\u2013212, 1984.","journal-title":"Networks"},{"issue":"3","key":"34_CR26","doi-asserted-by":"crossref","first-page":"421","DOI":"10.1137\/0216030","volume":"16","author":"R. Tamassia","year":"1987","unstructured":"R. Tamassia. 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":"9","key":"34_CR27","doi-asserted-by":"crossref","first-page":"1230","DOI":"10.1109\/31.34669","volume":"CAS-36","author":"R. Tamassia","year":"1989","unstructured":"R. Tamassia and I. G. Tollis. Planar grid embedding in linear time. IEEE Trans. on Circuits and Systems, CAS-36(9):1230\u20131234, 1989.","journal-title":"IEEE Trans. on Circuits and Systems"},{"issue":"4","key":"34_CR28","doi-asserted-by":"crossref","first-page":"349","DOI":"10.1007\/BF00353654","volume":"5","author":"C. Thomassen","year":"1989","unstructured":"C. Thomassen. Planar acyclic oriented graphs. Order, 5(4):349\u2013361, 1989.","journal-title":"Order"},{"issue":"2","key":"34_CR29","doi-asserted-by":"crossref","first-page":"135","DOI":"10.1109\/TC.1981.6312176","volume":"C-30","author":"L. Valiant","year":"1981","unstructured":"L. Valiant. Universality considerations in VLSI circuits. IEEE Trans. Comput., C-30(2):135\u2013140, 1981.","journal-title":"IEEE Trans. Comput."},{"key":"34_CR30","doi-asserted-by":"crossref","first-page":"355","DOI":"10.1137\/0214027","volume":"14","author":"G. Vijayan","year":"1985","unstructured":"G. Vijayan and A. Wigderson. Rectilinear graphs and their embeddings. SIAM J. Comput., 14:355\u2013372, 1985.","journal-title":"SIAM J. Comput."}],"container-title":["Lecture Notes in Computer Science","Graph Drawing"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-58950-3_384.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,11,17]],"date-time":"2020-11-17T21:24:52Z","timestamp":1605648292000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-58950-3_384"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1995]]},"ISBN":["9783540589501","9783540491552"],"references-count":30,"URL":"https:\/\/doi.org\/10.1007\/3-540-58950-3_384","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1995]]}}}