{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T18:38:27Z","timestamp":1787337507867,"version":"build-2736575974"},"reference-count":34,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"1","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Comput."],"published-print":{"date-parts":[[1998,1]]},"abstract":"<jats:p>\n                    A digraph is upward planar if it has a planar drawing such that all the edges are monotone with respect to the vertical direction. Testing upward planarity and constructing upward planar drawings is important for displaying hierarchical network structures, which frequently arise in software engineering, project management, and visual languages. In this paper we investigate upward planarity testing of single-source digraphs; we provide a new combinatorial characterization of upward planarity and give an optimal algorithm for upward planarity testing. Our algorithm tests whether a single-source digraph with n vertices is upward planar in O(n) sequential time, and in O(log n) time on a CRCW PRAM with $n \\log \\log n\/\\log n$ processors, using O(n,) space. The algorithm also constructs an upward planar drawing if the test is successful. The previously known best result is an O(n\n                    <jats:sup>2<\/jats:sup>\n                    )-time algorithm by Hutton and Lubiw [Proc. 2nd ACM--SIAM Symposium on Discrete Algorithms, SIAM, Philadelphia, 1991, pp. 203--211]. No efficient parallel algorithms for upward planarity testing were previously known.\n                  <\/jats:p>","DOI":"10.1137\/s0097539794279626","type":"journal-article","created":{"date-parts":[[2003,6,11]],"date-time":"2003-06-11T11:12:06Z","timestamp":1055329926000},"page":"132-169","source":"Crossref","is-referenced-by-count":76,"title":["Optimal Upward Planarity Testing of Single-Source Digraphs"],"prefix":"10.1137","volume":"27","author":[{"given":"Paola","family":"Bertolazzi","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Giuseppe","family":"Di Battista","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Carlo","family":"Mannino","sequence":"additional","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,28]]},"reference":[{"key":"R1","doi-asserted-by":"crossref","unstructured":"P. Bertolazzi, R. F. Cohen, G. Di Battista, R. Tamassia, and I. G. Tollis,\n                      How to draw a series\u2010parallel digraph\n                      , in Proc. 3rd Scand. Workshop Algorithm Theory, Lecture Notes in Comput. Sci. 621, Springer\u2010Verlag, Berlin, 1992, pp. 272\u2013283.","DOI":"10.1007\/3-540-55706-7_23"},{"key":"R2","doi-asserted-by":"publisher","DOI":"10.1142\/S0218195994000215"},{"key":"R3","doi-asserted-by":"crossref","unstructured":"P. Bertolazzi and G. Di Battista,\n                      On upward drawing testing of triconnected digraphs\n                      , in Proc. 7th Annual ACM Sympos. Comput. Geom., 1991, ACM, New York, pp. 272\u2013280.","DOI":"10.1145\/109648.109679"},{"key":"R4","doi-asserted-by":"publisher","DOI":"10.1007\/BF01188716"},{"key":"R5","doi-asserted-by":"crossref","unstructured":"R. Cole and U. Vishkin,\n                      Approximate and exact parallel scheduling with applications to list, tree, and graph problems\n                      , in Proc. 27th IEEE Symp. on Foundations of Computer Science, IEEE Computer Society Press, Los Alamitos, CA, 1986, pp. 478\u2013491.","DOI":"10.1109\/SFCS.1986.10"},{"key":"R6","doi-asserted-by":"publisher","DOI":"10.1016\/0925-7721(92)90021-J"},{"key":"R7","doi-asserted-by":"publisher","DOI":"10.1016\/0925-7721(94)00014-X"},{"key":"R8","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(90)90045-Y"},{"key":"R9","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(88)90123-5"},{"key":"R10","doi-asserted-by":"crossref","unstructured":"G. Di Battista and R. Tamassia,\n                      On\u2010line graph algorithms with spqr\u2010trees\n                      , in Automata, Languages and Programming (Proc. 17th ICALP), Lecture Notes in Comput. Sci. 442, Springer\u2010Verlag, New York, 1990, pp. 598\u2013611.","DOI":"10.1007\/BFb0032061"},{"key":"R11","doi-asserted-by":"publisher","DOI":"10.1007\/s004539900017"},{"key":"R12","doi-asserted-by":"publisher","DOI":"10.1007\/BF02187850"},{"key":"R13","unstructured":"P. Eades, T. Lin, and X. Lin,\n                      Minimum size h\u2010v drawings\n                      , in Advanced Visual Interfaces (Proc. AVI \u201992), World Scientific Series in Computer Science 36, World Scientific, River Edge, NJ, 1992, pp. 386\u2013394."},{"key":"R14","doi-asserted-by":"crossref","unstructured":"Donald Fussell, Vijaya Ramachandran, Ramakrishna Thurimella, Finding triconnected components by local replacements (extended abstract), Lecture Notes in Comput. Sci., Vol. 372, Springer, Berlin, 1989, 379\u20133931037063","DOI":"10.1007\/BFb0035771"},{"key":"R15","doi-asserted-by":"crossref","unstructured":"A. Garg, M. T. Goodrich, and R. Tamassia,\n                      Area\u2010efficient upward tree drawings\n                      , in Proc. 9th Annual ACM Sympos. Comput. Geom., ACM, New York, 1993, pp. 359\u2013368.","DOI":"10.1145\/160985.161165"},{"key":"R16","doi-asserted-by":"crossref","unstructured":"Ashim Garg, Roberto Tamassia, On the computational complexity of upward and rectilinear planarity testing (extended abstract), Lecture Notes in Comput. Sci., Vol. 894, Springer, Berlin, 1995, 286\u20132971337517","DOI":"10.1007\/3-540-58950-3_384"},{"key":"R17","doi-asserted-by":"publisher","DOI":"10.1137\/0202012"},{"key":"R18","doi-asserted-by":"publisher","DOI":"10.1145\/321850.321852"},{"key":"R19","unstructured":"Michael Hutton, Anna Lubiw, Upward planar drawing of single source acyclic digraphs, ACM, New York, 1991, 203\u20132111095835"},{"key":"R20","doi-asserted-by":"crossref","unstructured":"M.\u2010Y. Kao and G. E. Shannon,\n                      Local reorientations, global order, and planar topology\n                      , in Proc. 30th IEEE Symp. on Foundations of Computer Science, IEEE Computer Society Press, Los Alamitos, CA, 1989, pp. 286\u2013296.","DOI":"10.1145\/73007.73034"},{"key":"R21","doi-asserted-by":"publisher","DOI":"10.1016\/0012-365X(87)90008-2"},{"key":"R22","doi-asserted-by":"publisher","DOI":"10.4153\/CJM-1975-074-0"},{"key":"R23","unstructured":"A. Lempel, S. Even, and I. Cederbaum,\n                      An algorithm for planarity testing of graphs\n                      , in Theory of Graphs: Internat. Symposium, Rome, 1966, Gordon and Breach, New York, 1967, pp. 215\u2013232."},{"key":"R24","unstructured":"L. Lovasz and M. D. Pummer,\n                      Matching Theory\n                      , Ann. Discrete Math. 29, North\u2013Holland, Amsterdam, 1986."},{"key":"R25","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":"R26","doi-asserted-by":"publisher","DOI":"10.1016\/0095-8956(76)90024-1"},{"key":"R27","doi-asserted-by":"publisher","DOI":"10.1016\/S0022-0000(05)80070-4"},{"key":"R28","doi-asserted-by":"crossref","unstructured":"V. Ramachandran and J. H. Reif,\n                      An optimal parallel algorithm for graph planarity\n                      , in Proc. 30th Annual IEEE Sympos. Found. Comput. Sci., IEEE Computer Society Press, Los Alamitos, CA, 1989, pp. 282\u2013293.","DOI":"10.1109\/SFCS.1989.63491"},{"key":"R29","doi-asserted-by":"publisher","DOI":"10.1109\/TSE.1981.234519"},{"key":"R30","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":"R31","doi-asserted-by":"publisher","DOI":"10.1007\/BF00289576"},{"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.1016\/0095-8956(77)90048-X"}],"container-title":["SIAM Journal on Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/S0097539794279626","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T18:14:34Z","timestamp":1787336074000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/S0097539794279626"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1998,1]]},"references-count":34,"journal-issue":{"issue":"1","published-print":{"date-parts":[[1998,1]]}},"alternative-id":["10.1137\/S0097539794279626"],"URL":"https:\/\/doi.org\/10.1137\/s0097539794279626","relation":{},"ISSN":["0097-5397","1095-7111"],"issn-type":[{"value":"0097-5397","type":"print"},{"value":"1095-7111","type":"electronic"}],"subject":[],"published":{"date-parts":[[1998,1]]}}}