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.
