?url_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Adc&rft.title=Complexity+Results+for+Three-dimensional+Orthogonal+Graph+Drawing&rft.creator=Patrignani%2C+Maurizio&rft.subject=P.600.700+Orthogonal&rft.subject=G.999+Others&rft.subject=P.060+3D&rft.description=We+introduce+the+3SAT+reduction+framework+which+can+be+used+to+prove+the+NP-hardness+of+finding+three-dimensional+orthogonal+drawings+with+specific+constraints.+We+use+it+to+show+that+finding+a+drawing+of+a+graph+whose+edges+have+a+fixed+shape+is+NP-hard.+Also%2C+it+is+NP-hard+finding+a+drawing+of+a+graph+with+nodes+at+prescribed+positions+when+a+maximum+of+two+bends+per+edge+is+allowed.+We+comment+the+impact+of+these+results+on+the+two+open+problems+of+determining+whether+a+graph+always+admits+a+3D+orthogonal+drawing+with+at+most+two+bends+per+edge+and+of+characterizing+orthogonal+shapes+admitting+a+drawing+without+intersections.%0D%0A++++&rft.publisher=Springer&rft.contributor=Healy%2C+Patrick&rft.contributor=Nikolov%2C+Nikola+S.&rft.date=2006&rft.type=Conference+Paper&rft.type=NonPeerReviewed&rft.identifier=Patrignani%2C+Maurizio+(2006)+Complexity+Results+for+Three-dimensional+Orthogonal+Graph+Drawing.+[Conference+Paper]&rft.relation=http%3A%2F%2Fgdea.informatik.uni-koeln.de%2F705%2F