%0 Book Section %1 cflrvw-cdgfl-WADS17 %A Chaplick, Steven %A Fleszar, Krzysztof %A Lipp, Fabian %A Ravsky, Alexander %A Verbitsky, Oleg %A Wolff, Alexander %B Proc. Algorithms Data Struct. Symp. (WADS'17) %D 2017 %E Ellen, Faith %E Kolokolova, Antonina %E Sack, Jörg-Rüdiger %I Springer-Verlag %K "affinity myown number" %P 265--276 %R 10.1007/978-3-319-62127-2_23 %T The Complexity of Drawing Graphs on Few Lines and Few Planes %U http://dx.doi.org/10.1007/978-3-319-62127-2_23 %V 10389 %X It is well known that any graph admits a crossing-free straight-line drawing in  \$\$\backslashmathbb \R\ ^3\$\$ and that any planar graph admits the same even in  \$\$\backslashmathbb \R\ ^2\$\$ . For a graph G and \$\$d \backslashin \backslash\2,3\backslash\\$\$ , let \$\$\backslashrho ^1\_d(G)\$\$ denote the minimum number of lines in \$\$\backslashmathbb \R\ ^d\$\$ that together can cover all edges of a drawing of G. For \$\$d=2\$\$ , G must be planar. We investigate the complexity of computing these parameters and obtain the following hardness and algorithmic results. %@ 978-3-319-62127-2

@inbook{cflrvw-cdgfl-WADS17, abstract = {It is well known that any graph admits a crossing-free straight-line drawing in  {\$}{\$}{\backslash}mathbb {\{}R{\}} ^3{\$}{\$} and that any planar graph admits the same even in  {\$}{\$}{\backslash}mathbb {\{}R{\}} ^2{\$}{\$} . For a graph G and {\$}{\$}d {\backslash}in {\backslash}{\{}2,3{\backslash}{\}}{\$}{\$} , let {\$}{\$}{\backslash}rho ^1{\_}d(G){\$}{\$} denote the minimum number of lines in {\$}{\$}{\backslash}mathbb {\{}R{\}} ^d{\$}{\$} that together can cover all edges of a drawing of G. For {\$}{\$}d=2{\$}{\$} , G must be planar. We investigate the complexity of computing these parameters and obtain the following hardness and algorithmic results.}, added-at = {2017-07-04T14:19:32.000+0200}, author = {Chaplick, Steven and Fleszar, Krzysztof and Lipp, Fabian and Ravsky, Alexander and Verbitsky, Oleg and Wolff, Alexander}, biburl = {https://www.bibsonomy.org/bibtex/2011bfa4b178509449d90757a21ca7ea3/fabianlipp}, booktitle = {Proc. Algorithms Data Struct. Symp. (WADS'17)}, doi = {10.1007/978-3-319-62127-2_23}, editor = {Ellen, Faith and Kolokolova, Antonina and Sack, Jörg-Rüdiger}, interhash = {a60ddbaa74f4f93956bf779200355549}, intrahash = {011bfa4b178509449d90757a21ca7ea3}, isbn = {978-3-319-62127-2}, keywords = {"affinity myown number"}, pages = {265--276}, publisher = {Springer-Verlag}, series = {Lecture Notes in Computer Science}, timestamp = {2017-07-04T14:19:32.000+0200}, title = {The Complexity of Drawing Graphs on Few Lines and Few Planes}, url = {http://dx.doi.org/10.1007/978-3-319-62127-2_23}, volume = 10389, year = 2017 }