?url_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Adc&rft.title=Planar+Decompositions+and+the+Crossing+Number+of+Graphs+with+an+Excluded+Minor&rft.creator=Wood%2C+David+R.&rft.creator=Telle%2C+Jan+Arne&rft.subject=G.420+Crossings&rft.subject=M.999+Others&rft.subject=Z.999+Others&rft.description=Tree+decompositions+of+graphs+are+of+fundamental+importance+in+structural+and+algorithmic+graph+theory.+Planar+decompositions+generalise+tree+decompositions+by%0D%0Aallowing+an+arbitrary+planar+graph+to+index+the+decomposition.+We+prove+that+every+graph+that+excludes+a+fixed+graph+as+a+minor+has+a+planar+decomposition+with%0D%0Abounded+width+and+a+linear+number+of+bags.%0D%0AThe+crossing+number+of+a+graph+is+the+minimum+number+of+crossings+in+a+drawing+of+the+graph+in+the+plane.+We+prove+that+planar+decompositions+are+intimately+related+to+the+crossing+number%2C+in+the+sense+that+a+graph+with+bounded+degree+has+linear+crossing+number+if+and+only+if+it+has+a+planar+decomposition+with+bounded+width+and+linear+order.+It+follows+from+the+above+result+about+planar+decompositions+that+every+graph+with+bounded+degree+and+an+excluded+minor+has+linear+crossing+number.%0D%0AAnalogous+results+are+proved+for+the+convex+and+rectilinear+crossing+numbers.+In+particular%2C+every+graph+with+bounded+degree+and+bounded+tree-width+has+linear+convex+crossing+number%2C+and+every+K_3%2C3-minor-free+graph+with+bounded+degree+has+linear+rectilinear+crossing+number.%0D%0A++++&rft.publisher=Springer&rft.contributor=Kaufmann%2C+Michael&rft.contributor=Wagner%2C+Dorothea&rft.date=2007&rft.type=Conference+Paper&rft.type=NonPeerReviewed&rft.identifier=Wood%2C+David+R.+and+Telle%2C+Jan+Arne+(2007)+Planar+Decompositions+and+the+Crossing+Number+of+Graphs+with+an+Excluded+Minor.+[Conference+Paper]&rft.relation=http%3A%2F%2Fgdea.informatik.uni-koeln.de%2F770%2F