{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,28]],"date-time":"2024-09-28T04:26:57Z","timestamp":1727497617623},"reference-count":0,"publisher":"Journal of Graph Algorithms and Applications","issue":"2","license":[{"start":{"date-parts":[[2023,2,1]],"date-time":"2023-02-01T00:00:00Z","timestamp":1675209600000},"content-version":"unspecified","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["JGAA"],"abstract":"<jats:p>The slope number of a graph $G$ is the smallest number of slopes needed \nfor the segments representing the edges in any straight-line drawing of $G$.\nIt serves as a measure of the visual complexity of a graph drawing.\nSeveral bounds on the slope number for particular graph classes have been established, \nboth in the planar and the non-planar setting.\nMoreover, the slope number can also be defined for directed graphs and upward planar drawings.\n\nWe study upward planar straight-line drawings that use only a constant number of slopes.\nIn particular, for a fixed number $k$ of slopes,\nwe are interested in whether a given directed graph $G$ \nwith maximum in- and outdegree at most $k$\nadmits an upward planar $k$-slope drawing.\nWe investigate this question both in the fixed and the\nvariable embedding scenario.\nWe show that this problem is in general NP-hard \nto decide for outerplanar graphs ($k = 3$) and planar graphs ($k \\ge 3$).\nOn the positive side, we can decide whether a given cactus graph\nadmits an upward planar $k$-slope drawing and, in the affirmative, construct such a drawing \nin FPT time with parameter $k$.\nFurthermore, we can determine the minimum number of slopes required for a given tree in linear time \nand compute the corresponding drawing efficiently.<\/jats:p>","DOI":"10.7155\/jgaa.00617","type":"journal-article","created":{"date-parts":[[2023,2,25]],"date-time":"2023-02-25T13:40:08Z","timestamp":1677332408000},"page":"49-70","source":"Crossref","is-referenced-by-count":0,"title":["Upward Planar Drawings with Three and More Slopes"],"prefix":"10.7155","volume":"27","author":[{"given":"Jonathan","family":"Klawitter","sequence":"first","affiliation":[]},{"given":"Johannes","family":"Zink","sequence":"additional","affiliation":[]}],"member":"4175","published-online":{"date-parts":[[2023,2,1]]},"container-title":["Journal of Graph Algorithms and Applications"],"original-title":[],"link":[{"URL":"https:\/\/jgaa.info\/index.php\/jgaa\/article\/download\/paper617\/2338","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/jgaa.info\/index.php\/jgaa\/article\/download\/paper617\/2338","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,9,27]],"date-time":"2024-09-27T20:10:58Z","timestamp":1727467858000},"score":1,"resource":{"primary":{"URL":"https:\/\/jgaa.info\/index.php\/jgaa\/article\/view\/paper617"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,2,1]]},"references-count":0,"journal-issue":{"issue":"2","published-online":{"date-parts":[[2023,2,1]]}},"URL":"https:\/\/doi.org\/10.7155\/jgaa.00617","relation":{},"ISSN":["1526-1719"],"issn-type":[{"type":"electronic","value":"1526-1719"}],"subject":[],"published":{"date-parts":[[2023,2,1]]}}}