{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,8,6]],"date-time":"2025-08-06T12:12:51Z","timestamp":1754482371691},"reference-count":0,"publisher":"Journal of Graph Algorithms and Applications","issue":"6","license":[{"start":{"date-parts":[[2023,7,1]],"date-time":"2023-07-01T00:00:00Z","timestamp":1688169600000},"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>It is well known that any graph admits a crossing-free straight-line\n  drawing in $\\mathbb{R}^3$ and that any planar graph admits the same even\n  in $\\mathbb{R}^2$.  For a graph $G$ and $d \\in \\{2,3\\}$, let\n  $\\rho^1_d(G)$ denote the smallest number of lines in $\\mathbb{R}^d$\n  whose union contains a crossing-free straight-line drawing of $G$.\n  For $d=2$, the graph $G$ must be planar.  Similarly, let\n  $\\rho^2_3(G)$ denote the smallest number of planes\n  in $\\mathbb{R}^3$ whose union contains a crossing-free straight-line\n  drawing of $G$.\n\n  We investigate the complexity of computing these three\n  parameters and obtain the following hardness and algorithmic\n  results.\n  \n  For $d\\in\\{2,3\\}$, we prove that deciding whether\n    $\\rho^1_d(G)\\le k$ for a given graph $G$ and integer $k$ is\n    $\\exists\\mathbb{R}$-complete.\n  Since $NP \\subseteq \\exists\\mathbb{R}$, deciding $\\rho^1_d(G)\\le\n    k$ is $NP$-hard for $d\\in\\{2,3\\}$.  On the positive side, we show\n    that the problem is fixed-parameter tractable with respect to $k$.\n   Since $\\exists\\mathbb{R} \\subseteq PSPACE$, both $\\rho^1_2(G)$\n     and $\\rho^1_3(G)$ are computable in polynomial space. On the\n     negative side, we show that  drawings that are optimal with respect to $\\rho^1_2$ or $\\rho^1_3$  sometimes require irrational coordinates.\n   We prove that deciding whether $\\rho^2_3(G)\\le k$ is\n    $NP$-hard for any fixed $k \\ge 2$.  Hence, the problem is not\n    fixed-parameter tractable with respect to $k$ unless\n    $P=NP$.\n  <\/jats:p>","DOI":"10.7155\/jgaa.00630","type":"journal-article","created":{"date-parts":[[2023,7,14]],"date-time":"2023-07-14T14:42:02Z","timestamp":1689345722000},"page":"459-488","source":"Crossref","is-referenced-by-count":2,"title":["The Complexity of Drawing Graphs on Few Lines and Few Planes"],"prefix":"10.7155","volume":"27","author":[{"given":"Steven","family":"Chaplick","sequence":"first","affiliation":[]},{"given":"Krzysztof","family":"Fleszar","sequence":"additional","affiliation":[]},{"given":"Fabian","family":"Lipp","sequence":"additional","affiliation":[]},{"given":"Alexander","family":"Ravsky","sequence":"additional","affiliation":[]},{"given":"Oleg","family":"Verbitsky","sequence":"additional","affiliation":[]},{"given":"Alexander","family":"Wolff","sequence":"additional","affiliation":[]}],"member":"4175","published-online":{"date-parts":[[2023,7,1]]},"container-title":["Journal of Graph Algorithms and Applications"],"original-title":[],"link":[{"URL":"https:\/\/jgaa.info\/index.php\/jgaa\/article\/download\/paper630\/2326","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/jgaa.info\/index.php\/jgaa\/article\/download\/paper630\/2326","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,9,27]],"date-time":"2024-09-27T20:09:46Z","timestamp":1727467786000},"score":1,"resource":{"primary":{"URL":"https:\/\/jgaa.info\/index.php\/jgaa\/article\/view\/paper630"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,7,1]]},"references-count":0,"journal-issue":{"issue":"6","published-online":{"date-parts":[[2023,7,1]]}},"URL":"https:\/\/doi.org\/10.7155\/jgaa.00630","relation":{},"ISSN":["1526-1719"],"issn-type":[{"type":"electronic","value":"1526-1719"}],"subject":[],"published":{"date-parts":[[2023,7,1]]}}}