{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T18:40:23Z","timestamp":1787337623115,"version":"build-2736575974"},"reference-count":35,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"2","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Comput."],"published-print":{"date-parts":[[2001,1]]},"abstract":"<jats:p>A directed graph is upward planar if it can be drawn in the plane such that every edge is a monotonically increasing curve in the vertical direction and no two edges cross. An undirected graph is rectilinear planar if it can be drawn in the plane such that every edge is a horizontal or vertical segment and no two edges cross. Testing upward planarity and rectilinear planarity are fundamental problems in the effective visualization of various graph and network structures. For example, upward planarity is useful for the display of order diagrams and subroutine-call graphs, while rectilinear planarity is useful for the display of circuit schematics and entity-relationship diagrams.<\/jats:p>\n                  <jats:p>We show that upward planarity testing and rectilinear planarity testing are NP-complete problems. We also show that it is NP-hard to approximate the minimum number of bends in a planar orthogonal drawing of an n-vertex graph with an $O(n^{1-\\epsilon})$ error for any $\\epsilon &gt; 0$.<\/jats:p>","DOI":"10.1137\/s0097539794277123","type":"journal-article","created":{"date-parts":[[2003,6,11]],"date-time":"2003-06-11T11:12:06Z","timestamp":1055329926000},"page":"601-625","source":"Crossref","is-referenced-by-count":184,"title":["On the Computational Complexity of Upward and Rectilinear Planarity Testing"],"prefix":"10.1137","volume":"31","author":[{"given":"Ashim","family":"Garg","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Roberto","family":"Tamassia","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2006,7,27]]},"reference":[{"key":"R1","doi-asserted-by":"publisher","DOI":"10.1142\/S0218195994000215"},{"key":"R2","doi-asserted-by":"crossref","unstructured":"P. Bertolazzi and G. Di Battista,\n                      On upward drawing testing of triconnected digraphs\n                      , in\n                      Proceedings of the 7th Annual Symposium on Computational Geometry\n                      , North Conway, NH, 1991, pp. 272\u2013280.","DOI":"10.1145\/109648.109679"},{"key":"R3","doi-asserted-by":"publisher","DOI":"10.1007\/BF01188716"},{"key":"R4","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539794279626"},{"key":"R5","doi-asserted-by":"publisher","DOI":"10.1016\/S0925-7721(97)00026-6"},{"key":"R6","doi-asserted-by":"publisher","DOI":"10.1016\/0925-7721(94)00014-X"},{"key":"R7","unstructured":"G. Di Battista, P. Eades, R. Tamassia, and I. G. Tollis,\n                      Graph Drawing\n                      , Prentice Hall, Upper Saddle River, NJ, 1999."},{"key":"R8","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539794262847"},{"key":"R9","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(90)90045-Y"},{"key":"R10","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(88)90123-5"},{"key":"R11","doi-asserted-by":"publisher","DOI":"10.1007\/BF02187850"},{"key":"R12","unstructured":"S. Even and G. Granot,\n                      Rectilinear Planar Drawings with Few Bends in Each Edge\n                      , Technical report 797, Computer Science Department, Technion, Haifa, Israel, 1994."},{"key":"R13","volume-title":"Computers and intractability","author":"Garey Michael","year":"1979"},{"key":"R14","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539792235906"},{"key":"R15","doi-asserted-by":"publisher","DOI":"10.1007\/s004539900035"},{"key":"R16","doi-asserted-by":"publisher","DOI":"10.1016\/0012-365X(87)90008-2"},{"key":"R17","doi-asserted-by":"publisher","DOI":"10.4153\/CJM-1975-074-0"},{"key":"R18","unstructured":"A. Lempel, S. Even, and I. Cederbaum,\n                      An algorithm for planarity testing of graphs\n                      , in Theory of Graphs, Gordon and Breach, New York, 1967, pp. 215\u2013232."},{"key":"R19","doi-asserted-by":"publisher","DOI":"10.1007\/BF02662066"},{"key":"R20","doi-asserted-by":"publisher","DOI":"10.1007\/BF02006154"},{"key":"R21","doi-asserted-by":"publisher","DOI":"10.1007\/BF02006104"},{"key":"R22","unstructured":"Y. Liu, A. Morgana, and B. Simeone,\n                      A Linear Algorithm for 3\u2010Bend Embeddings of Planar Graphs in the Grid\n                      , manuscript, 1993."},{"key":"R23","doi-asserted-by":"crossref","unstructured":"Achilleas Papakostas, Upward planarity testing of outerplanar dags (extended abstract), Lecture Notes in Comput. Sci., Vol. 894, Springer, Berlin, 1995, 298\u20133061337518","DOI":"10.1007\/3-540-58950-3_385"},{"key":"R24","doi-asserted-by":"publisher","DOI":"10.1016\/0095-8956(76)90024-1"},{"key":"R25","doi-asserted-by":"crossref","unstructured":"I. Rival,\n                      The diagram\n                      , in Graphs and Order, I. Rival, ed., Reidel, Dordrecht, the Netherlands, 1985, pp. 103\u2013133.","DOI":"10.1007\/978-94-009-5315-4_3"},{"key":"R26","doi-asserted-by":"crossref","unstructured":"Ivan Rival, Graphical data structures for ordered sets, Kluwer Acad. Publ., Dordrecht, 1989, 3\u20133191k:06007","DOI":"10.1007\/978-94-009-2639-4_1"},{"key":"R27","doi-asserted-by":"crossref","unstructured":"Ivan Rival, Reading, drawing, and order, NATO Adv. Sci. Inst. Ser. C Math. Phys. Sci., Vol. 389, Kluwer Acad. Publ., Dordrecht, 1993, 359\u201340494d:06003","DOI":"10.1007\/978-94-017-0697-1_9"},{"key":"R28","unstructured":"Y. Shiloach,\n                      Arrangements of Planar Graphs on the Planar Lattice\n                      , Ph.D. thesis, Weizmann Institute of Science, Rehovot, Israel, 1976."},{"key":"R29","doi-asserted-by":"publisher","DOI":"10.1002\/net.3230140202"},{"key":"R30","doi-asserted-by":"publisher","DOI":"10.1137\/0216030"},{"key":"R31","doi-asserted-by":"publisher","DOI":"10.1109\/31.34669"},{"key":"R32","doi-asserted-by":"publisher","DOI":"10.1137\/0220045"},{"key":"R33","doi-asserted-by":"publisher","DOI":"10.1007\/BF00353654"},{"key":"R34","doi-asserted-by":"publisher","DOI":"10.1109\/TC.1981.6312176"},{"key":"R35","doi-asserted-by":"publisher","DOI":"10.1137\/0214027"}],"container-title":["SIAM Journal on Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/S0097539794277123","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T18:21:37Z","timestamp":1787336497000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/S0097539794277123"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2001,1]]},"references-count":35,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2001,1]]}},"alternative-id":["10.1137\/S0097539794277123"],"URL":"https:\/\/doi.org\/10.1137\/s0097539794277123","relation":{},"ISSN":["0097-5397","1095-7111"],"issn-type":[{"value":"0097-5397","type":"print"},{"value":"1095-7111","type":"electronic"}],"subject":[],"published":{"date-parts":[[2001,1]]}}}