A Survey on Graph Layout Problems #

ASurveyonGraphLayoutProblems∗JosepD´ıaz†JordiPetit†Mar´ıaSerna†October17,20001IntroductionInthispaperwesurveyresultsonseveralgraphlayoutproblemsfromanalgorithmicpointofview.Graphlayoutproblemsareaparticularclassofcombinatorialoptimizationproblemswhosegoalistofindalinearlayoutofaninputgraphinsuchwaythatacertainobjectivecostisoptimized.Alinearlayoutisalabelingofthenodesofagraphwithdistinctintegers.Alargeamountofrelevantproblemsindifferentareascanbeformulatedasgraphlayoutproblems.Theseincludenetworkoptimization,VLSIcircuitdesign,informationretrieval,numericalanalysis,computationalbiology,graphtheory,scheduling,archaeology,etc.Ontheotherhand,theminimalvaluesofsomelayoutcostsarealsorelatedtointerestinggraphtheoreticinvariantsofgraphs.MostofthegraphlayoutproblemsareNP-complete,but,inmanyoftheirapplications,feasiblesolutionswithanalmostoptimalcostaresufficientand,thus,approximationalgorithmsoreffectiveheuristicscanbeused.Thereexistdifferentothersurveysthatdealwithseveralaspectsofgraphlayoutprob-lems;seeforinstance[9,18,20,75].WehavetriedtogiveacompleteviewofthecurrentstateoftheartwithrespecttolayoutsproblemsThepaperisorganizedasfollows.InSection1,wedefineseverallayoutproblemsandstatesomebasicproperties.InSection2,wepresentmotivationsandapplicationsforthisfamilyofproblems.NegativeandpositivecomplexityresultsarereviewedinSection4.Section5presentsmethodstogetlowerboundsforlayoutproblems.InSections6and7,wepresentworkdoneinapproximationalgorithmsandheuristics,respectively.ProbabilisticresultsondifferentmodelsofrandomgraphsforlayoutproblemsarepresentedinSection8.Weclosethepaperwithaselectionofopenproblems.2TheproblemsA(linear)layoutϕofanundirectedgraphG=(V,E)withn=|V|nodesisabijectivefunctionϕ:V→{1,2,...,n}.WedenotebyΦ(G)thesetofalllayoutsofthegraphG.Alayoutisalsocalledalineararrangementoralabelingoranumberingofthenodesofagraph.∗ThisresearchwaspartiallysupportedbytheISTProgrammeoftheEUundercontractnumberIST-1999-14186(ALCOM-FT).†DepartamentdeLlenguatgesiSistemesInform`atics.UniversitatPolit`ecnicadeCatalunya.CampusNordC6.c/JordiGirona1-3.08034Barcelona,Catalonia.{diaz,jpetit,mjserna}@lsi.upc.es1abcdefghiL(i,ϕ,G)R(i,ϕ,G)achgbdefi123i=456789Figure1:AgraphGandagraphicalrepresentationofalayoutϕofG.GivenalayoutϕofagraphG=(V,E)andanintegeri,wedefinethesetsL(i,ϕ,G)={u∈V:ϕ(u)6i}andR(i,ϕ,G)={u∈V:ϕ(u)i}.The(edge)cutatpositioniofϕisdefinedasθ(i,ϕ,G)=|{uv∈E:u∈L(i,ϕ,G)∧v∈R(i,ϕ,G)}|andthemodified(edge)cutatpositioniofϕasζ(i,ϕ,G)=|{uv∈E:u∈L(i,ϕ,G)∧v∈R(i,ϕ,G)∧ϕ(u)6=i}|.Thevertexcutorseparationatpositioniofϕisdefinedasδ(i,ϕ,G)=|{u∈L(i,ϕ,G):∃v∈R(i,ϕ,G):uv∈E}|.GivenalayoutϕofGandanedgeuv∈E,thelengthofuvonϕisλ(uv,ϕ,G)=|ϕ(u)−ϕ(v)|.AnaturalwaytorepresentalayoutϕofagraphGistoalignitsnodesonaline,mappingnodeutopositionϕ(u),asshowninFig.1.AlayoutcostisafunctionFthatassociatestoeachlayoutϕofagraphGanintegerF(ϕ,G).LetFbealayoutcost;the(optimization)layoutproblemassociatedwithFconsistsindeterminingsomelayoutϕ∗∈Φ(G)ofaninputgraphGsuchthatF(ϕ∗,G)=minϕ∈Φ(G)F(ϕ,G)=F(G).InTable1weshow,theparticularlayoutcostsandthecorrespondingproblems.Atthispointitisrelevanttopointoutsomebasicbutrelevantobservations:Observation1.Thegraphlayoutproblemswehaveformulatedexplicitlyaskforanoptimallayoutratherthanthecostofanoptimallayout:“GivenagraphG,findalayoutϕ∗∈Φ(G)suchthatF(ϕ∗,G)=F(G).”Alltheproblemscanhoweverberestatedasdecisionalproblems,wherethetaskistodecidewhetherornotagraphadmitsalayoutwithcostnotgreaterthanacertaininputinteger:“GivenagraphGandanintegerK,istheresomelayoutϕ∈Φ(G)suchthatF(ϕ,G)6K?”Inthefollowing,wewillnotinsisttoomuchonwhichversionoftheproblemweareconsidering(optimizationordecisional),becausetheywillbedifferentiatedbythecontext.2ProblemNameCostBandwidthBandwidthbw(ϕ,G)=maxuv∈Eλ(uv,ϕ,G)MinLinearArrangementMinLAla(ϕ,G)=Puv∈Eλ(uv,ϕ,G)=Pni=1θ(i,ϕ,G)CutwidthCutwidthcw(ϕ,G)=maxni=1θ(i,ϕ,G)ModifiedCutModCutmc(ϕ,G)=Pni=1ζ(i,ϕ,G)VertexSeparationVertSepvs(ϕ,G)=maxni=1δ(i,ϕ,G)SumCutSumCutsc(ϕ,G)=Pni=1δ(i,ϕ,G)=pr(ϕR,G)ProfileProfilepr(ϕ,G)=ϕ(u)−minv∈Γ∗(u)ϕ(v)EdgeBisectionEdgeBiseb(ϕ,G)=θ(⌊n/2⌋,ϕ,G)VertexBisectionVertBisvb(ϕ,G)=δ(⌊n/2⌋,ϕ,G)Table1:LayoutproblemsforagraphG=(V,E)with|V|=n.Observation2.ForanygraphG=(V,E)andanylayoutϕofG,thetotaledgelengthequalsthesumofalledgecuts:Puv∈Eλ(uv,ϕ,G)=Pi∈[|V|]θ(i,ϕ,G).ThisfactwasfirstnoticedbyHarper[50].Itfollowsfromtheobservationthatanyedgeuv∈Ewithϕ(u)ϕ(v)contributesϕ(v)−ϕ(u)tothelefthandsideand1toeachoneofthetermsθ(ϕ(u),ϕ,G),θ(ϕ(u)+1,ϕ,G),...,θ(ϕ(v),ϕ,G)intherighthandside.Observation3.ForanygraphG=(V,E)andanylayoutϕofG,itisthecasethatpr(ϕ,G)=sc(ϕR,G)whereϕRdenotesthelayoutϕreversed(i.e.,ϕR(u)=|V|−ϕ(u)+1forallu∈V).Thereasonisthateachnodeu∈Vcontributesϕ(u)−minv∈Γ∗(u)ϕ(v)timesoneunittothesumcutinthereversedlayout.Asaconsequence,ProfileandSumCutareequivalentproblems!Observation4.LetGbeanygraphwithnnodesandmedges.Thefollowingresultsareabasicconsequenceofthepreviousdefinitions.la(G)6n·cw(G),la(G)6m·bw(G),sc(G)6n·vs(G),mc(G)6la(G),vb(G)6vs(G)6bw(G),eb(G)6cw(G).Observation5.ForanylayoutcostFintheset{bw,cw,vs,la,mc,sc},itispossibletoobtainanoptim