%0 Book Section %1 Chaplick2017 %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) %C Cham %D 2017 %E Ellen, Faith %E Kolokolova, Antonina %E Sack, Jörg-Rüdiger %I Springer %K conference myown publication %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 https://doi.org/10.1007/978-3-319-62127-2_23 %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{Chaplick2017, 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-09-13T10:07:36.000+0200}, address = {Cham}, author = {Chaplick, Steven and Fleszar, Krzysztof and Lipp, Fabian and Ravsky, Alexander and Verbitsky, Oleg and Wolff, Alexander}, biburl = {https://www.bibsonomy.org/bibtex/2ff926d86a024af6857988b10851a95f7/chaplick}, booktitle = {Proc. Algorithms Data Struct. Symp. (WADS'17)}, description = {The Complexity of Drawing Graphs on Few Lines and Few Planes | SpringerLink}, doi = {10.1007/978-3-319-62127-2_23}, editor = {Ellen, Faith and Kolokolova, Antonina and Sack, Jörg-Rüdiger}, interhash = {a60ddbaa74f4f93956bf779200355549}, intrahash = {ff926d86a024af6857988b10851a95f7}, isbn = {978-3-319-62127-2}, keywords = {conference myown publication}, pages = {265--276}, publisher = {Springer}, series = {Lecture Notes in Computer Science}, timestamp = {2017-09-13T10:18:24.000+0200}, title = {The Complexity of Drawing Graphs on Few Lines and Few Planes}, url = {https://doi.org/10.1007/978-3-319-62127-2_23}, year = 2017 }