Efficient algorithms for geometric representations of graphs

BUET ILS
BUET Institutional Repository: Home
→
Dissertations/Theses
→
Dissertations/Theses - Department of Computer Science and Engineering
→
View Item

dc.contributor.advisor	Rahman, Dr.Md.Saidur
dc.contributor.author	Sultana, Shaheena
dc.date.accessioned	2018-09-26T05:03:54Z
dc.date.available	2018-09-26T05:03:54Z
dc.date.issued	2018-02-28
dc.identifier.uri	http://lib.buet.ac.bd:8080/xmlui/handle/123456789/4997
dc.description.abstract	Agraphconsistsofasetofverticesandasetofedges,eachjoiningtwovertices.Age-ometricrepresentationofagraphisarepresentationofthegraphinwhichtheverticesandedgesarerepresentedbygeometricobjects.Visibilityrepresentations,orthogonalrepresen-tations,L-shapedrepresentations,covercontactgraphs(CCG)etc.aresomeexamplesofgeometricrepresentationsofgraphs.TheserepresentationshavenumerousapplicationsinVLSIlayoutdesign,statediagrams,facilitylocationproblem,dataflowdiagramsandso-cialnetworkvisualization.Inthisthesiswestudybar1-visibilityrepresentations,trianglecovercontactgraphs(TCCG),L-shapedorthogonalrepresentationsandL-shapedpointsetembeddings.Wegivelinear-timealgorithmstoconstructbar1-visibilityrepresentationsofdiagonalgridgraphs,maximalouter1-planegraphs,recursivequadrangle1-planargraphsandpseudodoublewheel1-planargraphs.Wefindefficientalgorithmstoconstructa3-connectedTCCGanda4-connectedTCCGforagivensetofpointseeds.Weshowthatconnectedouterplanargraphs,cubicplanarHamiltoniangraphsanda×bgridgraphsandournewlyintroducedsuper-HalingraphshaverealizationsasTCCGoncollinearseeds,andfindefficientalgorithmstofindsuchrealizations.Wealsoshowthatcompletegraphsaswellasournewlyintroducedclique-3graphshaverealizationsasTCCGs onanygivensetofseeds.InthisthesiswestudyL-shapedorthogonalrepresentationsofseries-parallelgraphsinvariableembeddingsettings.Weshowthateveryseries-parallelgraphofmaximumde-gree3aswellaseverymaximalouterplanegraphofmaximumdegree4admitsL-shapedorthogonalrepresentations.WegeneralizeL-shapedpointsetembeddingsforhighdegreeplanegraphs.WeshowthateverytreeaswellaseveryHalingraphadmitsplaneL-shapedpointsetembeddingsona2DpointsetPofnpointssuchthatnotwopointsinPlieonahorizontaloronaverticalline.	en_US
dc.language.iso	en	en_US
dc.publisher	Department of Computer Science and Engineering	en_US
dc.subject	Graph theory	en_US
dc.title	Efficient algorithms for geometric representations of graphs	en_US
dc.type	Thesis-PhD	en_US
dc.contributor.id	0412054002	en_US
dc.identifier.accessionNumber	116133
dc.contributor.callno	511.5/SHA/2018	en_US