文档下载 文档下载导航
设为首页 | 加入收藏
搜索 请输入内容:  
 导航当前位置: 文档下载 > 所有分类 > How Much Work Does It Take To Straighten a Plane Graph Out
侵权投诉

How Much Work Does It Take To Straighten a Plane Graph Out

We prove that if one wants to make a plane graph drawing straight-line then in the worst case one has to move almost all vertices.

7

2

l

Ju

3

2

]

OC

.

h

ta

m

[

1

v

3

7

3

3

.

7

7

:0v

i

X

r

aHowMuchWorkDoesItTakeToStraightenaPlaneGraphOut?M.Kang M.Schacht O.Verbitsky AbstractWeprovethatifonewantstomakeaplanegraphdrawingstraight-linethenintheworstcaseonehastomovealmostallvertices.Weusethestandardconceptsofaplanegraphandaplaneembedding(ordrawing)ofanabstractplanargraph(see,e.g.,[1]).GivenaplanegraphG,wewanttoredrawitmakingallitsedgesstraightlinesegmentswhilekeepingasmanyverticesonthespotaspossible.Letshift(G)denotethesmallestssuchthatwecandothejobbyshiftingonlysvertices.Wede nes(n)tobethemaximumshift(G)overallGwithnvertices.Thefunctions(n)canhaveanotherinterpretationcloselyrelatedtoanicewebpuzzlecalledPlanarityGame[3].Atthestartofthegame,aplayerseesastraightlinedrawingofaplanargraphwithmanyedgecrossings.Inamoves/heisallowedtoshiftonevertextoanewposition;theincidentedgesareredrawncorrespondingly(beingallthetimestraightlinesegments).Theobjectiveistoobtainacrossing-freedrawing.Thus,s(n)isequaltothenumberofmovesthattheplayer,playingoptimally,isforcedtomakeonann-vertexgameinstanceattheworstcase.

TheWagner-F´ary-Steintheorem(see,e.g.,[2])saysthateveryGhasastraightlineplaneembeddingandimmediatelyimpliesanupperbounds(n)≤n 3.Wehereaimatprovingalowerbound.

GivenanabstractplanargraphG,letshift(G)denotethemaximumshift(G′)overallplaneembeddingsG′ofG.Thus,weareseekingforGwith

第1页

你可能喜欢

热门文档

相关文档

站点地图 | 文档上传 | 侵权投诉 | 手机版
本站所有资源均来自互联网,本站只负责收集和整理,均不承担任何法律责任,如有侵权等其它行为请联系我们.
文档下载 Copyright 2013 doc.guandang.net All Rights Reserved.  -  email