?url_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Adc&rft.title=Bar+k-Visibility+Graphs%3A+Bounds+on+the+Number+of+Edges%2C+Chromatic+Number%2C+and+Thickness&rft.creator=Dean%2C+Alice+M.&rft.creator=Evans%2C+William&rft.creator=Gethner%2C+Ellen&rft.creator=Laison%2C+Joshua+D.&rft.creator=Safari%2C+Mohammad+Ali&rft.creator=Trotter%2C+William+T.&rft.subject=Z.999+Others&rft.description=Let+S+be+a+set+of+horizontal+line+segments%2C+or+bars%2C+in+the+plane.+We+say+that+G+is+a+bar+visibility+graph%2C+and+S+its+bar+visibility+representation%2C+if+there+exists+a+one-to-one+correspondence+between+vertices+of+G+and+bars+in+S%2C+such+that+there+is+an+edge+between+two+vertices+in+G+if+and+only+if+there+exists+an+unobstructed+vertical+line+of+sight+between+their+corresponding+bars.+If+bars+are+allowed+to+see+through+each+other%2C+the+graphs+representable+in+this+way+are+precisely+the+interval+graphs.+We+consider+representations+in+which+bars+are+allowed+to+see+through+at+most+k+other+bars.+Since+all+bar+visibility+graphs+are+planar%2C+we+seek+measurements+of+closeness+to+planarity+for+bar+k-visibility+graphs.+We+obtain+an+upper+bound+on+the+number+of+edges+in+a+bar+k-visibility+graph.+As+a+consequence%2C+we+obtain+an+upper+bound+of+12+on+the+chromatic+number+of+bar+1-visibility+graphs%2C+and+a+tight+upper+bound+of+8+on+the+size+of+the+largest+complete+bar+1-visibility+graph.+We+conjecture+that+bar+1-visibility+graphs+have+thickness+at+most+2.%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=Dean%2C+Alice+M.+and+Evans%2C+William+and+Gethner%2C+Ellen+and+Laison%2C+Joshua+D.+and+Safari%2C+Mohammad+Ali+and+Trotter%2C+William+T.+(2006)+Bar+k-Visibility+Graphs%3A+Bounds+on+the+Number+of+Edges%2C+Chromatic+Number%2C+and+Thickness.+[Conference+Paper]&rft.relation=http%3A%2F%2Fgdea.informatik.uni-koeln.de%2F681%2F