{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T19:35:22Z","timestamp":1787340922603,"version":"build-2736575974"},"reference-count":27,"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":[[1996,4]]},"abstract":"<jats:p>An upward plane drawing of a directed acyclic graph is a plane drawing of the digraph in which each directed edge is represented as a curve monotone increasing in the vertical direction. Thomassen has given a nonalgorithmic, graph-theoretic characterization of those directed graphs with a single source that admit an upward plane drawing. This paper presents an efficient algorithm to test whether a given single-source acyclic digraph has an upward plane drawing and, if so, to find a representation of one such drawing. This result is made more significant in light of the recent proof by Garg and Tamassia that the problem is NP-complete for general digraphs.<\/jats:p>\n                  <jats:p>The algorithm decomposes the digraph into biconnected and triconnected components and defines conditions for merging the components into an upward plane drawing of the original digraph. To handle the triconnected components, we provide a linear algorithm to test whether a given plane drawing of a single-source digraph admits an upward plane drawing with the same faces and outer face, which also gives a simpler, algorithmic proof of Thomassen\u2019s result. The entire testing algorithm (for general single-source directed acyclic graphs) operates in $O(n^2 )$ time and $O(n)$ space (n being the number of vertices in the input digraph) and represents the first polynomial-time solution to the problem.<\/jats:p>","DOI":"10.1137\/s0097539792235906","type":"journal-article","created":{"date-parts":[[2005,2,24]],"date-time":"2005-02-24T06:43:31Z","timestamp":1109227411000},"page":"291-311","source":"Crossref","is-referenced-by-count":43,"title":["Upward Planar Drawing of Single-Source Acyclic Digraphs"],"prefix":"10.1137","volume":"25","author":[{"given":"Michael D.","family":"Hutton","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Anna","family":"Lubiw","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2006,7,13]]},"reference":[{"key":"R1","doi-asserted-by":"crossref","unstructured":"P. Bertolazzi, G. Di Battista,  On upward drawing testing of triconnected digraphs,  Proc. 7th ACM Symposium on Computational Geometry,  1991,  272\u2013280, Tech. report RAP.18.90, Dipartimento di Informatica a Sistemistica, Universit\u00e0 degli Studi di Roma \u201cLa Sapienza,\u201d 1991","DOI":"10.1145\/109648.109679"},{"key":"R2","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-349-03521-2"},{"key":"R3","doi-asserted-by":"publisher","DOI":"10.1016\/S0022-0000(76)80045-1"},{"key":"R4","doi-asserted-by":"crossref","unstructured":"H. de Fraysseix, J. Pach, R. Pollack,  Small sets supporting F\u00e0ry embeddings of planar graphs,  Proc. 20th ACM Symposium on the Theory of Computing (STOC),  1988,  426\u2013433","DOI":"10.1145\/62212.62254"},{"key":"R5","unstructured":"G. Di Battista, P. Eades, R. Tamassia, I. G. Tollis,  Algorithms for drawing graphs: An annotated bibliography,  1993, preprint, Department of Computer Science, Brown University, Providence, RI; ongoing version available via anonymous ftp from ftp.cs.brown.edu:pub\/papers\/compgeo\/,gdbiblio.tex.Z, and gdbiblio.ps.Z"},{"key":"R6","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(90)90045-Y"},{"key":"R7","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(88)90123-5"},{"key":"R8","doi-asserted-by":"publisher","DOI":"10.1007\/BF02187850"},{"key":"R9","first-page":"147","volume-title":"Advances in Computing Research, Vol. 2","author":"Dolev D.","year":"1984"},{"key":"R10","first-page":"229","volume":"11","author":"F\u00e1ry I.","year":"1948","journal-title":"Acta Univ. Szeged. Sect. Sci. Math."},{"key":"R11","doi-asserted-by":"crossref","unstructured":"I. S. Filotti, G. L. Miller, J. Reif,  On determining the genus of a graph in  O(\u03c5O(g)) steps,  Proc. 11th ACM Symposium on the Theory of Computing (STOC),  1979,  27\u201337","DOI":"10.1145\/800135.804395"},{"key":"R12","unstructured":"A. Garg, R. Tamassia,  On the computational complexity of upward and rectilinear planarity testing, Tech. report, CS-94-10, Department of Computer Science, Brown University, Providence, RI,  1994"},{"key":"R13","doi-asserted-by":"publisher","DOI":"10.1137\/0202012"},{"key":"R14","doi-asserted-by":"publisher","DOI":"10.1145\/321850.321852"},{"key":"R15","unstructured":"M. D. Hutton, Masters Thesis,  Upward planar drawing of single source acyclic digraphs, Master's thesis, University of Waterloo, Waterloo, ON, Canada,  1990"},{"key":"R16","unstructured":"Michael D. Hutton, Anna Lubiw,  Upward planar drawing of single source acyclic digraphs,  Proceedings of the Second Annual ACM-SIAM Symposium on Discrete Algorithms (San Francisco, CA, 1991), ACM, New York,  1991,  203\u2013211, (SODA) 1 095 8350785.05028"},{"key":"R17","doi-asserted-by":"publisher","DOI":"10.1016\/0012-365X(87)90008-2"},{"key":"R18","doi-asserted-by":"publisher","DOI":"10.4153\/CJM-1975-074-0"},{"key":"R19","doi-asserted-by":"publisher","DOI":"10.1016\/0095-8956(76)90024-1"},{"key":"R20","unstructured":"W. Schnyder,  Embedding planar graphs on the grid,  Proc. 1st ACM-SIAM Symposium on Discrete Algorithms (SODA),  1990,  138\u2013148 0786.05029"},{"key":"R21","doi-asserted-by":"publisher","DOI":"10.1090\/S0002-9939-1951-0041425-5"},{"key":"R22","volume-title":"Vorlesungen \u00fcber die Theorie de Polyeder","author":"Steinitz E.","year":"1934"},{"key":"R23","doi-asserted-by":"publisher","DOI":"10.1137\/0201010"},{"key":"R24","doi-asserted-by":"publisher","DOI":"10.1007\/BF00353654"},{"key":"R25","doi-asserted-by":"publisher","DOI":"10.1112\/plms\/s3-10.1.304"},{"key":"R26","first-page":"26","volume":"46","author":"Wagner K.","year":"1936","journal-title":"Jahresber. Deutsch. Math.-Verein."},{"key":"R27","doi-asserted-by":"publisher","DOI":"10.1090\/dimacs\/009"}],"container-title":["SIAM Journal on Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/S0097539792235906","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T18:56:09Z","timestamp":1787338569000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/S0097539792235906"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1996,4]]},"references-count":27,"journal-issue":{"issue":"2","published-print":{"date-parts":[[1996,4]]}},"alternative-id":["10.1137\/S0097539792235906"],"URL":"https:\/\/doi.org\/10.1137\/s0097539792235906","relation":{},"ISSN":["0097-5397","1095-7111"],"issn-type":[{"value":"0097-5397","type":"print"},{"value":"1095-7111","type":"electronic"}],"subject":[],"published":{"date-parts":[[1996,4]]}}}