Citation
Coloring toroidal graphs while conserving colors

Material Information

Title:
Coloring toroidal graphs while conserving colors
Creator:
Mantey, Zachary A. ( author )
Place of Publication:
Denver, CO
Publisher:
University of Colorado Denver
Publication Date:
Language:
English
Physical Description:
1 electronicfile (137 pages). : ;

Subjects

Subjects / Keywords:
Graph coloring ( lcsh )
Torus (Geometry) ( lcsh )
Graph theory ( lcsh )
Genre:
bibliography ( marcgt )
theses ( marcgt )
non-fiction ( marcgt )

Notes

Review:
Graph Theory has been used throughout Computer Science ranging amongst topics such as scheduling, network mapping, fingerprint identification, symbol recognition, and network security. Graph coloring has a significant role in each of these tasks, further developing the models used to solve problems in these areas. A specific facet of graph theory is embedding, and is most widespread in the fields of chip testing and solid state drive technology. The embeddings used in these areas are planar, since computer chips and hard drives have components embedded on a single silicon sheet. I investigate Albertson's conjecture regarding the coloring of graphs embeddable on the torus. The torus allows for a multitude of graphs, which may be used to model chips and hard drives, to be embedded. Coloring these graphs allows more modeling of specific problems. The conjecture states that any graph embedded on the torus may be colored with the same four colors excepting up to three vertices.
Thesis:
Thesis (M.S.)--University of Colorado Denver. Computer science
Bibliography:
Includes bibliographic references.
General Note:
Department of Computer Science and Engineering
Statement of Responsibility:
by Zachary A. Mantey.

Record Information

Source Institution:
|University of Colorado Denver
Holding Location:
|Auraria Library
Rights Management:
All applicable rights reserved by the source institution and holding location.
Resource Identifier:
912929334 ( OCLC )
ocn912929334

Downloads

This item is only available as the following downloads:


Full Text

PAGE 1

COLORINGTOROIDALGRAPHSWHILECONSERVINGCOLORS by ZACHARYA.MANTEY B.S.MathematicsandComputerScience,ColoradoSchoolofMines,2009 Athesissubmittedtothe FacultyoftheGraduateSchoolofthe UniversityofColoradoinpartialfulllment oftherequirementsforthedegreeof MasterofScience ComputerScience 2015

PAGE 2

ThisthesisfortheMasterofSciencedegreeby ZacharyA.Mantey hasbeenapprovedforthe ComputerScienceProgram by EllenGethner,Chair GitaAlaghband MichaelFerrara April10,2015 ii

PAGE 3

Mantey,ZacharyA.M.S.,ComputerScience Coloringtoroidalgraphswhileconservingcolors ThesisdirectedbyEllenGethner ABSTRACT GraphTheoryhasbeenusedthroughoutComputerSciencerangingamongst topicssuchasscheduling,networkmapping,ngerprintidentication,symbolrecognition,andnetworksecurity.Graphcoloringhasasignicantroleineachofthese tasks,furtherdevelopingthemodelsusedtosolveproblemsintheseareas.Aspecic facetofgraphtheoryisembedding,andismostwidespreadintheeldsofchiptesting andsolidstatedrivetechnology.Theembeddingsusedintheseareasareplanar,since computerchipsandharddriveshavecomponentsembeddedonasinglesiliconsheet. IinvestigateAlbertson'sconjectureregardingthecoloringofgraphsembeddableon thetorus.Thetorusallowsforamultitudeofgraphs,whichmaybeusedtomodel chipsandharddrives,tobeembedded.Coloringthesegraphsallowsmoremodeling ofspecicproblems.Theconjecturestatesthatanygraphembeddedonthetorus maybecoloredwiththesamefourcolorsexceptinguptothreevertices. Theformandcontentofthisabstractareapproved.Irecommenditspublication. Approved:EllenGethner iii

PAGE 4

TothememoryofMichealO.Albertson iv

PAGE 5

ACKNOWLEDGMENT IwouldliketothankProfessorEllenGethnerforhersupportasmymentor,teacher, andadvisor.Iappreciatethetimeandeortithastakenintobringingmeupfrom aedglingresearchertothispoint,andforcritiquingmyresearchandreadingmy thesisdrafts.Icouldnothaveachievedthiswithouther. IwouldliketothankProfessorsMichaelFerraraandGitaAlaghbandfortheir timeandeortinbeingmythesisreaders. IwouldliketothankDr.WilliamKocayfromtheUniversityofManitobafor hisinputandcodesamplesassistingtheresearchandimplementationofmythesis. IwouldalsoliketothankJiahuaYufromSimonFraserUniversity,forsupplyingme withhisthesisresultsandtoroidalembeddinglibraryfromhisownthesiscompleted lastyear.Thesetworepresentthehighestqualityofacademiccollaboration. Finally,Iwouldliketoexpressmydeepestappreciationformywife,Kimberly Mantey,inherunwaiveringsupportandencouragementduringtheprocessofobtainingmymaster'sdegree.Withouthersupport,thisthesiswouldnothavebeen possible. v

PAGE 6

TABLEOFCONTENTS Figures.......................................viii Tables........................................x Chapter 1.Background...................................1 1.1GraphTheoryinComputerScience..................1 1.2ABriefHistoryofGraphTheory....................4 1.3TheProblem...............................6 1.4BasicTheory...............................7 1.4.1Surfaces..............................7 1.4.2Graphs..............................9 1.4.3NewDenitions..........................16 2.ConstructingGraphs..............................19 2.1GraphGeneration............................19 2.2TheFirstRule..............................19 2.3TheSecondRule.............................20 2.4TheThirdRule.............................20 2.5TheFourthRule.............................21 3.TestingGraphs.................................22 3.1AlgorithmMotivation..........................22 3.2TheAlgorithm..............................27 3.3InitialResults..............................29 3.4Improvingresults............................36 3.5The M graph..............................37 4.AnalysisandResults..............................39 5.FurtherResearchandConclusions.......................49 6.AppendixA...................................51 vi

PAGE 7

References ......................................125 vii

PAGE 8

FIGURES Figure 1.1Precursortomicrochip............................2 1.2List-coloring..................................4 1.3Konigsberg..................................5 1.4TreeGraph..................................6 1.5Mobiusstrip.................................9 1.6TheTorus...................................9 1.7ThreeholedTorus-torus.........................9 1.8subdivision..................................11 1.9contraction..................................12 1.10Petersen....................................12 1.11Hadwiger...................................15 1.12The J graph.................................16 1.13AMajorvertex.................................17 1.14AMajoredge.................................17 2.1CombinatorialThumbtacks.........................21 3.1 K 5 SubdivisionGraph............................23 3.2MajorVertexIsolation............................24 3.3TheOriginalGraph.............................30 3.4EdgeContracted:,0............................32 3.5EdgeContracted:,0............................32 3.6EdgeContracted:,0............................32 3.7EdgeContracted:,9............................32 3.8MajorVertices................................32 3.9FinalColoring................................34 3.10The M graph.................................37 viii

PAGE 9

3.11The M graphmajorvertices.........................37 3.12The M graphafteroneisolation......................38 3.13The M graphproperlycolored.......................38 s ix

PAGE 10

TABLES Table 3.1InitialResults.................................35 4.17VertexResults...............................39 4.28VertexResults...............................40 4.39VertexResults...............................41 4.410VertexResults..............................42 4.511VertexResults..............................43 4.612VertexResults..............................44 4.713VertexResults..............................45 4.814VertexResults1..............................46 4.914VertexResults2..............................47 4.1015VertexResults..............................48 x

PAGE 11

1.Background 1.1GraphTheoryinComputerScience GraphTheoryisasectionofmathematicsdescribingthetopology,construction, traversal,andcoloringofgraphs.IthasmanyapplicationsthroughoutComputer Science,includingtraveloptimization[27],chiptopologytests[20],schedulingalgorithms[24,33],databasedesigns[23],andnaturallanguageprocessing[4].Awell knownapplicationofgraphtheoryintraveloptimizationisGoogleMaps,amapping technologywhichcandesignroutesbasedonvariouscriteria.Inthisapplication, theverticesofthegrapharetheintersectionsofroads,andtheroadsthemselvesare theedges.Theshortest-pathproblemisthenappliedtothemodel,anddirections aregivenbasedoncertainparameterstheuserdenes.Thesepreferencestheuser submitstotheapplicationarethenappliedasweightstotheedgesofthegraphand theshortest-pathproblemisrunagainwiththenewinput[27].TheprominentDijktra'salgorithmisoftenappliedtothisproblem,althoughfromboththesourceand destination,andthetreesareexpandeduntiltheymeetinthemiddle.Thisproduces asignicantreductionincomplexityandcomputationtime. Intherealmofchiptopologytestinganddesigngraphtheoryplaysanimportant role.Asarule,thewiresonacomputerchipcannotcross,duetothevoltagecomplicationsintroduced.Ingraphtheory,thecomponentsofthechipareverticesina graphandthewiresthatconnectthemareedges.Agraphforwhichedgesdonot crossisdenedasaplanegraph.Thesedenitionsareincludedinasubsetofgraph theorytermedembedding,whichfocusesonhowtodrawgraphsonsurfaceswhere edgesofthegraphdonotcross.Thefactthatwiresdonotcrossisnottheonly designconsideration,however.Thecomponentsofcomputerchipsmustbearranged insuchawaythatthetimeittakestocompleteanoperationusingthosecomponents isoptimal.Thisisdonebyassigningweightsbetweenthecomponentsthatrepresent priority.Therearealgorithmsthatattempttoproducetheoptimalchiptopology usinggraphtheory[20]. 1

PAGE 12

Figure1.1: Theprecursortothemodernmicrochip,theTexasInstrumentsall semiconductorsolidcircuitdesignedbyJackKilby 2

PAGE 13

Graphcoloringisasubsetofgraphtheory,anditisveryoftenusedinscheduling problems[24,33].Thegoalofthisrealmofthescienceistoobtainapropercoloring ofthegraph,oroneforwhichtwoadjacentverticesdonothavethesamecolor.For example,asetofjobsneedstobecompletedandsomejobsrequirethesameresources. Theproblemistoschedulethejobsinsuchawaythattheresourcesarenotaccessed atthesametime.Aconictgraphiscreatedwheretheverticesofthegrapharethe jobsthemselvesandtheedgesconnectjobsthatshareresources.Thecolorsinthis examplearetimeslotswhenthesejobshavetheavailableresourcestobecompleted. Whenapropercoloringofthegraphisassigned,theoptimaltimeslotsperjobhave beenfound.Thesamemethodhasbeenappliedincommercialapplicationssuchas airtraccontrolandmerchantpackaginganddeliverysystems[25]. Anextensionofthegraphcoloringexampleisasubsetoftheproblemtermed listcoloring,whereeachvertexhasalistofavailablecolors.Thiscanbeusedto modeldierentresourceconstraintsonthejobbeingperformed.Thegoalofthe graphtheoristinthisinstanceistondapropercoloringjustaswiththeprevious example.Thishasgreaterapplicationintheshippingindustrythaninprogramssuch asGoogleMaps.However,ithasmanyapplicationsinproblemswhereresourcesare limitedoronlyavailableduringcertaintimes[15,22]. Itiswithgraphcoloringthatthispaperisconcerned,aswefocusonanareaof thesciencethatinvolvessurfacesthataremorecomplexthanthesphere.Thesphere, whichistheonepointcompacticationoftheplane,isusedtomodelmanydierent reallifescenariosconcerninggraphsandgraphcoloring.Thepreviouslymentioned GoogleMapsisonesuchproblem.Anotheristhecoloringofmapsandthecountries representedwithoutadjacentnationscoloredthesameway.Ithasbeenproventhat oneneedsonlyfourcolorssee"FourColorTheorem"tofulllapropercoloringof suchamap[30]. 3

PAGE 14

Figure1.2: Anexampleoflistcoloring. 1.2ABriefHistoryofGraphTheory In1736amathematiciannamedLeonhardEulerpublishedapaperontheseven bridgesofKonigsberg.Itconcernedaproblemwhereinthemathematiciandesired towalkapaththroughthecitythatcrossedeachbridgeexactlyonce.Thecitywas setonbothsidesofthePregelRiver,andincludedtwolargeislandsconnectedto eachotherandthemainlandbysevenbridges.Inthispaper,Eulerprovedthatthe problemhadnosolution,andgraphtheorywascreated[11].Suchpathsdenedin thispaperarenowcalledEulerianpaths.Theformularelatingtothenumberof edges,vertices,andfacesofapolygondescribedbyEulerinthispaperalsoleadto thecreationofthesectionofmathematicsknownastopology. Morethanahundredyearslaterin1857,ArthurCayleypublishedapapertitled `Onthetheoryoftheanalyticalformscalledtrees'[7].Atreeisaspecialtypeofgraph 4

PAGE 15

Figure1.3: ThecurrentlayoutoftheKonigsbergbridges.Thebridgesmarkedin redhavebeendestroyed,theonesingreenrepresenttheoriginalbridges. inwhichanytwoverticesareconnectedbyexactlyonepath,andthispaperfurthered thestudyofgraphtheory.Theterm'graph'wascoinedbyJamesJosephSylvester, anEnglishmathematician,in1878inajournalentitled'Nature'inanarticlethat wasconcernedwithalgebraandmoleculardiagrams[34].In1936,thersttextbook onthesubjectofgraphtheorywaspublishedbyHungarianmathematicianDenes K}onig[17].ThistextbookwasimprovedonbyanAmericanmathematiciannamed FrankHarary,whoseworkwasatonetimeconsideredtobethedenitivetextbook onthesubject[14]. Oneofthemostpopularandprolicproblemsingraphtheorywasthefour-color problem,posedbySouthAfricanmathematicianandbotanistFrancisGuthriein 1852.Theproblemstates,Isittruethatanymapdrawnintheplanemayhaveits regionscoloredwithfourcolors,insuchawaythatanytworegionshavingacommon borderhavedierentcolors?"Therstrecordofthisproblemisinalettersent 5

PAGE 16

Figure1.4: Anexampleofatreegraph. fromtheEnglishmathematicianAugustusDeMorgan,wholivedinIndia,tofellow scientistandmathematicianWilliamHamilton,whowasfromandlivedinIreland. Manyawedproofsweresubmittedforthisproblemoveraperiodof145yearsbefore theacceptedproofwaswrittenin1976byAppelandHaken[2]andimprovedin1997 byRobertson,Seymour,SandersandThomas[30]. Manyotheradvancesinthesciencehavebeenmadeinthetimebetweenthese smallbutimportantpointsinhistoryandthepresent,thetopicscoveredbygraph theoryrangingfurtherandfurtherasnewdiscoveriesaremade.Theproofofthefourcolortheoremfortheplanehascompletedthequestionasitappliestothesurface.It haspushedthequestformoreanswerstothetorus,andthemorecomplextoroidal surfaces. 1.3TheProblem TheproblemwearetacklinginthispaperisonegivenbyAlbertsoninhisarticle submittedtothejournalofProceedingsoftheLondonMathematicalSociety[1]that ispresentedintheformofaconjecturethatstates,Thegraphsembeddableonthe torusmaybecoloredwithmostlyfourcolorsexceptinguptothreevertices."This resultbeingprovenwouldhaveinterestingresultsintheapplicationsofgraphtheory. 6

PAGE 17

Itmaybepossibletomodelcertainproblemsastoroidalgraphsandrunalgorithms onthemtoproducesignicantresults.Theexceptionofthreeverticesmaybeused tomodelthreeuniqueconditionsinaproblemwheremostfunctionslieinthefour colorarea. Whatthisproblemposesinsimplelanguageisthatwhencoloringgraphsonthe torus,onecanusethesamefourcolorstocolormostofthegraphinsuchawaythat notwoadjacentverticesarethesamecolor.Whenagraphtheoristproperlycolors mostofthegraph,therewillbeuptothreeverticesthatcannotbecoloredbyanyof theoriginalfourcolorsandthusneedtobecoloredbyafth,sixth,orseventhcolor. Forgraphsontheplanewithnoedgecrossings,theFourColorTheoremstands.This conjecture,ifproven,wouldbesimilartotheFourColorTheoremfortheplane. Wehavefurthernarrowedthedenitionofthisconjecturebasedontheresearch wehavedone.Wecontendthatinadditiontotheoriginalconjecture,thethree verticesexceptedbythesecoloringslieonsubgraphswhichareisomorphictocomplete graphsortheirsubdivisions.Thiswouldalsomeanthatanygraphnotcontaining asubgraphisomorphictothecompletegraphsembeddableonthetorusortheir subdivisionsarefour-colorable.Wealsoinvestigatewhetherthenumberofvertices exceptedfromthefour-coloringisequaltotheorderofthecompletesubgraphless four.Forexample,ifthetoroidalgraphcontainsa K 5 oritssubdivision,thenumber ofverticesexceptedbythefour-coloringisequaltoone. 1.4BasicTheory Inthissectionthegraphtheorynecessarytounderstandtheresearchofthis problemisreviewed. 1.4.1Surfaces Asurface S isconsideredorientableifitispossibletomakeaconsistentchoice ofasurfacenormalvectorateverypoint.Almostallsurfacesweencounterinthe 7

PAGE 18

worldareorientable.Thesphere,everymemberofthetorusfamily,andplanesare orientable.Whiletravelingacrossthesesurfaces,wealwaysknowwhichdirectionis up.ImaginetravelingacrosstheplanetEarthinanairplane.Thereisnosudden pointduringtheightwhenupbecomesdown,andviceversa.Eveniftheplane circumnavigatestheglobe,theskywillalwaysbeupandthelandsandoceansdown. Ifonecirclestheearth,theywilltravelthecircumferenceonlyonce. Ifasurfaceisnon-orientable,thereisapointwheretheorientationchanges.The Mobiusstrip,forexample,isanon-orientablesurface.Ifoneweretravelalongthe Mobiusstrip,theywouldgotwicearoundthesurfacebeforereturningtothestarting position.Inotherwords,thecircumferenceofthe"loop"oftheMobiusstripwould betraveledtwiceduringacircumnavigationofthestrip. Toexplainfurther,theorientationofasurfaceexistsinside"thesurfaceitself. Imaginetwopeoplelivinginthesurfaceofamobiusstrip,onewaveswiththeleft hand,andtheotherwiththeright.Thelefthandedwaiverdecidestoexplorethe surfacetondmorepeoplethatwaivewiththelefthand.Sincethesurfaceisastrip, thepersoncanalwaysseetotheotherside,justasapersontravelingthespherecould alwaysseeintothecenter,andoutintothespaceopposite.Thepersontravelsand goesonecircumferencearoundthestripandndsanotherpersonwaivingwiththeir lefthandatlast.However,itismerelythesamecompaniontheyhadbefore,with theorientationchanged. Thispaperdealswithorientablesurfaces,namelytheplaneandthetorus.The torusisshapedlikeadonut,oraspherewithahandleattached.Manyshapesadhere tothisdescription,suchasacoeemug,apipe,awatchwhenclasped.Thereare severalwaystoformatorusbutthispaperwilldealwiththesimplestrendering,the donut.Therearemanyfactsaboutthetoruswhichmakesitinteresting.Therst hastodowithitsgenus. 8

PAGE 19

Figure1.5: TheMobiusstrip. Figure1.6: TheTorus Thegenusofanorientablesurfacecanbesummarizedasthenumberofhandles thatareattached.Thetorusfamilyencapsulatesallsurfaceswithagenusgreater thanone,ormorethanonehandle.The n -torusisdenedanorientablesurfaceof genus n .The0-torusisthesphere.Thetoruscanbeusedtomodelnearlyanything intheworld.Simplytakeanobject,counthowmanyholesithas,andthatisthe orderoftorusthatmodelsthatobject. Figure1.7: Thethreeholedtorus,or3-torus. 1.4.2Graphs Agraphisdenedasacollectionofverticesthedotsinagraphandtheedges orlinesegmentswhichconnectthem.Thevertexsetofagraphisdenoted V G and 9

PAGE 20

theedgesetisexpressedas E G .Apathisdenedasasetofedgeswhichconnect thevertices u and v .Apathmaybelongorshort,andtherearemanygraphtheory problemswherethelengthofapathbetweentwoverticesisconsidered.Acycleof edgesisdenedasapathwhere u and v happentobethesamevertex,orinother wordsthepathbeginsandendsonthesamevertex.Agraphisconsideredembedded inasurfacewhenthegraphisdrawnwithnoedgesthatcross.Aplanegraphisone thatcanbeembeddedintheplane,andthesespecialgraphshavemanyattributes thatareuseful.Itisalsoofinteresttonotethattheplanecanbeinterchangedwith thesphere,sincethesphereistheonepointcompacticationoftheplane. TherstattributeofplanegraphsaretheirEulercharacteristic[29],whichis denedas: G =2 )]TJ/F15 11.9552 Tf 11.955 0 Td [(2 g = V )]TJ/F19 11.9552 Tf 11.955 0 Td [(E + F .1 where g isequaltothegenusofthesurfaceinwhichthegraphisattemptingto beembedded, V isequaltothenumberofverticesinthegraph, E thenumberof edges,and F thenumberoffaces.Afaceofagraphisconsideredtobeanempty regionencompassedbyacycleofedges.Forplanegraphs,thegenusiszero,therefore theEulerequationforplanegraphsbecomes: G =2= V )]TJ/F19 11.9552 Tf 11.955 0 Td [(E + F .2 Thisequationisextremelyusefulforprovingwhetherornotagraphmaybe embeddedintheplanebasedonthesimplestatisticsofthegraph.Agraphbecomes non-planewhentheEulercharacteristicdecreasesbelowtwo,orwhenthegenus increasesabovezero.Thismeansthatthegraphcannotbeembeddeduponthe sphereorplanebutneedsatleastthetorusasasurfaceinwhichtodrawitselfwith noedgecrossings.Inotherwords,asgraphsbecomemorecomplexoneneedstostart 10

PAGE 21

addinghandlestotheplaneorsphereinordertodrawthemwithoutcrossingedges. Thereareseveralotherwaystoprovethatagraphisnotembeddableonthe plane.Buttoreviewthem,thereaderrstneedsafewdenitions.Manydenitions forgraphtheorycanbesuppliedbyMoharandCarsten[26].Therstdenition isthatofacompletegraph.Agraph G onnverticesissaidtobecompletewhen everyvertexin G isadjacenttoeveryothervertex.Thistypeofgraphislabeled as K n where n isthenumberofvertices.Thenextdenitionisthatofasubgraph. Asubgraphofagraph H isdenedasagraphwhosevertexsetisasubsetofthe vertexsetof G ,andwhoseedgesareasubsetofthoseof G restrictedtothissubset ofvertices.Itissaidthatgraph G containsanothergraph H aslongas H oragraph isomorphictoHisasubgraphof G .Finally,asubdivisionofagraphisdenedasa newgraphobtainedfromthesubdivisionof G 'sedges.Inordertosubdivideanedge withendpoints u and v ,oneintroducedanewvertex w alongtheedgeandcreates twoedgesinplaceoftheoldone,anedge u;w e 1 andanedge w;v e 2 Figure1.8: Anedgeissubdividedintotwo. Kuratowski'stheorem[21]statesthatanitegraphisplanarifandonlyifitdoes notcontainasubgraphthatisasubdivisionof K 5 or K 3 ; 3 Agraphminorisanundirectedgraph H thatcanbeformedfromthegraph G bydeletingedgesandbycontractingedges.Whenanedgeisdeletedfromagraph, theverticesandtheirremainingedgesetsremain.Whenanedgeiscontracted,the twoendpointsoftheedgebecomeoneandtheremainingedgesfromtheendpoint thatisdeletedfromthegrapharenowassignedtothevertexthatremains. 11

PAGE 22

Figure1.9: Anedgeiscontracted. Figure1.10: ThePetersengraphhasaminorof K 5 butnosubdivisionof K 5 Wagner'stheorem[35]statesthatanygraphisplanaraslongasitdoesnot containaminorisomorphicto K 5 or K 3 ; 3 AtoroidalgraphadherestoEuler'stheoremEquation1.1.Usingthisequation, onecanobtainanupperboundonthenumberofedgesthatatoroidalgraphcan contain.Thisequationisobtainedbysubstitutingtheinequality: j F j 2 = 3 j E j .3 forthevariablerepresentingthenumberoffacesinEuler'sformula: 2 )]TJ/F15 11.9552 Tf 11.955 0 Td [(2 g V )]TJ/F19 11.9552 Tf 11.955 0 Td [(E +2 = 3 E .4 andthroughsomealgebrawehave: 6 )]TJ/F15 11.9552 Tf 11.955 0 Td [(6 g 3 V )]TJ/F15 11.9552 Tf 11.955 0 Td [(3 E +2 E .5 12

PAGE 23

6 )]TJ/F15 11.9552 Tf 11.955 0 Td [(6 g 3 V )]TJ/F19 11.9552 Tf 11.955 0 Td [(E .6 E 3 V )]TJ/F15 11.9552 Tf 11.955 0 Td [(6+6 g .7 Therefore,aninequalityforthenumberofedgesthatagraphmaycontainin ordertobeembeddedonthetorus,whichhasgenus g =1is: j E j 3 j V j .8 Wehavenotbeenabletondasuccinctalgorithmforcalculatingthenumber offaceswithinagraph,andsothisequationwasusefultohelpreducethenumber ofcandidaterandomlygeneratedgraphsforthisthesis.Ifasuccinctalgorithmfor calculatinggraphfaceshadbeenfound,theuseofEuler'sformulawouldhavebeen implementedinsteadofthisfunctionforthepurposesofverifyingwhetheragenerated graphistoroidalinnature. Aproper k -coloringofagraphisanassignmentofthecolors1through k tothe verticesofagraphsuchthatnotwoadjacentverticesareassignedthesamecolor. A k -chromaticgraphisthatwhichhasa k -coloringbutno k -1-coloring.Forany graphwitha k -coloring,thechromaticnumber ofthatgraphisequalto k .The torusisaspherewithonehandleattachedtoit.Foranygraphthatembedsonthe surfaceofthetorus,amaximumnumberofcolorsneededtocoloranysuchgraphcan bedeterminedbythetorus'Haewoodnumber.ThefunctionforHaewoodnumberis asfollows: H S = b 7+ p 49 )]TJ/F15 11.9552 Tf 11.956 0 Td [(24 S = 2 c ; .9 where S isdenedastheEulercharacteristic,whichweknowforthetorusis0. Therefore,wecancalculatetheHaewoodnumberofthetorusthusly: 13

PAGE 24

H torus = b 7+ p 49 )]TJ/F15 11.9552 Tf 11.955 0 Td [(24 = 2 c .10 H torus = b 7+ p 49 = 2 c .11 H torus = b 7+7 = 2 c = b 14 = 2 c = b 7 c =7.12 Thechromaticnumber ofacompletegraph K n isequalto n ,thenumberof verticesthegraphcontains.FromtheHeawoodnumber[16]ofthetorusonecan concludethatthemaximumcompletegraphthatcanbeembeddedonthetorusis K 7 .TheFourColorTheorem[30]statesthatanygraphembeddedontheplanecan becoloredwithatmostfourcolors. Hadwiger'sConjecture[13]statesthatifallpropercoloringsofanundirected graph G use k ormorecolors,thenonecannd k disjointconnectedsubgraphsof G suchthateachsubgraphisconnectedbyanedgetoeachothersubgraph.Contractingtheedgeswithineachofthesesubgraphssuchthateachsubgraphcollapsestoa singlevertexproducesacompletegraph K k on k verticesasaminorof G .Thiswas provedforthe k =5casebyKlausWagnerin1937[35]byshowingthatthecasewas equivalenttoTheFourColorTheorem,whichwasprovenin1997.The k =6case wasprovenbyRobertson,Seymour,andThomasin1993[31].Finally,onlygraphs containingaminorisomorphicto K 7 are7-chromaticonthetorus,asprovedbyG. Dirac[8]. AnoteabouttheconrmationofHadwiger'sConjecturefor k =5isthatnowwe cansaythatanytoroidalgraphnotcontaining K 5 asaminorislessthan5-colorable. Thisiswhatallowsustosaylaterthatifagraphonlycontains K 3 ; 3 asaminorrather 14

PAGE 25

Figure1.11: AvisualizationofHadwiger'sConjecturefor k =4 thananyofthecompletegraphs,thenthegraphis4-colorable.Thisremovesalarge numberofgraphsfromtheeldofthisconjecture. BohmeandKostochka[5]showedthatforanygraphembeddedinthetorus,the graphcannotcontainaminorisomorphictotwodisjointcopiesof K 5 [5].Thiscan beeasilyextendedtoinclude K 6 and K 7 .Itshouldalsobesaidthatafterembedding anyofthetoroidalcompletegraphsintothetorus,thateveryfaceofthosecomplete graphsislocallyplanar,andthuseverygraphembeddablewithinthosefacesmust beplanaraswell. Itwasshownthatforeverytrianglefreegraphembeddedonthetorusthatthe graphcanbecoloredwithatmostfourcolorsbyKronkandWhite[19].Thisremoves anotherwideswathofgraphsfromthepurviewofthisconjectureandallowsusto focusonthosegraphsthatcontainsubgraphsandminorsisomorphictothetoroidal completegraphs.Trianglefreegraphsaretheirownsubjectinthespaceoftoroidal graphcoloringandhashadmanypaperspublishedonthesubject[3,6,9,18,32,36]. ItwasshownbyAlbertson[1]thattheonlysix-chromaticgraphonthetorus besidesthosecontaininga K 6 wastheuniquegraph J producedbythatpaper,which 15

PAGE 26

containedasubdivisionof K 6 .Thisgraphadherestotheconjecturetackledbythis problem.Meaningthatacoloringexistssuchthatthesamefourcolorsareused exceptingtwovertices. Figure1.12: The J graphmostlyfourcoloredexceptingtwovertices. 1.4.3NewDenitions Inordertofurtherunderstandtheproblempresentedinthispaper,wehavecreate newdenitionsregardingcertainverticesandpathswithinsubdivisions. Denition1.4.1 MajorVertex Supposegraph G containsaminorisomorphicto acompletegraph K .Thesetof majorvertices M V isasubsetoftheverticesof G where M V isthevertexsetof K Manyverticesmaybelabeledasmajorinagraphcontainingmanydierent variationsofcompletegraphsasminorsorsubgraphs. Denition1.4.2 MinorVertex Supposegraph G containsaminorisomorphicto acompletegraph K .A minorvertex isonenotcontainedin M V Manyverticesmaybelabeledasminorinagraphcontainingmanydierent variationsofcompletegraphsasminorsorsubgraphs.Figure1.13colorstheminor verticesinagraycolor. 16

PAGE 27

Figure1.13: Themajorverticesofthe J graph,coloredbytheirrespectivecolors fromthegraph'spropercoloring. Denition1.4.3 MajorEdge Supposegraph G containsaminorisomorphictoa completegraph K .Thesetof majoredges M E isasubsetoftheedgesof G where M E istheedgesetof K Manyedgescanbelabeledasmajoredgesinagraphcontainingmanydierent variationsofcompletegraphsasminorsorsubgraphs. Figure1.14: Themajoredgesofthe J graph.Theblueedgesinthisgraphic representdirectconnectionsbetweenthemajorvertices,andtheothercolorededges representpathsconnectingthosemajorverticeswhicharenotdirectlyconnected. Denition1.4.4 MinorEdge Supposegraph G containsaminorisomorphictoa completegraph K .A minoredge isonenotcontainedin M E 17

PAGE 28

InFigure1.14theminoredgesarecoloredinblack.Fromthesemajoredges andverticeswecanidentifywithprecisionthecompletesubdivisionwhichexistsin complexgraphs.Laterinthispaperwewillbediscussinggraphsinrelationtotheir majorandminorvertices. Denition1.4.5 VertexIsolation Avertex v isconsidered isolated whenallof it'sadjacentedgeshavebeenremovedfromthegraphcontaining v 18

PAGE 29

2.ConstructingGraphs 2.1GraphGeneration Theproblemapproachedbythisthesisrequiresthattheinputgraphsbetoroidal innature.ThereareseveralrulesthattoroidalgraphsmustfollowdetailedinNeufeld andMyrvold'sPracticalToroidalityTesting[28]. 2.2TheFirstRule Therstruleistheupperboundonedges,discussedinthesection1.4.2under equation1.8. Thegoalforgraphproductionwastousearandomgraphgeneratorthatproduces graphsbasedonthenumberofverticesandprobabilityofanedgeexistingbetween anytwovertices.Duringourresearch,wediscoveredaneasyequationtodetermine themaximumpercentageofprobabilitybetweenedgesforanytoroidalgraphinrelationtoitsvertices.Thisequationwasdiscoveredbyexaminingthefactthatthe percentageinthegeneratorwasappliedeachtimetoacombinationofedges.This washelpfulinavoidinggeneratinggraphsthatwerenon-toroidaloverandover.The numberofcombinationsinanyarrayofverticesisequalto: n n )]TJ/F15 11.9552 Tf 11.955 0 Td [(1 = 2.1 Whenthisnumberismultipliedbythepercentagechancethatanedgeexists betweentwovertices,representedby x ,andthisproductissubstitutedintheequation 1.8thefollowingisgained: j V j j V j)]TJ/F15 11.9552 Tf 17.933 0 Td [(1 x= 2 3 j V j .2 whichisreducedto j V j j V j)]TJ/F15 11.9552 Tf 17.933 0 Td [(1 x 6 j V j .3 19

PAGE 30

thento x 6 = j V j)]TJ/F15 11.9552 Tf 17.932 0 Td [(1.4 Usingthisequationwewereabletoproducegraphsthatcontinuouslymetthe equation1.8constraint,andsimplyreducingthispercentagechancebytwopercent wasenoughtogaingeneratedgraphsthatttheproblemfortherstruleoftoroidal graphs.However,itwasdiscoveredwhenintegratingthetoroidalembeddinglibrary thatthesegraphswereusuallynottoroidalinnature. 2.3TheSecondRule Thesecondruleisthatthegraphmaycontaintoomanyfaces,denedbythe followingequation: j F j > j V j)-222(j E j .5 ThisrulecanbeeasilyexplainedusingtheEulerEquationequation1.1.For thetorus,whichhasgenus g =1Euler'sEquationbecomes 0= V )]TJ/F19 11.9552 Tf 11.956 0 Td [(E + F .6 2.4TheThirdRule Thethirdisedgeoveruse,whereinanyedgeappearsinmorethantwofacesof anembedding.Forthetorus,itisonlyallowedthatanedgeexistsasaboundaryof exactlytwofaces.Insomegraphs,asdisplayedinthegure2.1abelow,thisrulecan bebroken. 20

PAGE 31

2.5TheFourthRule Andthefourthandlastisthepresenceofadwarfrimisforbidden.Inotherwords therecannotbeacyclicsetofconstraintsofsizelessthanthedegreeofavertexv. Figure2.1: CombinatorialThumbtacks. Inordertoenforcetheserulesourapplicationrequiredatoroidalembedding algorithminordertoensurethatthegraphsbeinggeneratedweretoroidal.Withhelp fromJiahuaYu,anembeddinglibrarywasutilizedinverifyingthegraphsgenerated weremadetoroidal[37]. Toconstructgraphsthattthisproblem,werstusedarandomgraphgenerator providedbytheNetworkXpackageinpython,andlatertherandomgraphgenerator suppliedbytheboostgraphinglibraryinC++.Thesegeneratorsproducegraphs accordingtheErd}osandRenyimethod[10]onaspeciednumberofverticeswith edgesbetweenthemoccurringaccordingtoaspeciedpercentage p .Thisgenerator sometimesproducesmulti-edges,andloops,whichthisthesisisnotconcernedwith. Partofthegraphgenerationportionofthesoftwareistogetridoftheseloopsand multi-edges.Aresultingpartofreducingthesegraphswereisolatededges,orthose withnoedges.Thisalsobroketherulesoftheembeddinglibraryandsohadtobe removedfromthegraph.Wewereabletoproduceover70thousandtoroidalgraphs withthisgenerator.Thisnumbercontinuestoincreaseastimepasses. 21

PAGE 32

3.TestingGraphs Usingtheutilitydescribedinthepreviouschapter,wewereabletogenerate graphsrelevanttotheproblemathandandtestthem.Inthischaptertheprocedure usedtotestthegraphsforcertaincharacteristicsisdescribedindepth. 3.1AlgorithmMotivation Recallthedenitionscreatedattheendofthebasictheorysectionofthispaper, repeatedhere: Denition3.1.1 MajorVertex Supposegraph G containsaminorisomorphicto acompletegraph K .Thesetof majorvertices M V isasubsetoftheverticesof G where M V isthevertexsetof K Manyverticesmaybelabeledasmajorinagraphcontainingmanydierent variationsofcompletegraphsasminorsorsubgraphs. Denition3.1.2 MajorEdge Supposegraph G containsaminorisomorphictoa completegraph K .Thesetof majoredges M E isasubsetoftheedgesof G where M E istheedgesetof K Manyedgescanbelabeledasmajoredgesinagraphcontainingmanydierent variationsofcompletegraphsasminorsorsubgraphs. Proposition3.1.1. Inanyembeddedgraph,anyvertexboundbyafaceofmajor edgescannotbeadjacenttomajorverticesthatdonotlieonthefaceboundaries. Reasoning:Consideragraph G whichhasavertex v whichresidesinaface boundbymajorvertices a b c .Anothermajorvertex d liesoutsidetheface a b c .If v isadjacentto d thegraphisnolongerembeddedonthesurfaceduetothedenition ofembedded-ness,thatagraphexistsonasurfaceembeddedaslongasnoedge crossingsexist.Thiscaneasilybeextendedtofacesofeverysize. 22

PAGE 33

Proposition3.1.2. Whenoneisolatesasinglemajorvertexonatoroidalgraph containing K 5 ,thegraphbecomes4-colorable. Reasoning:Consideragraph G embeddedonthetoruswithaminorisomorphic to K 5 asit'smaximumclique.Fiveverticesarelabeledasmajorvertices,andtheir associatedmajoredgesarelabeled. Figure3.1: K 5 SubdivisionGraph. Amajorvertex v isisolatedfromthegraphbydeletingitsadjacentedges.Dueto Proposition3.1.1theverticeswithinthefacesthatwereboundbyedgescontaining v cannotbeadjacenttoeachother,thereforethe K 5 isbrokenandnoothersubgraph isomorphictothe K 5 mayexist.TheonlyotherKuratowskisubgraphwhichmay existalongwiththe K 5 isthe K 3 ; 3 whichwasshowntobe4-colorablebyHadwiger's conjecturebeingprovenforthe k =5case. BohmeandKostochkashowedthatforanygraphembeddedinthetorus,the graphcannotcontainaminorisomorphictotwodisjointcopiesof K 5 [5]. AlongwiththesupportfromBohmeandKostochka,weseethatthelemmais conrmedforallgraphsonthetoruscontainingaminorisomorphicto K 5 ,including thosegraphswhichcontainminorsisomorphicto K 6 and K 7 Proposition3.1.3. Anygraphembeddedonthetoruscontainingaminorisomorphic to K 5 maybecoloredwithuptovecolors,whereonlyonevertexisassignedthecolor 23

PAGE 34

Figure3.2: MajorVertexIsolation 5. Reasoning:FromProposition3.1.2weunderstandthatisolatingoneofthemajor verticesofagraph G whichcontainsaminorisomorphicto K 5 is4-colorable.Thereforethisgraph G=v canbecoloredwithfourcolors.Whentheremovedvertex v is restoredtothegraph,thegraphlosesplanarityandnowcontainsaminorisomorphic to K 5 ,thereforeisforcedtoutilizevecolors.Thefthcolormaybeassignedtothe recentlyrestoredvertex. Proposition3.1.4. Whenoneisolatesamajoredge,includingthetwomajorendpointsofagraphembeddedonthetoruswhichcontainsaminorisomorphicto K 6 thegraphbecomes4-colorable. Reasoning:ConsideragraphGembeddedonthetoruswithaminorisomorphic to K 6 asit'smaximumclique.Sixverticesarelabeledasmajor,andtheirassociated majoredgesarelabeled. Amajoredge,alongwithitsassociatedmajorvertices,aredeletedfromthe graph.FromProposition3.1.1weunderstandthatverticeswithinthefacesthatwere boundbythepreviouslydeletedmajoredgecannotbeadjacenttothemajorvertices thatarenotapartofthosefaces,andthereforetheremaynotexista K 6 or K 5 24

PAGE 35

AgainthankstoBohmeandKostochkaweknowthattherecannotbetwodisjoint copiesof K 5 or K 6 mayexistonthetorusatthesametime.Therefore,thisremaining graphis4-colorable. Proposition3.1.5. Anygraphembeddedonthetoruscontainingaminorisomorphic to K 6 maybecoloredwithuptosixcolors,whereonlytwoverticesareassignedthe colors5and6. Reasoning:Fromproposition3.1.4weknowthatthegraphafterdeletingamajor edgeanditsassociatedmajorverticesis4-colorable.Withtherestorationofthe previouslydeletededgewerestorethe K 6 andthereforeneedsixcolorstomaintain apropercoloring.Byassigningthecolors5and6tothenewlyrestoredendpoints oftheedgewemaintainapropercoloring. Proposition3.1.6. Whenoneisolatesatriangularfacecomposedofmajoredgesfor agraphembeddedonthetoruscontainingaminorisomorphicto K 7 ,theremaining graphis4-colorable. Reasoning:ConsideragraphGembeddedonthetoruswithaminorisomorphicto K 7 asit'smaximumclique.Sevenverticesarelabeledasmajor,andtheirassociated majoredgesarelabeled. Afaceboundedbymajoredgesisisolatedfromtherestofthegraph.Dueto BohmeandKostochkatheremaynotexistadisjointcopyof K 6 or K 5 otherthanthe copiescontainedassubgraphstotheoriginal K 7 .Thereforeintheremaininggraph thereexisttwodisjointcopiesofcompletegraphs.Oneisoforderfourandtheother oforderthree.Theremaininggraphis4-colorable. Proposition3.1.7. Anygraphembeddedonthetoruscontainingaminorisomorphic to K 7 maybecoloredwithuptosevencolors,whereonlythreeverticesareassigned thecolors5,6,and7. 25

PAGE 36

Reasoning:FromProposition3.1.6weknowthatthegraphafterthereduction describedinthelemmais4-colorable.Boththegraphcontainingthesubgraphof K 4 andthegraphcontainingthe K 3 maybecoloredwith4colors.Withtherestoration oftheedgesconnectingthe K 4 tothe K 3 ,thecolors5,6,and7maybeassignedto themajorverticesofthegraphcontainingthe K 3 .Iftheedgesofthissecondgraph aresubdivided,onecanseethatthefaceboundbytheedgesexternaltoeachedge ofthe K 3 isaplane,andthereforetheverticesalongthesubdividededgescanbe coloredusingthefourcolorsusedtocolortherestofthegraph. Fromthepreviouslyexplainedsteps,amethodforcoloringeverygraphembeddableonthetorusisdescribed,whichsupportsAlbertson'sConjecture[1]. 26

PAGE 37

3.2TheAlgorithm ThebasicalgorithmusedtotesttheinputgraphsfromtheConstructingGraphs chapterisasfollows: Algorithm1: BeginTest input :Aconrmedtoroidalgraph output :ApropercoloringofthegraphwhichtsAlbertson'sConjecture boyer myrvold planarity test ; if planar then continue ; if K 3 ; 3 then continue ; if K 5 then Mantey test; TheBoyerandMyrvoldplanaritytesttakesanygraphasanadjacencylistand returnswhetherthegraphisplanar.Ifthegraphisnotplanar,thenthetestreturns thekuratowskisubgraphwhichbreakstheplanarityoftheinputgraph.Theplanar and K 3 ; 3 casesareignoredduetotheirfour-colorablenatures.Thereaderisreminded thatthe K 3 ; 3 minorcanbeignoredduetotheHadwigerConjecturebeingprovenin the k =5case.Thismeansthatanygraphnotcontaininga K 5 orminormaybe four-colored.The Mantey test algorithmisshownnext. 27

PAGE 38

Algorithm2: Mantey test input :Aconrmedtoroidalgraphcontaininga K 5 minor,isolationnumber output :ApropercoloringofthegraphwhichtsAlbertson'sConjecture identifythemajorverticesofthe K 5 subgraph; switch iteration do case 1 List =eachmajorvertex; case 2 List> =eachcombinationoftwomajor vertices; case 3 List> =eachcombinationof threemajorvertices; for List do isolateandtestplanarity; if planar then returnColor ; if K 3 ; 3 then returnColor ; if K 5 then if iteration !=3 then Mantey test iteration +1; throwerror; IdentifyingthemajorverticesDenition1.13ofthesubgraphreturnedbythe BoyerandMyrvoldplanaritytestrequiredalterationofthefunctioncontainingthe logictoidentifytheKuratowskisubgraphofthenon-planargraph.Thefunction contractstheedgesofthegraphuntilitndstheremaininggraphisisomorphicto 28

PAGE 39

K 5 or K 3 ; 3 .Duringthesecontractionswecapturedtheverticesthatwereconsumed bytheprocessandperformedadierenceonthesetofverticesthatwereconsumed withthoseoftheoverallextractedKuratowskisubgraph.Inthiswaywewereable toextractthemajorverticesofthegraph.Ifonekeepstrackofwhichedgeswere contracted,oneisabletodiscoverthemajoredgesofthegraphaswell. Allthatisleftistocolorthegraphwhena K 3 ; 3 orplanargraphhasbeenfound afteranisolationoperation.Thatprocessisdetailedhere. Algorithm3: Color input :Aconrmedtoroidalgraphcontaininga K 5 minorwithanumberof majorverticesisolated,alistofremovededges,andalistofisolated vertices output :ApropercoloringofthegraphwhichtsAlbertson'sConjecture colortheinputgraphusingabacktrackingalgorithm; for eachisolatedvertex do assignthecolor4+indexofthevertexinthelist; restoretheremovededgesofthegraph; testthepropercoloringofthegraph; if proper then return coloring ; throwerror ; 3.3InitialResults Wehaveincludedanexcerptfromourinitialresultstofurtherexplainthisprocess, beforeanythingislogged,thegraphinquestionhasbeenveriedastoroidal. GraphEdges:,3,9,2,8,8,9,4,9,8,4, 3,7,5,7,8,7,5,4,8,6,7,9,9,7 ,2,9,7 29

PAGE 40

TestingforPlanarity Inputgraphisnotplanar TestingforKuratowskiSubgraph ... ThegraphcontainsakuratowskisubgraphofK5 Figure3.3: OriginalGraph Hereweknowthatthegraphinquestion,showninFigure3.3,hasasubgraphof K 5 accordingtoBoyerandMyrvold. TestingforKuratowskiSubgraph EdgesintheKuratowskisubgraph: ,3,2,8,8,9,4,3,7,7,4,6,9,7,7 Isakuratowskisubgraph?Yes EdgeContracted:,0 EdgeContracted:,0 30

PAGE 41

EdgeContracted:,0 EdgeContracted:,9 K5MajorVertices:3,0,9,4,7 31

PAGE 42

Figure3.4: EdgeContracted:,0 Figure3.5: EdgeContracted:,0 Figure3.6: EdgeContracted:,0 Figure3.7: EdgeContracted:,9 Figure3.8: MajorVertices Atthispointinthealgorithmwehavediscoveredthemajorverticesofthegraph thatmakeupthe K 5 subgraph.InFigures3.4,3.5,3.6,and3.7wecanseetheedge contractionsdetailedinthelogastheyprogress.Finally,ingure3.8wecanseethe majorverticeshighlightedintheremaininggraph.Thegraphisrunthroughmany isolationsuntilavalidoneisfound,thoseiterationshavebeenomittedfromthis excerpt. 32

PAGE 43

IsolatingVertex:2 IsolatingVertex:3 TwoVerticesIsolated,RetestingPlanarity: ,9,8,8,9,8,4,7,5,7,5,7,9,7,9 Inputgraphisnotplanar TestingforKuratowskiSubgraph EdgesintheKuratowskisubgraph:,8,8,9,4,5,7,5,7,9,7,9 Isakuratowskisubgraph?Yes. EdgeContracted:,5 EdgeContracted:,6 ThegraphcontainsakuratowskisubgraphofK3,3 Thegraphistherefore4-colorableaccordingtoHadwiger Thegraphwassuccessfullycolored! Vertex:0Color:1 Vertex:1Color:1 Vertex:2Color:5 Vertex:3Color:6 Vertex:4Color:2 Vertex:5Color:2 Vertex:6Color:1 Vertex:7Color:3 Vertex:8Color:2 Vertex:9Color:4 Finallythegraphiscolored,asseeningure3.9 Initially,ouralgorithmdidnottesttheisolationofeachmajorvertex.Theinitialresultsthatfollowdetailastepinourprocessofdevelopingthenalalgorithm includedinthispaper.Therstalgorithmonlytestedtherstvertexinthelistof 33

PAGE 44

Figure3.9: FinalColoring 34

PAGE 45

majorvertices.Ifa K 5 wasstillfoundaftertheplanaritytest,thealgorithmmoved ontoisolateasecondvertex,andsoon.TheinitialresultsaredisplayedinTable3.3 fromrunningtherstdraftalgorithmovernight. Table3.1: Theresultsoftherstproduction. NumberofGraphs Percentage TotalGraphs 4,448,954 100% PlanarGraphs 2 negligible Graphswith K 3 ; 3 403,837 89.95% GraphsPlanarafter1 st isolation 20 negligible Graphswith K 3 ; 3 after1 st isolation 35,557 7.92% GraphsPlanarafter2 nd isolation 80 negligible Graphswith K 3 ; 3 after2 nd isolation 7,285 1.62% Graphswith K 5 after2 nd isolation 2,173 0.48% Aftertestingtheplanarityoftheinputgraphsonceamajorvertexhasbeenisolated,alargepercentageofthegraphsbecomeeitherplanarorcontainasubgraph isomorphicto K 3 ; 3 .Theinterestingcaseiswhenoneisolatesavertexofthe K 5 subgraphandisleftwithagraphthatstillcontainsa K 5 subgraphorminor.Thiscould meanthattheoriginalhypothesis,thatagraphonthetoruscanbecoloredwith mostlyfourcolorsexceptinguptothreeverticesisinjeopardy.Thiscaseneededto beanalyzedfurthertoascertainthevalidityoftheresults.Itcouldbethata K 6 or K 7 subgraphhasbeenidentied,whichrequiresadierentmeansofanalysis. Theseresultstellaninterestingstory.Thereareseveralgraphsforwhicha vertexofthe K 5 wasisolatedanda K 5 subgraphremained.Asecondaryisolation wasperformedandmajorityofthesecaseswereresolvedtoagraphcontaininga K 3 ; 3 35

PAGE 46

subgraphoraplanargraph.However,therearesomecaseswherea K 5 subgraph stillexistswithinthegraph.Thereareseveralexplanationsforthisbehaviorthat neededtobeaddressed.Themajoritycasecouldbeexplainedasadiscoveryofa K 6 subgraph,duetothefactthattheBoyerandMyrvoldplanarityfunctiononlytells uswhetherthereisaKuratowskisubgraph,andouralterationsonlytelltheanalyst whetherthatgraphisa K 5 ora K 3 ; 3 .Thelattercasecouldalsobeexplainedasa K 7 forthesamereason,butwedidnotknowforsureuntilthefunctionwasaltered todiscoverthesetwocases. 3.4Improvingresults Theinitialresultsoftheexperimentbroughtintotheforegroundproblemsin ourmethodology.Eachoftheseissuesneededtoberesolvedbeforecontinuingto producegraphsandcolorthem.Firstly,weneededawaytoidentifywhetherthe inputgraphcontaineda K 6 ora K 7 incaseswherea K 5 minorwasidentiedaftera vertexisolation.Thefactthattherstalgorithmonlytestedtheisolationofasingle majorvertexunveiledanimportantruletocoloringtoroidalgraphs.Whichmajor vertexyouisolatematters.Theremaybemultipleconjoinedminorsof K 5 withinthe graph,butisolatingaspecicmajorvertexsharedbybothmaybreaktheplanarity, asdiscussedinsection3.5laterinthispaper. Fromthisrevelation,wedecidedtoiteratethroughallidentiedmajorvertices andisolateeachoneinturn,restoringtheedgeswedeletedintheprocessbefore movingontothenextmajorvertex.Thisimprovedresultssubstantially,andwe decidedthesamemustbedoneforthe K 6 and K 7 cases.Forthe K 6 case,weneeded toproduceallcombinationsoftwoverticesinthelistofKuratowskivertices.For the K 7 ,weneededtoproduceallcombinationsofthreevertices.Thesechangesare reectedinthepreviouslyreviewedalgorithms. 3.5The M graph 36

PAGE 47

ThereisaninterestingsituationdetailedinGagarin,Labelle,andLeroux'spaper onthestructureof K 3 ; 3 graphs[12].ThegraphMdetailedinthispaperandshow belowisacasewheretheisolationofavertexofa K 5 subgraphresultsinthegraph stillcontaininga K 5 subgraph. Figure3.10: The M graph. Identifyingthemajorverticesofoneoftheconjoined K 5 minorsisshownbelow ingure3.11withmajorverticesshowninred. Figure3.11: The M graphwithmajorverticesidentiedinred. Fromherewecanseeiftheanalystisolatedthecentervertexofoneofthese K 5 minors,thegraphwouldstillcontaina K 5 minor.However,ifoneisolatedthe vertexidentiedinblueingure3.11,thenthegraphbecomesplanar,andthus four-colorableasshowningure3.12below. Finally,byincreasingthecolorindexoftheisolatedvertexandrestoringthe edges,onecanseeapropercoloringofthe M graphwithonlyonevertexhavingthe 37

PAGE 48

Figure3.12: ThePlanarafteroneisolation M graph. 5thcolor. Figure3.13: Theproperlycolored M graph. 38

PAGE 49

4.AnalysisandResults Collectedbelowaretheresultsfromseveralexperimentswithvertexcountand edgeprobability. Table4.1: Theresultsofthe7vertexproduction. 7Vertices,98%Probability #ofGraphs Percentage #Colored TotalGraphs 7771 100% PlanarGraphs 0 0% Graphswith K 3 ; 3 3794 48.82% GraphsPlanarafter1 st isolation 0 0% Graphswith K 3 ; 3 after1 st isolation 644 8.29% 547 GraphsPlanarafter2 nd isolation 86 1.11% Graphswith K 3 ; 3 after2 nd isolation 0 0% Graphswith K 5 after2 nd isolation 0 0% GraphsPlanarafter3 rd isolation 0 0% Graphswith K 3 ; 3 after3 rd isolation 0 0% Graphswith K 5 after3 rd isolation 0 0% NonToroidalgraphsGenerated 3247 41.78% 39

PAGE 50

Table4.2: Theresultsofthe8vertexproduction. 8Vertices,83.7%Probability #ofGraphs Percentage #Colored TotalGraphs 5571 100% PlanarGraphs 0 0% Graphswith K 3 ; 3 3386 60.78% GraphsPlanarafter1 st isolation 0 0% Graphswith K 3 ; 3 after1 st isolation 855 15.35% 774 GraphsPlanarafter2 nd isolation 58 1.04% Graphswith K 3 ; 3 after2 nd isolation 3 0.05% 3 Graphswith K 5 after2 nd isolation 0 0% GraphsPlanarafter3 rd isolation 0 0% Graphswith K 3 ; 3 after3 rd isolation 0 0% Graphswith K 5 after3 rd isolation 0 0% NonToroidalgraphsGenerated 1269 22.78% 40

PAGE 51

Table4.3: Theresultsofthe9vertexproduction. 9Vertices,73%Probability #ofGraphs Percentage #Colored TotalGraphs 6972 100% PlanarGraphs 0 0% Graphswith K 3 ; 3 4198 60.20% GraphswithPlanarafter1 st isolation 0 0% Graphswith K 3 ; 3 after1 st isolation 1370 19.65% 547 GraphsPlanarafter2 nd isolation 50 0.72% Graphswith K 3 ; 3 after2 nd isolation 20 0.29% 17 Graphswith K 5 after2 nd isolation 0 0% GraphsPlanarafter3 rd isolation 1 0.01% Graphswith K 3 ; 3 after3 rd isolation 0 0% Graphswith K 5 after3 rd isolation 0 0% NonToroidalgraphsGenerated 399 5.72% 41

PAGE 52

Table4.4: Theresultsofthe10vertexproduction. 10Vertices,64%Probability #ofGraphs Percentage #Colored TotalGraphs 5787 100% PlanarGraphs 0 0% Graphswith K 3 ; 3 3829 67.25% GraphsPlanarafter1 st isolation 0 0% Graphswith K 3 ; 3 after1 st isolation 1440 24.88% 1349 GraphsPlanarafter2 nd isolation 26 0.45% Graphswith K 3 ; 3 after2 nd isolation 31 0.54% 26 Graphswith K 5 after2 nd isolation 0 0% GraphsPlanarafter3 rd isolation 0 0% Graphswith K 3 ; 3 after3 rd isolation 0 0% Graphswith K 5 after3 rd isolation 0 0% NonToroidalgraphsGenerated 398 6.88% 42

PAGE 53

Table4.5: Theresultsofthe11vertexproduction. 11Vertices,58%Probability #ofGraphs Percentage #Colored TotalGraphs 16460 100% PlanarGraphs 0 0% Graphswith K 3 ; 3 9357 56.85% GraphswithPlanarafter1 st isolation 0 0% Graphswith K 3 ; 3 after1 st isolation 3265 19.84% 3114 GraphsPlanarafter2 nd isolation 50 0.30% Graphswith K 3 ; 3 after2 nd isolation 53 0.32% 48 Graphswith K 5 after2 nd isolation 0 0% GraphsPlanarafter3 rd isolation 3 0.02% Graphswith K 3 ; 3 after3 rd isolation 0 0% Graphswith K 5 after3 rd isolation 0 0% NonToroidalgraphsGenerated 3732 22.67% 43

PAGE 54

Table4.6: Theresultsofthe12vertexproduction. 12Vertices,52.5%Probability #ofGraphs Percentage #Colored TotalGraphs 10466 100% PlanarGraphs 0 0% Graphswith K 3 ; 3 4725 45.15% GraphswithPlanarafter1 st isolation 0 0% Graphswith K 3 ; 3 after1 st isolation 1402 13.40% 1358 GraphsPlanarafter2 nd isolation 14 0.13% Graphswith K 3 ; 3 after2 nd isolation 23 0.22% 17 Graphswith K 5 after2 nd isolation 1 0.01% GraphsPlanarafter3 rd isolation 2 0.02% Graphswith K 3 ; 3 after3 rd isolation 1 0.01% 1 Graphswith K 5 after3 rd isolation 0 0% NonToroidalgraphsGenerated 4272 40.82% 44

PAGE 55

Table4.7: Theresultsofthe13vertexproduction. 13Vertices,48%Probability #ofGraphs Percentage #Colored TotalGraphs 8370 100% PlanarGraphs 0 0% Graphswith K 3 ; 3 3226 38.54% GraphswithPlanarafter1 st isolation 0 0% Graphswith K 3 ; 3 after1 st isolation 853 10.19% 830 GraphsPlanarafter2 nd isolation 10 0.12% Graphswith K 3 ; 3 after2 nd isolation 7 0.08% 7 Graphswith K 5 after2 nd isolation 1 0.01% GraphsPlanarafter3 rd isolation 1 0.01% Graphswith K 3 ; 3 after3 rd isolation 0 0% Graphswith K 5 after3 rd isolation 0 0% NonToroidalgraphsGenerated 4272 51.04% 45

PAGE 56

Table4.8: Theresultsofthe14vertexproductionwith40%Edgeprobability. 14Vertices,40%Probability #ofGraphs Percentage #Colored TotalGraphs 4037 100% PlanarGraphs 0 0% Graphswith K 3 ; 3 1266 31.36% GraphswithPlanarafter1 st isolation 0 0% Graphswith K 3 ; 3 after1 st isolation 235 5.82% 234 GraphsPlanarafter2 nd isolation 1 0.02% Graphswith K 3 ; 3 after2 nd isolation 0 0% Graphswith K 5 after2 nd isolation 0 0% GraphsPlanarafter3 rd isolation 0 0% Graphswith K 3 ; 3 after3 rd isolation 0 0% Graphswith K 5 after3 rd isolation 0 0% NonToroidalgraphsGenerated 2535 62.79% 46

PAGE 57

Table4.9: Theresultsofthe14vertexproductionwith35%Edgeprobability. 14Vertices,35%Probability #ofGraphs Percentage #Colored TotalGraphs 4009 100% PlanarGraphs 0 0% Graphswith K 3 ; 3 3510 87.55% GraphsPlanarafter1 st isolation 0 0% Graphswith K 3 ; 3 after1 st isolation 496 12.37% 491 GraphsPlanarafter2 nd isolation 3 0.07% Graphswith K 3 ; 3 after2 nd isolation 0 0% Graphswith K 5 after2 nd isolation 0 0% GraphsPlanarafter3 rd isolation 0 0% Graphswith K 3 ; 3 after3 rd isolation 0 0% Graphswith K 5 after3 rd isolation 0 0% NonToroidalgraphsGenerated 0 0.0% 47

PAGE 58

Table4.10: Theresultsofthe15vertexproduction. 15Vertices,30%Probability #ofGraphs Percentage #Colored TotalGraphs 1201 100% PlanarGraphs 0 0% Graphswith K 3 ; 3 928 77.27% GraphswithPlanarafter1 st isolation 0 0% Graphswith K 3 ; 3 after1 st isolation 92 7.66% 92 GraphsPlanarafter2 nd isolation 0 0% Graphswith K 3 ; 3 after2 nd isolation 0 0% Graphswith K 5 after2 nd isolation 0 0% GraphsPlanarafter3 rd isolation 0 0% Graphswith K 3 ; 3 after3 rd isolation 0 0% Graphswith K 5 after3 rd isolation 0 0% NonToroidalgraphsGenerated 181 15.07% 48

PAGE 59

5.FurtherResearchandConclusions FromhereAlbertson'sconjecture,withtheconstraintregardingtheverticesof thecompletesubgraph,canbegeneralizedforgraphsembeddedonsurfacesofhigher genus. Thisconjecturewouldmostlikelytaketheformof"Thegraphsembeddedon then-torusmaybecoloredwithmostlyfourcolors,exceptinguptotheorderofthe highestembeddablecompletegraphlessfourvertices." Considerationsforthisconjectureincludethefollowingquestions. Whatcanhappentothechromaticnumberwhentherearetwodisjointcopies ofacompletegraphonthesame2-toroidalgraph? Hadwiger'shasnotbeenprovenforcasesgreaterthanve.Whatsix-chromatic graphsexistonthe2-torusthatdonotcontain K 6 ? WiththehelpofDr.WilliamKocay,workcontinuesonagraphicalrepresentationofthesegraphsbeingincludedintheutilityproducedbythisthesis.Withthe inclusionofDr.Kocay'scode,theutilitybecomesusableonlyinaresearchcapacity. Currentworkalsoincludeshuntingdowncoloringsforthosegraphsthatwerenot coloredbythisalgorithm.CurrentlyevidencepointstoabuginouralteredBoyer andMyrvoldplanaritytest,missingthosegraphswhichhave K 6 minorswithinthem. Futureworkontheutilitycouldincludetheadditionoftoolstomanipulate thetoroidaldrawingsproducedbyDr.Kocay'sgraphicalembeddingalgorithms,a 3Drepresentationofsaidgraphicalembeddings,andtheinclusionofalgorithmsto produceandtestthenextleveltorus. ThedataproducedbythisthesiscertainlysupportstheconjecturemadebyDr. Albertson,howeverthereaderisremindedthatsincenoformalproofisincludedin thisthesis,theconjectureremainsavailableforstudyandamoreformalproof.Itis theopinionoftheauthorthattheconjectureholdstrue,andthattheconjecturemay 49

PAGE 60

befurtherreducedtosaythattheverticesnecessitatingtheextracolorsmustlieon thecompleteminorofthetoroidalgraphandthenumberofextracolorsneededis theordertothecompleteminorlessfour. 50

PAGE 61

6.AppendixA Thisappendixcontainsthecodefromouralgorithmtodiscovergraphswhichare toroidalandtoattempttocolorthem.Thisisasubsetofthecodepertainingtothis thesis,theentirecodeandloglesshallbeavailableonlineatalaterdate. #include "GraphOps.h" #include "Logger.h" #include < boost/graph/adjacency list.hpp > //forgraphtype #include < boost/graph/properties.hpp > //forgraphproperties #include < boost/graph/graph traits.hpp > //forgraphtraits #include < boost/property map/property map.hpp > //foraccessingproperties #include < boost/ref.hpp > // #include < boost/algorithm/string.hpp > //forsplitwhenreadingingraphfiles #include < boost/graph/boyer myrvold planar test.hpp > //for planaritytesting #include < boost/graph/is kuratowski subgraph.hpp > //forverifyingplanarityorK3,3 #include < boost/graph/erdos renyi generator.hpp > //forgeneratingrandomgraphs #include < boost/random/linear congruential.hpp > //forgeneratingrandomgraphs 51

PAGE 62

#include < boost/config.hpp > //forkuratowski identification #include < boost/tuple/tuple.hpp > //fortieinkuratowski identification #include < boost/graph/isomorphism.hpp > //forkuratowskiidentification #include < boost/graph/connected components.hpp > //for makingsureweareconnected #include < iostream > #include < utility > #include < algorithm > #include < string > #include "embedder.h" usingnamespace boost; GraphOps::GraphOps f planar graphs=0; k 3 3 graphs=0; k 5 then k 3 3 graphs=0; k 5 then k 3 3 graphs colored=0; k 5 then planar graphs=0; k 5 then k 5 graphs=0; k 5 then k 5 then planar graphs=0; 52

PAGE 63

k 5 then k 5 then k 3 3 graphs=0; k 5 then k 5 then k 3 3 graphs colored=0; k 5 then k 5 then k 5 then k 3 3 graphs=0; k 5 then k 5 then k 5 then k 3 3 graphs colored=0; k 5 then k 5 then k 5 then planar graphs=0; k 5 then k 5 then k 5 graphs=0; k 5 then k 5 then k 5 then k 5 graphs=0; graphs colored=0; graphs not colored=0; non toroidal graphs=0; g //Sothatwecanknowwhichkuratowskisubgraphweare dealingwith template < typename Graph, typename ForwardIterator > GraphOps::kgraphGraphOps::identify kuratowski subgraph const Graph&g,ForwardIteratorbegin,ForwardIteratorend f return return type of kuratowskig,begin,end,get vertex index,g; g GraphOps::kgraphGraphOps::testGraphGraphZ::Graphg f //Testforplanarity typedef std::vector < graph traits < GraphZ::Graph > :: edge descriptor > 53

PAGE 64

kuratowski edges t; GraphOps::kur vertices.clear; kuratowski edges tkuratowski edges; if boyer myrvold planarity testboyer myrvold params:: graph=g, boyer myrvold params::kuratowski subgraph= std::back inserterkuratowski edges f return planar; g else f Logger::Instance )]TJ/F19 11.9552 Tf 7.556 0 Td [(> writeToLogFile"Input graph is not planar",NULL; Logger::Instance )]TJ/F19 11.9552 Tf 7.556 0 Td [(> writeToLogFile"Testing for Kuratowski Subgraph",NULL; Logger::Instance )]TJ/F19 11.9552 Tf 7.556 0 Td [(> writeToLogFile"Edges in the Kuratowski subgraph : ",NULL; kuratowski edges t::iteratorki,ki end; ki end=kuratowski edges.end; for ki=kuratowski edges.begin;ki!=ki end;++ ki f Logger::Instance )]TJ/F19 11.9552 Tf 7.556 0 Td [(> writeToLogFile ki; 54

PAGE 65

graph traits < GraphZ::Graph > ::edge descriptor edge t ki; graph traits < GraphZ::Graph > ::vertex descriptor vertex sourcesourceedge t,g; graph traits < GraphZ::Graph > ::vertex descriptor vertex targettargetedge t,g; if std::findkur vertices.begin,kur vertices. end,vertex source!=kur vertices.end f / kur verticescontainsvertex source / / donothing / g else f / kur verticesdoesnotcontain vertex source / / addthevalue / kur vertices.push backvertex source; g if std::findkur vertices.begin,kur vertices. end,vertex target!=kur vertices.end f / kur verticescontainsvertex source / / donothing / g else f / kur verticesdoesnotcontain vertex source / / addthevalue / 55

PAGE 66

kur vertices.push backvertex target; g g Logger::Instance )]TJ/F19 11.9552 Tf 7.556 0 Td [(> logFileEndl; Logger::Instance )]TJ/F19 11.9552 Tf 7.556 0 Td [(> writeToLogFile"Is a kuratowski subgraph? ",NULL; if is kuratowski subgraph g,kuratowski edges.begin,kuratowski edges. end f Logger::Instance )]TJ/F19 11.9552 Tf 7.556 0 Td [(> writeToLogFile"Yes",NULL; kgraphkurgraph=identify kuratowski subgraphg, kuratowski edges.begin,kuratowski edges. end; switch kurgraph f case k 5: return k 5; break ; case k 3 3: return k 3 3; break ; g g 56

PAGE 67

else f Logger::Instance )]TJ/F19 11.9552 Tf 7.556 0 Td [(> writeToLogFile"No",NULL; return planar; g g g std::stringGraphOps::isolateThree const GraphZ::Graph&g, int iteration f //Thenumberofcombinationsthisthinghas,whichis5 choose3 int number of combinations=9; //arraynumbered //SowefoundaK 5again,let'stestit again //obtainthemajorverticesbytrackingthecontraction ofedgesinthe //kuratowskisubgraphfunction. std::vector < graph traits < GraphZ::Graph > :: vertex descriptor > diff3; std::vector < graph traits < GraphZ::Graph > :: vertex descriptor > isolated vertices3; std::vector < graph traits < GraphZ::Graph > :: vertex descriptor > ::iteratoritr3; 57

PAGE 68

std::vector < graph traits < GraphZ::Graph > ::edge descriptor > removed edges3; std::vector < graph traits < GraphZ::Graph > ::edge descriptor > ::iteratoritr4; //testingherewillresetthekur verticesandthe contracted verticesfromthe //testdonebelow. testGraphg; //findthedifferencebetweenthecontractedverticesand thekuratowskivertices //thereshouldbeexactly5inthedifference,theseare ourmajorvertices. for itr3=kur vertices.begin;itr3!=kur vertices. end;itr3++ f if std::findcontracted vertices.begin, contracted vertices.end, itr3!= contracted vertices.end f / contracted verticescontainskur vertex / / donothing / g else f / contracted verticesdoesnotcontain kur vertex / / addthevaluetodiff / 58

PAGE 69

diff3.push back itr3; g g Logger::Instance )]TJ/F19 11.9552 Tf 7.556 0 Td [(> writeToLogFile"3rd Isolation:",NULL ; Logger::Instance )]TJ/F19 11.9552 Tf 7.556 0 Td [(> logFileEndl; Logger::Instance )]TJ/F19 11.9552 Tf 7.556 0 Td [(> writeToLogFile"K5 Major Vertices:", NULL; Logger::Instance )]TJ/F19 11.9552 Tf 7.556 0 Td [(> logFileEndl; std::stringstreamss1; ss1 << "3rd Isolation" << std::endl; ss1 << "K5 Major Vertices: << std::endl; for itr3=diff3.begin;itr3!=diff3.end;itr3++ f Logger::Instance )]TJ/F19 11.9552 Tf 7.556 0 Td [(> writeToLogFile itr3; Logger::Instance )]TJ/F19 11.9552 Tf 7.556 0 Td [(> logFileEndl; ss1 << itr3 << std::endl; g std::vector < boost::tuple < graph traits < GraphZ::Graph > ::vertex descriptor, graph traits < GraphZ::Graph > ::vertex descriptor, graph traits < GraphZ::Graph > ::vertex descriptor >> the tuples=K7Combinationskur vertices; 59

PAGE 70

//selectthefirstvertexforisolation //we'lljustselectthefirstone isolated vertices3.clear; graph traits < GraphZ::Graph > ::vertex descriptor isolation vertex3=the tuples[iteration].get < 0 > ; Logger::Instance )]TJ/F19 11.9552 Tf 7.556 0 Td [(> writeToLogFile"Isolating Vertex: ", isolation vertex3; isolated vertices3.push backisolation vertex3; ss1 << "Isolation Vertex: << isolation vertex3 << std:: endl; //removetheedgescontainingthisvertex graph traits < GraphZ::Graph > ::edge iteratorei3,ei end3; //makeacopyofgtoworkwith,thisdoesn'thavetobe i,itcouldbeh GraphZ::Graphi=g; for boost::tuples::tieei3,ei end3=edgesi;ei3!= ei end3;++ei3 f if source ei3,i==isolation vertex3 jj target ei3,i==isolation vertex3 f removed edges3.push back ei3; g g 60

PAGE 71

for itr4=removed edges3.begin;itr4!= removed edges3.end;++itr4 f graph traits < GraphZ::Graph > ::vertex descriptor vertex1=source itr4,i; graph traits < GraphZ::Graph > ::vertex descriptor vertex2=target itr4,i; remove edgevertex1,vertex2,i; g //selectthesecondvertexforisolation //we'lljustselectthenextone isolation vertex3=the tuples[iteration].get < 1 > ; Logger::Instance )]TJ/F19 11.9552 Tf 7.556 0 Td [(> writeToLogFile"Isolating Vertex: ", isolation vertex3; isolated vertices3.push backisolation vertex3; ss1 << "Isolation Vertex: << isolation vertex3 << std:: endl; //removetheedgescontainingthisvertex for boost::tuples::tieei3,ei end3=edgesi;ei3!= ei end3;++ei3 f if source ei3,i==isolation vertex3 jj target ei3,i==isolation vertex3 f removed edges3.push back ei3; 61

PAGE 72

g g for itr4=removed edges3.begin;itr4!= removed edges3.end;++itr4 f graph traits < GraphZ::Graph > ::vertex descriptor vertex1=source itr4,i; graph traits < GraphZ::Graph > ::vertex descriptor vertex2=target itr4,i; remove edgevertex1,vertex2,i; g //selectthethirdvertexforisolation //we'lljustselectthenextone isolation vertex3=the tuples[iteration].get < 2 > ; Logger::Instance )]TJ/F19 11.9552 Tf 7.556 0 Td [(> writeToLogFile"Isolating Vertex: ", isolation vertex3; isolated vertices3.push backisolation vertex3; ss1 << "Isolation Vertex: << isolation vertex3 << std:: endl; //removetheedgescontainingthisvertex for boost::tuples::tieei3,ei end3=edgesi;ei3!= ei end3;++ei3 f 62

PAGE 73

if source ei3,i==isolation vertex3 jj target ei3,i==isolation vertex3 f removed edges3.push back ei3; g g for itr4=removed edges3.begin;itr4!= removed edges3.end;++itr4 f graph traits < GraphZ::Graph > ::vertex descriptor vertex1=source itr4,i; graph traits < GraphZ::Graph > ::vertex descriptor vertex2=target itr4,i; remove edgevertex1,vertex2,i; g Logger::Instance )]TJ/F19 11.9552 Tf 7.556 0 Td [(> writeToLogFile"Three Vertices Isolated, Retesting Planarity: ",NULL; ss1 << "Three Vertices Isolated, Retesting Planarity: << std::endl; //Initializetheinterioredgeindex property map < GraphZ::Graph,edge index t > ::typee index5 =getedge index,i; graph traits < GraphZ::Graph > ::edges size typeedge count5 =0; 63

PAGE 74

graph traits < GraphZ::Graph > ::edge iteratorei5,ei end5; for boost::tuples::tieei5,ei end5=edgesi;ei5!= ei end5;++ei5 f pute index5, ei5,edge count5++; Logger::Instance )]TJ/F19 11.9552 Tf 7.556 0 Td [(> writeToLogFilesource ei5,i, target ei5,i; ss1 << source ei5,i << "," << target ei5,i << std::endl; g //retestforplanarity,ifthereisaK3,3,weknowthat itcanbe4 )]TJ/F34 11.9552 Tf 10.561 0 Td [(coloredduetoHadwiger typedef std::vector < graph traits < GraphZ::Graph > :: edge descriptor > kuratowski edges t; kuratowski edges tkuratowski edges4; if boyer myrvold planarity testboyer myrvold params:: graph=i, boyer myrvold params::kuratowski subgraph= std::back inserterkuratowski edges4 f Logger::Instance )]TJ/F19 11.9552 Tf 7.556 0 Td [(> writeToLogFile"Input graph is planar",NULL; ss1 << "Input Graph is Planar" << std::endl; 64

PAGE 75

k 5 then k 5 then k 5 then planar graphs++; g else f Logger::Instance )]TJ/F19 11.9552 Tf 7.556 0 Td [(> writeToLogFile"Input graph is not planar",NULL; Logger::Instance )]TJ/F19 11.9552 Tf 7.556 0 Td [(> writeToLogFile"Testing for Kuratowski Subgraph",NULL; Logger::Instance )]TJ/F19 11.9552 Tf 7.556 0 Td [(> writeToLogFile"Edges in the Kuratowski subgraph: ",NULL; ss1 << "Input Graph is not Planar" << std::endl; ss1 << "Testing for Kuratowski Subgraph" << std::endl ; ss1 << "Edges in the Kuratowski Subgraph" << std:: endl; kuratowski edges t::iteratorki4,ki end4; ki end4=kuratowski edges4.end; for ki4=kuratowski edges4.begin;ki4!=ki end4; ++ki4 f Logger::Instance )]TJ/F19 11.9552 Tf 7.556 0 Td [(> writeToLogFile ki4; ss1 << ki4 << std::endl; graph traits < GraphZ::Graph > ::edge descriptor edge t ki4; graph traits < GraphZ::Graph > ::vertex descriptor vertex sourcesourceedge t,i; 65

PAGE 76

graph traits < GraphZ::Graph > ::vertex descriptor vertex targettargetedge t,i; if std::findkur vertices.begin,kur vertices. end,vertex source!=kur vertices.end f / kur verticescontainsvertex source / / donothing / g else f / kur verticesdoesnotcontain vertex source / / addthevalue / kur vertices.push backvertex source; g if std::findkur vertices.begin,kur vertices. end,vertex target!=kur vertices.end f / kur verticescontainsvertex source / / donothing / g else f / kur verticesdoesnotcontain vertex source / / addthevalue / kur vertices.push backvertex target; g g Logger::Instance )]TJ/F19 11.9552 Tf 7.556 0 Td [(> logFileEndl; 66

PAGE 77

Logger::Instance )]TJ/F19 11.9552 Tf 7.556 0 Td [(> writeToLogFile"Is a kuratowski subgraph?",NULL; ss1 << "Is a Kuratowski subgraph?" << std::endl; if is kuratowski subgraph i,kuratowski edges4.begin,kuratowski edges4. end f Logger::Instance )]TJ/F19 11.9552 Tf 7.556 0 Td [(> writeToLogFile"Yes.",NULL; ss1 << "Yes." << std::endl; kgraphkurgraph=identify kuratowski subgraphi, kuratowski edges4.begin,kuratowski edges4. end; switch kurgraph f case k 5: Logger::Instance )]TJ/F19 11.9552 Tf 7.556 0 Td [(> writeToLogFile"The graph contains a kuratowski subgraph of K5", NULL; ss1 << "The graph contains a kuratowski subgraph of K5" << std::endl; if iteration==number of combinations f std::stringRotationSystem= GetRotationSystemg; if RotationSystem!="Not Toroidal" 67

PAGE 78

k 5 then k 5 then k 5 then k 5 graphs ++; g else f isolateThreeg,++iteration; g break ; case k 3 3: Logger::Instance )]TJ/F19 11.9552 Tf 7.556 0 Td [(> writeToLogFile"The graph contains a kuratowski subgraph of K3,3", NULL; Logger::Instance )]TJ/F19 11.9552 Tf 7.556 0 Td [(> writeToLogFile"The graph is therefore 4 )]TJ/F15 11.9552 Tf 10.791 0 Td [(colorable according to Hadwiger",NULL; ss1 << "The graph contains a kuratowski subgraph of K3,3" << std::endl; ss1 << "The graph is therefore 4 )]TJ/F15 11.9552 Tf 10.792 0 Td [(colorable according to Hadwiger" << std::endl; k 5 then k 5 then k 5 then k 3 3 graphs++; if testColoringi,removed edges3, isolated vertices3 f Logger::Instance )]TJ/F19 11.9552 Tf 7.556 0 Td [(> writeToLogFile"The graph was successfully colored!",NULL ; 68

PAGE 79

ss1 << "The graph was successfully colored!" << std::endl; //Logthecolors graph traits < GraphZ::Graph > :: vertex iteratorvi2,vi end2; for boost::tuples::tievi2,vi end2= verticesg;vi2!=vi end2;++vi2 f Logger::Instance )]TJ/F19 11.9552 Tf 7.556 0 Td [(> writeToLogFile" Vertex: ", vi2; Logger::Instance )]TJ/F19 11.9552 Tf 7.556 0 Td [(> writeToLogFile" Color: ",vertex colors[ vi2]; Logger::Instance )]TJ/F19 11.9552 Tf 7.556 0 Td [(> logFileEndl; ss1 << "Vertex: << vi2 << Color: << vertex colors[ vi2] << std:: endl; g k 5 then k 5 then k 5 then k 3 3 graphs colored ++; g else f if iteration==number of combinations f Logger::Instance )]TJ/F19 11.9552 Tf 7.556 0 Td [(> writeToLogFile" The graph was not successfully 69

PAGE 80

colored :",NULL; ss1 << "The graph was not successfully colored :" << std:: endl; //spawnafilecontainingthe interestinggraph. std::ofstreamlogFile; time ttimev; std::stringstreamss; ss << "Isolate3 << time&timev << ".txt"; logFile.openss.str; logFile << num verticesg << std:: endl; for boost::tuples::tieei3,ei end3 =edgesg;ei3!=ei end3;++ei3 f logFile << source ei3,g << "," << target ei3,g << std:: endl; g logFile.close; g else f 70

PAGE 81

Logger::Instance )]TJ/F19 11.9552 Tf 7.556 0 Td [(> writeToLogFile" The graph was not successfully colored :",NULL; ss1 << "The graph was not successfully colored :" << std:: endl; ss1 << isolateThreeg,++iteration; g g break ; case planar: Logger::Instance )]TJ/F19 11.9552 Tf 7.556 0 Td [(> writeToLogFile"The graph does not contain a kuratowski subgraph", NULL; ss1 << "The graph does not contain a kuratowski subgraph" << std::endl; break ; g g g return ss1.str; g std::stringGraphOps::isolateTwo const GraphZ::Graph&g, int iteration f 71

PAGE 82

//thenumberofcombinationsthisthinghas,whichis5 choose2 int number of combinations=9; //arraynumbered //Hereiswherewewillisolatethevertexandcontinue withsome //testingandcoloring //WeknowthatthisgraphcontainseitheracompleteK 5 subgraph //orithasaK 5subdivision,mostlikelyasubdivision. //obtainthemajorverticesbytrackingthecontraction ofedgesinthe //kuratowskisubgraphfunction. std::vector < graph traits < GraphZ::Graph > :: vertex descriptor > diff2; std::vector < graph traits < GraphZ::Graph > :: vertex descriptor > isolated vertices2; std::vector < graph traits < GraphZ::Graph > :: vertex descriptor > ::iteratoritr2; std::vector < graph traits < GraphZ::Graph > ::edge descriptor > removed edges2; std::vector < graph traits < GraphZ::Graph > ::edge descriptor > ::iteratoritr3; //testingherewillresetthekur verticesandthe contracted verticesfromthe 72

PAGE 83

//testdonebelow. testGraphg; //findthedifferencebetweenthecontractedverticesand thekuratowskivertices //thereshouldbeexactly5inthedifference,theseare ourmajorvertices. for itr2=kur vertices.begin;itr2!=kur vertices. end;itr2++ f if std::findcontracted vertices.begin, contracted vertices.end, itr2!= contracted vertices.end f / contracted verticescontainskur vertex / / donothing / g else f / contracted verticesdoesnotcontain kur vertex / / addthevaluetodiff / diff2.push back itr2; g g std::stringstreamss1; Logger::Instance )]TJ/F19 11.9552 Tf 7.556 0 Td [(> writeToLogFile"2nd Isolation",NULL ; 73

PAGE 84

Logger::Instance )]TJ/F19 11.9552 Tf 7.556 0 Td [(> logFileEndl; Logger::Instance )]TJ/F19 11.9552 Tf 7.556 0 Td [(> writeToLogFile"K5 Major Vertices: ", NULL; ss1 << "2nd Isolation << std::endl; ss1 << "K5 Major Vertices: << std::endl; for itr2=diff2.begin;itr2!=diff2.end;itr2++ f Logger::Instance )]TJ/F19 11.9552 Tf 7.556 0 Td [(> writeToLogFile itr2; Logger::Instance )]TJ/F19 11.9552 Tf 7.556 0 Td [(> logFileEndl; ss1 << itr2 << std::endl; g Logger::Instance )]TJ/F19 11.9552 Tf 7.556 0 Td [(> logFileEndl; //weneedthecombinationsofverticesforthisK6,so let'sgetem std::vector < std::pair < graph traits < GraphZ::Graph > ::vertex descriptor, graph traits < GraphZ::Graph > ::vertex descriptor >> thePairs= K6Combinationskur vertices; //selectfirstoneforisolation //we'lljustselectthefirstone isolated vertices2.clear; 74

PAGE 85

graph traits < GraphZ::Graph > ::vertex descriptor isolation vertex2=thePairs[iteration].first; isolated vertices2.push backisolation vertex2; Logger::Instance )]TJ/F19 11.9552 Tf 7.556 0 Td [(> writeToLogFile"Isolating Vertex: ", isolation vertex2; ss1 << "Isolating Vertex: << isolation vertex2 << std:: endl; //removetheedgescontainingthisvertex graph traits < GraphZ::Graph > ::edge iteratorei2,ei end2; //makeacopyofgtoworkwith. GraphZ::Graphh=g; for boost::tuples::tieei2,ei end2=edgesh;ei2!= ei end2;++ei2 f if source ei2,h==isolation vertex2 jj target ei2,h==isolation vertex2 f removed edges2.push back ei2; g g for itr3=removed edges2.begin;itr3!= removed edges2.end;++itr3 f 75

PAGE 86

graph traits < GraphZ::Graph > ::vertex descriptor vertex1=source itr3,h; graph traits < GraphZ::Graph > ::vertex descriptor vertex2=target itr3,h; remove edgevertex1,vertex2,h; g //selectthesecondoneforisolation //we'lljustselectthenextone isolation vertex2=thePairs[iteration].second; Logger::Instance )]TJ/F19 11.9552 Tf 7.556 0 Td [(> writeToLogFile"Isolating Vertex: ", isolation vertex2; isolated vertices2.push backisolation vertex2; ss1 << "Isolating Vertex: << isolation vertex2 << std:: endl; //removetheedgescontainingthisvertex for boost::tuples::tieei2,ei end2=edgesh;ei2!= ei end2;++ei2 f if source ei2,h==isolation vertex2 jj target ei2,h==isolation vertex2 f removed edges2.push back ei2; g g 76

PAGE 87

for itr3=removed edges2.begin;itr3!= removed edges2.end;++itr3 f graph traits < GraphZ::Graph > ::vertex descriptor vertex1=source itr3,h; graph traits < GraphZ::Graph > ::vertex descriptor vertex2=target itr3,h; remove edgevertex1,vertex2,h; g Logger::Instance )]TJ/F19 11.9552 Tf 7.556 0 Td [(> writeToLogFile"Two Vertices Isolated Retesting Planarity: ",NULL; ss1 << "Two Vertices Isolated, Retesting Planarity: << std::endl; //Initializetheinterioredgeindex property map < GraphZ::Graph,edge index t > ::typee index3 =getedge index,h; graph traits < GraphZ::Graph > ::edges size typeedge count3 =0; graph traits < GraphZ::Graph > ::edge iteratorei3,ei end3; for boost::tuples::tieei3,ei end3=edgesh;ei3!= ei end3;++ei3 f pute index3, ei3,edge count3++; Logger::Instance )]TJ/F19 11.9552 Tf 7.556 0 Td [(> writeToLogFilesource ei3,h, target ei3,h; 77

PAGE 88

ss1 << source ei3,h << "," << target ei3,h << std::endl; g //retestforplanarity,ifthereisaK3,3,weknowthat itcanbe4 )]TJ/F34 11.9552 Tf 10.561 0 Td [(coloredduetosoandso typedef std::vector < graph traits < GraphZ::Graph > :: edge descriptor > kuratowski edges t; kuratowski edges tkuratowski edges3; if boyer myrvold planarity testboyer myrvold params:: graph=h, boyer myrvold params::kuratowski subgraph= std::back inserterkuratowski edges3 f Logger::Instance )]TJ/F19 11.9552 Tf 7.556 0 Td [(> writeToLogFile"Input graph is planar",NULL; ss1 << "Input graph is planar" << std::endl; k 5 then k 5 then planar graphs++; g else f Logger::Instance )]TJ/F19 11.9552 Tf 7.556 0 Td [(> writeToLogFile"Input graph is not planar",NULL; 78

PAGE 89

Logger::Instance )]TJ/F19 11.9552 Tf 7.556 0 Td [(> writeToLogFile"Testing for Kuratowski Subgraph",NULL; Logger::Instance )]TJ/F19 11.9552 Tf 7.556 0 Td [(> writeToLogFile"Edges in the Kuratowski subgraph: ",NULL; ss1 << "Input graph is not planar" << std::endl; ss1 << "Testing for Kuratowski Subgraph" << std::endl ; ss1 << "Edges in the Kuratowski subgraph: << std:: endl; kuratowski edges t::iteratorki3,ki end3; ki end3=kuratowski edges3.end; for ki3=kuratowski edges3.begin;ki3!=ki end3; ++ki3 f Logger::Instance )]TJ/F19 11.9552 Tf 7.556 0 Td [(> writeToLogFile ki3; graph traits < GraphZ::Graph > ::edge descriptor edge t ki3; graph traits < GraphZ::Graph > ::vertex descriptor vertex sourcesourceedge t,h; graph traits < GraphZ::Graph > ::vertex descriptor vertex targettargetedge t,h; if std::findkur vertices.begin,kur vertices. end,vertex source!=kur vertices.end f / kur verticescontainsvertex source / / donothing / g 79

PAGE 90

else f / kur verticesdoesnotcontain vertex source / / addthevalue / kur vertices.push backvertex source; g if std::findkur vertices.begin,kur vertices. end,vertex target!=kur vertices.end f / kur verticescontainsvertex source / / donothing / g else f / kur verticesdoesnotcontain vertex source / / addthevalue / kur vertices.push backvertex target; g g Logger::Instance )]TJ/F19 11.9552 Tf 7.556 0 Td [(> logFileEndl; Logger::Instance )]TJ/F19 11.9552 Tf 7.556 0 Td [(> writeToLogFile"Is a kuratowski subgraph? ",NULL; ss1 << "Is a kuratowski subgraph? << std::endl; if is kuratowski subgraph h,kuratowski edges3.begin,kuratowski edges3. end 80

PAGE 91

f Logger::Instance )]TJ/F19 11.9552 Tf 7.556 0 Td [(> writeToLogFile"Yes.",NULL; ss1 << "Yes." << std::endl; kgraphkurgraph=identify kuratowski subgraphh, kuratowski edges3.begin,kuratowski edges3. end; switch kurgraph f case k 5: Logger::Instance )]TJ/F19 11.9552 Tf 7.556 0 Td [(> writeToLogFile"The graph contains a kuratowski subgraph of K5", NULL; ss1 << "The graph contains a kuratowski subgraph of K5" << std::endl; if iteration==number of combinations f //ifwefoundanotherk5afterisolating 2vertices, //thenproceedtothenextisolationwith theoriginalgraph k 5 then k 5 then k 5 graphs++; ss1 << isolateThreeg,0; g else f ss1 << isolateTwog,++iteration; 81

PAGE 92

g break ; case k 3 3: Logger::Instance )]TJ/F19 11.9552 Tf 7.556 0 Td [(> writeToLogFile"The graph contains a kuratowski subgraph of K3,3", NULL; Logger::Instance )]TJ/F19 11.9552 Tf 7.556 0 Td [(> writeToLogFile"The graph is therefore 4 )]TJ/F15 11.9552 Tf 10.791 0 Td [(colorable according to Hadwiger",NULL; ss1 << "The graph contains a kuratowski subgraph of K3,3" << std::endl; ss1 << "The graph is therefore 4 )]TJ/F15 11.9552 Tf 10.792 0 Td [(colorable according to Hadwiger" << std::endl; k 5 then k 5 then k 3 3 graphs++; if testColoringh,removed edges2, isolated vertices2 f Logger::Instance )]TJ/F19 11.9552 Tf 7.556 0 Td [(> writeToLogFile"The graph was successfully colored!",NULL ; ss1 << "The graph was successfully colored!" << std::endl; //Logthecolors graph traits < GraphZ::Graph > :: vertex iteratorvi2,vi end2; 82

PAGE 93

for boost::tuples::tievi2,vi end2= verticesg;vi2!=vi end2;++vi2 f Logger::Instance )]TJ/F19 11.9552 Tf 7.556 0 Td [(> writeToLogFile" Vertex: ", vi2; Logger::Instance )]TJ/F19 11.9552 Tf 7.556 0 Td [(> writeToLogFile" Color: ",vertex colors[ vi2]; Logger::Instance )]TJ/F19 11.9552 Tf 7.556 0 Td [(> logFileEndl; ss1 << "Vertex: << vi2 << Color: << vertex colors[ vi2] << std:: endl; g k 5 then k 5 then k 3 3 graphs colored++; g else f if iteration==number of combinations f Logger::Instance )]TJ/F19 11.9552 Tf 7.556 0 Td [(> writeToLogFile" The graph was not successfully colored :",NULL; ss1 << "The graph was not successfully colored :" << std:: endl; //spawnafilecontainingthe interestinggraph. std::ofstreamlogFile; 83

PAGE 94

time ttimev; std::stringstreamss; ss << "Isolate2 << time&timev << ".txt"; logFile.openss.str; logFile << num verticesg << std:: endl; for boost::tuples::tieei3,ei end3 =edgesg;ei3!=ei end3;++ei3 f logFile << source ei3,g << "," << target ei3,g << std:: endl; g logFile.close; g else f Logger::Instance )]TJ/F19 11.9552 Tf 7.556 0 Td [(> writeToLogFile" The graph was not successfully colored :",NULL; ss1 << "The graph was not successfully colored :" << std:: endl; isolateTwog,++iteration; g 84

PAGE 95

g break ; case planar: Logger::Instance )]TJ/F19 11.9552 Tf 7.556 0 Td [(> writeToLogFile"The graph does not contain a kuratowski subgraph", NULL; ss1 << "The graph does not contain a kuratowski subgraph" << std::endl; break ; g g g return ss1.str; g std::stringGraphOps::isolateOne const GraphZ::Graph&g, int iteration f std::stringstreamss1; //Hereiswherewewillisolateavertexandcontinue withsome //testingandcoloring //WeknowthatthisgraphcontainseitheracompleteK 5 subgraph //orithasaK 5subdivision,mostlikelyasubdivision. 85

PAGE 96

//obtainthemajorverticesbytrackingthecontraction ofedgesinthe //kuratowskisubgraphfunction. std::vector < graph traits < GraphZ::Graph > :: vertex descriptor > diff; std::vector < graph traits < GraphZ::Graph > :: vertex descriptor > isolated vertices; std::vector < graph traits < GraphZ::Graph > :: vertex descriptor > ::iteratoritr; std::vector < graph traits < GraphZ::Graph > ::edge descriptor > removed edges; std::vector < graph traits < GraphZ::Graph > ::edge descriptor > ::iteratoritr2; //testingherewillresetthekur verticesandthe contracted verticesfromthe //testdonebelow. testGraphg; //findthedifferencebetweenthecontractedverticesand thekuratowskivertices //thereshouldbeexactly5inthedifference,theseare ourmajorvertices. for itr=kur vertices.begin;itr!=kur vertices.end ;itr++ f 86

PAGE 97

if std::findcontracted vertices.begin, contracted vertices.end, itr!= contracted vertices.end f / contracted verticescontainskur vertex / / donothing / g else f / contracted verticesdoesnotcontain kur vertex / / addthevaluetodiff / diff.push back itr; g g Logger::Instance )]TJ/F19 11.9552 Tf 7.556 0 Td [(> writeToLogFile"K5 Major Vertices: ", NULL; ss1 << "K5 Major Vertices: << std::endl; for itr=diff.begin;itr!=diff.end;itr++ f Logger::Instance )]TJ/F19 11.9552 Tf 7.556 0 Td [(> writeToLogFile itr; Logger::Instance )]TJ/F19 11.9552 Tf 7.556 0 Td [(> logFileEndl; ss1 << itr << std::endl; g Logger::Instance )]TJ/F19 11.9552 Tf 7.556 0 Td [(> logFileEndl; //selectoneforisolation 87

PAGE 98

//we'llselectthevertexassociatedwiththisiteration isolated vertices.clear; graph traits < GraphZ::Graph > ::vertex descriptor isolation vertex=diff[iteration]; isolated vertices.push backdiff[iteration]; Logger::Instance )]TJ/F19 11.9552 Tf 7.556 0 Td [(> writeToLogFile"Isolating Vertex: ", isolation vertex; ss1 << "Isolating Vertex: << isolation vertex << std:: endl; //removetheedgescontainingthisvertex graph traits < GraphZ::Graph > ::edge iteratorei,ei end; //makeacopyofgtoworkwith. GraphZ::Graphh=g; //placetheedgestoberemovedinavector for boost::tuples::tieei,ei end=edgesh;ei!= ei end;++ei f if source ei,h==isolation vertex jj target ei, h==isolation vertex f removed edges.push back ei; g g 88

PAGE 99

//removetheedges for itr2=removed edges.begin;itr2!=removed edges. end;++itr2 f graph traits < GraphZ::Graph > ::vertex descriptor vertex1=source itr2,h; graph traits < GraphZ::Graph > ::vertex descriptor vertex2=target itr2,h; remove edgevertex1,vertex2,h; g Logger::Instance )]TJ/F19 11.9552 Tf 7.556 0 Td [(> writeToLogFile"Vertex Isolated, Retesting Planarity: ",NULL; ss1 << "Vertex Isolated, Retesting Planarity: << std:: endl; //Initializetheinterioredgeindex property map < GraphZ::Graph,edge index t > ::typee index2 =getedge index,h; graph traits < GraphZ::Graph > ::edges size typeedge count2 =0; graph traits < GraphZ::Graph > ::edge iteratorei2,ei end2; for boost::tuples::tieei2,ei end2=edgesh;ei2!= ei end2;++ei2 f pute index2, ei2,edge count2++; 89

PAGE 100

Logger::Instance )]TJ/F19 11.9552 Tf 7.556 0 Td [(> writeToLogFilesource ei2,h, target ei2,h; g kgraphkurgraph=testGraphh; switch kurgraph f case k 5: Logger::Instance )]TJ/F19 11.9552 Tf 7.556 0 Td [(> writeToLogFile"The graph contains a kuratowski subgraph of K5",NULL; ss1 << "The graph contains a kuratowski subgraph of K5" << std::endl; //ifwehavestillfoundaK5afteriteratingover allmajorvertices, //testagaintofigureoutifwehadaK6orshould //continuetofindaK7 if iteration==4 f k 5 then k 5 graphs++; ss1 << isolateTwog,0; //usetheoriginalgraph! g else f ss1 << isolateOneg,++iteration; g break ; 90

PAGE 101

case k 3 3: Logger::Instance )]TJ/F19 11.9552 Tf 7.556 0 Td [(> writeToLogFile"The graph contains a kuratowski subgraph of K3,3",NULL; Logger::Instance )]TJ/F19 11.9552 Tf 7.556 0 Td [(> writeToLogFile"The graph is therefore 4 )]TJ/F15 11.9552 Tf 10.791 0 Td [(colorable according to Hadwiger",NULL ; ss1 << "The graph contains a kuratowski subgraph of K3,3" << std::endl; ss1 << "The graph is therefore 4 )]TJ/F15 11.9552 Tf 10.792 0 Td [(colorable according to Hadwiger" << std::endl; k 5 then k 3 3 graphs++; if testColoringh,removed edges,isolated vertices f Logger::Instance )]TJ/F19 11.9552 Tf 7.556 0 Td [(> writeToLogFile"The graph was successfully colored!",NULL; ss1 << "The graph was successfully colored!" << std::endl; //Logthecolors graph traits < GraphZ::Graph > ::vertex iteratorvi2, vi end2; for boost::tuples::tievi2,vi end2=vertices g;vi2!=vi end2;++vi2 f Logger::Instance )]TJ/F19 11.9552 Tf 7.556 0 Td [(> writeToLogFile"Vertex: vi2; 91

PAGE 102

Logger::Instance )]TJ/F19 11.9552 Tf 7.556 0 Td [(> writeToLogFile"Color: ", vertex colors[ vi2]; Logger::Instance )]TJ/F19 11.9552 Tf 7.556 0 Td [(> logFileEndl; ss1 << "Vertex: << vi2 << Color: << vertex colors[ vi2] << std::endl; g k 5 then k 3 3 graphs colored++; g else f if iteration==4 f Logger::Instance )]TJ/F19 11.9552 Tf 7.556 0 Td [(> writeToLogFile"The graph was not successfully colored :",NULL; ss1 << "The graph was not successfully colored :" << std::endl; //spawnafilecontainingtheinteresting graph. std::ofstreamlogFile; time ttimev; std::stringstreamss; ss << "Isolate1 << time&timev << ".txt"; logFile.openss.str; logFile << num verticesg << std::endl; for boost::tuples::tieei2,ei end2=edges g;ei2!=ei end2;++ei2 f 92

PAGE 103

logFile << source ei2,g << "," << target ei2,g << std::endl; g logFile.close; g else f Logger::Instance )]TJ/F19 11.9552 Tf 7.556 0 Td [(> writeToLogFile"The graph was not successfully colored :",NULL; ss1 << "The graph was not successfully colored :" << std::endl; ss1 << isolateOneg,++iteration; g g break ; case planar: Logger::Instance )]TJ/F19 11.9552 Tf 7.556 0 Td [(> writeToLogFile"The graph does not contain a kuratowski subgraph",NULL; ss1 << "The graph does not contain a kuratowski subgraph" << std::endl; break ; g return ss1.str; g //MakesasimpleK 5graphsothatwecantest //isomorphisminthekuratowskisubgraphcheck 93

PAGE 104

template < typename Graph > GraphGraphOps::make K 5 f typename graph traits < Graph > ::vertex iteratorvi,vi end, inner vi; GraphK 55; for boost::tievi,vi end=verticesK 5;vi!=vi end ;++vi for inner vi=nextvi;inner vi!=vi end;++inner vi add edge vi, inner vi,K 5; return K 5; g //MakesasimpleK 3 3graphsothatwecantest //isomorphisminthekuratowskisubgraphcheck template < typename Graph > GraphGraphOps::make K 3 3 f typename graph traits < Graph > ::vertex iterator vi,vi end,bipartition start,inner vi; GraphK 3 36; bipartition start=nextnextnextverticesK 3 3.first ; for boost::tievi,vi end=verticesK 3 3;vi!= bipartition start;++vi for inner vi=bipartition start;inner vi!=vi end;++ inner vi 94

PAGE 105

add edge vi, inner vi,K 3 3; return K 3 3; g //Contractsedgesforthekuratowskicheck template < typename AdjacencyList, typename Vertex > void GraphOps::contract edgeAdjacencyList&neighbors,Vertex u,Vertexv f //Removeufromv'sneighborlist neighbors[v].erasestd::removeneighbors[v].begin, neighbors[v].end,u neighbors[v].end ; //Replaceanyreferencestouwithreferencestov typedeftypename AdjacencyList::value type::iterator adjacency iterator t; adjacency iterator tu neighbor end=neighbors[u].end; for adjacency iterator tu neighbor itr=neighbors[u]. begin; u neighbor itr!=u neighbor end;++u neighbor itr f Vertexu neighbor u neighbor itr; 95

PAGE 106

std::replaceneighbors[u neighbor].begin, neighbors[u neighbor].end,u,v ; g //Removevfromu'sneighborlist neighbors[u].erasestd::removeneighbors[u].begin, neighbors[u].end,v neighbors[u].end ; //Addeverythinginu'sneighborlisttov'sneighbor list std::copyneighbors[u].begin, neighbors[u].end, std::back inserterneighbors[v] ; //Clearu'sneighborlist neighbors[u].clear; g //returnsthetypeofkuratowskisubgraphwearedealingwith template < typename Graph, typename ForwardIterator, typename VertexIndexMap > 96

PAGE 107

GraphOps::kgraphGraphOps::return type of kuratowski const Graph&g,ForwardIteratorbegin,ForwardIteratorend, VertexIndexMapvm f typedeftypename graph traits < Graph > ::vertex descriptor vertex t; typedeftypename graph traits < Graph > ::vertex iterator vertex iterator t; typedeftypename graph traits < Graph > ::edge descriptor edge t; typedeftypename graph traits < Graph > ::edges size type e size t; typedeftypename graph traits < Graph > ::vertices size type v size t; typedeftypename std::vector < vertex t > v list t; typedeftypename v list t::iteratorv list iterator t; typedef iterator property map < typename std::vector < v list t > ::iterator, VertexIndexMap > vertex to v list map t; typedef adjacency list < vecS,vecS,undirectedS > small graph t; target graph ttarget graph=tg k 3 3; //unlesswe decideotherwiselater 97

PAGE 108

static small graph tK 5GraphOps::make K 5 < small graph t > ; static small graph tK 3 3GraphOps::make K 3 3 < small graph t > ; v size tn verticesnum verticesg; v size tmax num edges3 n vertices )]TJ/F15 11.9552 Tf 16.778 0 Td [(5; std::vector < v list t > neighbors vectorn vertices; vertex to v list map tneighborsneighbors vector.begin ,vm; //hereiswherewepopulatethecontractedvertices,so clearitbeforehand contracted vertices.clear; //Countthenumberofedgesandcreateneighborlistsfor eachvertex e size tcount=0; for ForwardIteratoritr=begin;itr!=end;++itr f if count++ > max num edges return planar; edge te itr; 98

PAGE 109

vertex tusourcee,g; vertex tvtargete,g; neighbors[u].push backv; neighbors[v].push backu; g for v size tmax size=2;max size < 5;++max size f vertex iterator tvi,vi end; for boost::tievi,vi end=verticesg;vi!= vi end;++vi f vertex tv vi; //ahacktomakesurewedon'tcontractthe middleedgeofapath //offourdegree )]TJ/F34 11.9552 Tf 8.888 0 Td [(3vertices if max size==4&&neighbors[v].size==3 f if neighbors[neighbors[v][0]].size+ neighbors[neighbors[v][1]].size+ neighbors[neighbors[v][2]].size < 11 //so,ithastwodegree )]TJ/F34 11.9552 Tf 8.889 0 Td [(3neighbors 99

PAGE 110

continue ; g while neighbors[v].size > 0&&neighbors[v]. size < max size f //Findoneofv'sneighborsusuchthatv andu //havenoneighborsincommon.We'lllook forsucha //neighborwithanaivecubic )]TJ/F34 11.9552 Tf 9.297 0 Td [(timealgorithm sincethe //maxsizeofanyoftheneighborsetswe'll consider //mergingis3 bool neighbor sets intersect= false ; vertex tmin u=graph traits < Graph > :: null vertex; vertex tu; v list iterator tv neighbor end=neighbors[ v].end; for v list iterator tv neighbor itr= neighbors[v].begin; v neighbor itr!=v neighbor end; ++v neighbor itr 100

PAGE 111

f neighbor sets intersect= false ; u= v neighbor itr; v list iterator tu neighbor end= neighbors[u].end; for v list iterator tu neighbor itr= neighbors[u].begin; u neighbor itr!=u neighbor end&& !neighbor sets intersect; ++u neighbor itr f for v list iterator t inner v neighbor itr= neighbors[v].begin; inner v neighbor itr!= v neighbor end; ++inner v neighbor itr f if u neighbor itr== inner v neighbor itr f neighbor sets intersect= true ; break ; 101

PAGE 112

g g g if !neighbor sets intersect&& min u==graph traits < Graph > :: null vertex jj neighbors[u].size < neighbors[min u ].size f min u=u; g g if min u==graph traits < Graph > ::null vertex //Exitedtheloopwithoutfindingan appropriateneighborof //v,sovmustbealostcause.Moveon toothervertices. break ; else u=min u; contract edgeneighbors,u,v; 102

PAGE 113

contracted vertices.push backu; Logger::Instance )]TJ/F19 11.9552 Tf 7.556 0 Td [(> edgeContractedu,v; g //enditerationoverv'sneighbors g //enditerationthroughverticesv if max size==3 f //checktoseewhetherweshouldgoontofinda K 5 for boost::tievi,vi end=verticesg;vi!= vi end;++vi if neighbors[ vi].size==4 f target graph=tg k 5; break ; g if target graph==tg k 3 3 break ; g g //enditerationthroughmaxdegree2,3,and4 //Now,thereshouldonlybe5or6verticeswithany neighbors.Findthem. 103

PAGE 114

v list tmain vertices; vertex iterator tvi,vi end; for boost::tievi,vi end=verticesg;vi!=vi end; ++vi f if !neighbors[ vi].empty main vertices.push back vi; g //createagraphisomorphictothecontractedgraphto test //againstK 5andK 3 3 small graph tcontracted graphmain vertices.size; std::map < vertex t, typename graph traits < small graph t > :: vertex descriptor > contracted vertex map; typename v list t::iteratoritr,itr end; itr end=main vertices.end; typename graph traits < small graph t > ::vertex iterator si=verticescontracted graph.first; for itr=main vertices.begin;itr!=itr end;++itr, ++si f 104

PAGE 115

contracted vertex map[ itr]= si; g typename v list t::iteratorjtr,jtr end; for itr=main vertices.begin;itr!=itr end;++itr f jtr end=neighbors[ itr].end; for jtr=neighbors[ itr].begin;jtr!=jtr end; ++jtr f if getvm, itr < getvm, jtr f add edgecontracted vertex map[ itr], contracted vertex map[ jtr], contracted graph ; g g g if target graph==tg k 5 f if boost::isomorphismK 5,contracted graph f return k 5; g g else //target graph==tg k 3 3 105

PAGE 116

f if boost::isomorphismK 3 3,contracted graph f return k 3 3; g g g void GraphOps::reset f planar graphs=0; k 3 3 graphs=0; k 5 then k 3 3 graphs=0; k 5 then planar graphs=0; k 5 then k 5 graphs=0; k 5 then k 5 then planar graphs=0; k 5 then k 5 then k 3 3 graphs=0; k 5 then k 5 then k 5 then k 3 3 graphs=0; k 5 then k 5 then k 5 then planar graphs=0; k 5 then k 5 then k 5 graphs=0; k 5 then k 5 then k 5 then k 5 graphs=0; graphs colored=0; graphs not colored=0; non toroidal graphs=0; k 5 then k 3 3 graphs colored=0; k 5 then k 5 then k 3 3 graphs colored=0; k 5 then k 5 then k 5 then k 3 3 graphs colored=0; 106

PAGE 117

g void GraphOps::LogStatistics f Logger::Instance )]TJ/F19 11.9552 Tf 7.556 0 Td [(> writeToLogFile"Planar Graphs: ", planar graphs; Logger::Instance )]TJ/F19 11.9552 Tf 7.556 0 Td [(> writeToLogFile"K 3 3 Graphs: ", k 3 3 graphs; Logger::Instance )]TJ/F19 11.9552 Tf 7.556 0 Td [(> writeToLogFile"K 5 then K 3 3 Graphs : ",k 5 then k 3 3 graphs; Logger::Instance )]TJ/F19 11.9552 Tf 7.556 0 Td [(> writeToLogFile"K 5 then Planar Graphs: ",k 5 then planar graphs; Logger::Instance )]TJ/F19 11.9552 Tf 7.556 0 Td [(> writeToLogFile"K 5 then K 5 Graphs: ",k 5 then k 5 graphs; Logger::Instance )]TJ/F19 11.9552 Tf 7.556 0 Td [(> writeToLogFile"K 5 then K 5 then Planar Graphs: ",k 5 then k 5 then planar graphs; Logger::Instance )]TJ/F19 11.9552 Tf 7.556 0 Td [(> writeToLogFile" k 5 then k 5 then k 3 3 Graphs: ", k 5 then k 5 then k 3 3 graphs; Logger::Instance )]TJ/F19 11.9552 Tf 7.556 0 Td [(> writeToLogFile" k 5 then k 5 then k 5 then k 3 3 Graphs: ", k 5 then k 5 then k 5 then k 3 3 graphs; Logger::Instance )]TJ/F19 11.9552 Tf 7.556 0 Td [(> writeToLogFile" k 5 then k 5 then k 5 then planar Graphs: ", k 5 then k 5 then k 5 then planar graphs; Logger::Instance )]TJ/F19 11.9552 Tf 7.556 0 Td [(> writeToLogFile"k 5 then k 5 then k 5 Graphs: ",k 5 then k 5 then k 5 graphs; 107

PAGE 118

Logger::Instance )]TJ/F19 11.9552 Tf 7.556 0 Td [(> writeToLogFile" k 5 then k 5 then k 5 then k 5 Graphs: ", k 5 then k 5 then k 5 then k 5 graphs; Logger::Instance )]TJ/F19 11.9552 Tf 7.556 0 Td [(> writeToLogFile"graphs colored: ", graphs colored; Logger::Instance )]TJ/F19 11.9552 Tf 7.556 0 Td [(> writeToLogFile"graphs not colored: ,graphs not colored; Logger::Instance )]TJ/F19 11.9552 Tf 7.556 0 Td [(> writeToLogFile"non toroidal graphs: ",non toroidal graphs; Logger::Instance )]TJ/F19 11.9552 Tf 7.556 0 Td [(> writeToLogFile" k 5 then k 3 3 graphs colored: ", k 5 then k 3 3 graphs colored; Logger::Instance )]TJ/F19 11.9552 Tf 7.556 0 Td [(> writeToLogFile" k 5 then k 5 then k 3 3 graphs colored", k 5 then k 5 then k 3 3 graphs colored; Logger::Instance )]TJ/F19 11.9552 Tf 7.556 0 Td [(> writeToLogFile" k 5 then k 5 then k 5 then k 3 3 graphs colored", k 5 then k 5 then k 5 then k 3 3 graphs colored; g GraphZ::GraphGraphOps::generateRandomGraph int graph size, double graph percentage f //Randomgraphgeneration typedef boost::erdos renyi iterator < boost::minstd rand, GraphZ::Graph > ERGen; boost::minstd randgenclock; 108

PAGE 119

GraphZ::GraphgERGengen,graph size,graph percentage, ERGen,graph size; return g; g double GraphOps::getDefaultEdgePercentage int graph size f return double 6/ double graph size )]TJ/F15 11.9552 Tf 16.778 0 Td [(1 )]TJ/F15 11.9552 Tf 17.406 0 Td [(0.02; g std::stringGraphOps::runtest graphGraphZ::Graphg f std::stringstreamss; Logger::Instance )]TJ/F19 11.9552 Tf 7.556 0 Td [(> writeToLogFile" <<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>> ",NULL; Logger::Instance )]TJ/F19 11.9552 Tf 7.556 0 Td [(> writeToLogFile" <<< NEW GRAPH >>> ", NULL; Logger::Instance )]TJ/F19 11.9552 Tf 7.556 0 Td [(> writeToLogFile" <<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>> ",NULL; Logger::Instance )]TJ/F19 11.9552 Tf 7.556 0 Td [(> writeToLogFile"Graph Edges: ",NULL ; ss << "Graph Edges: << std::endl; 109

PAGE 120

graph traits < GraphZ::Graph > ::edge iteratoredgeI, edgeI end; std::vector < graph traits < GraphZ::Graph > ::edge descriptor > theEdgesOfTheGraph; //placetheedgesinavector for boost::tuples::tieedgeI,edgeI end=edgesg; edgeI!=edgeI end;++edgeI f theEdgesOfTheGraph.push back edgeI; g for std::vector < graph traits < GraphZ::Graph > :: edge descriptor > ::size typei=0;i!= theEdgesOfTheGraph.size;i++ f //getridofloops if sourcetheEdgesOfTheGraph[i],g==target theEdgesOfTheGraph[i],g f g.remove edgetheEdgesOfTheGraph[i]; continue ; g //makesurealledgesfollowtheu < vformat if sourcetheEdgesOfTheGraph[i],g > target theEdgesOfTheGraph[i],g 110

PAGE 121

f add edgetargettheEdgesOfTheGraph[i],g,source theEdgesOfTheGraph[i],g,g; g.remove edgetheEdgesOfTheGraph[i]; continue ; g g graph traits < GraphZ::Graph > ::edge iteratoredgeI2, edgeI end2; std::vector < graph traits < GraphZ::Graph > ::edge descriptor > theEdgesOfTheGraph2; //placetheedgesinavector for boost::tuples::tieedgeI2,edgeI end2=edgesg; edgeI2!=edgeI end2;++edgeI2 f theEdgesOfTheGraph2.push back edgeI2; g //makesuretherearenoloopsorparalleledges for std::vector < graph traits < GraphZ::Graph > :: edge descriptor > ::size typei=0;i!= theEdgesOfTheGraph2.size;i++ f for std::vector < graph traits < GraphZ::Graph > :: edge descriptor > ::size typej=i+1;j!= 111

PAGE 122

theEdgesOfTheGraph2.size;j++ f //getridofduplicateedges if sourcetheEdgesOfTheGraph2[i],g==source theEdgesOfTheGraph2[j],g&& targettheEdgesOfTheGraph2[i],g==target theEdgesOfTheGraph2[j],g f g.remove edgetheEdgesOfTheGraph2[i]; break ; g g g graph traits < GraphZ::Graph > ::edge iteratoredgeI3, edgeI end3; std::vector < graph traits < GraphZ::Graph > ::edge descriptor > theEdgesOfTheGraph3; //placetheedgesinavector for boost::tuples::tieedgeI3,edgeI end3=edgesg; edgeI3!=edgeI end3;++edgeI3 f theEdgesOfTheGraph3.push back edgeI3; g //removesinglevertices 112

PAGE 123

graph traits < GraphZ::Graph > ::vertex iteratorvi,vi end, next; boost::tievi,vi end=verticesg; for next=vi;vi!=vi end;vi=next f ++next; bool found= false ; for std::vector < graph traits < GraphZ::Graph > :: edge descriptor > ::size typei=0;i < theEdgesOfTheGraph3.size;i++ f if sourcetheEdgesOfTheGraph3[i],g== vi jj targettheEdgesOfTheGraph3[i],g== vi found= true ; g if !found f remove vertex vi,g; g g //makesureweareconnectedorelsetheembedding librarywillshitthebed std::vector < int > componentnum verticesg; int number of connected components=connected components g,&component[0]; 113

PAGE 124

if number of connected components > 1 f ss << "The graph was disconnected." << std::endl; return ss.str; g std::stringembedding=""; if embedCreateGraphStringg,embedding,EmbedderAlg:: Tor JY f //Initializetheinterioredgeindex property map < GraphZ::Graph,edge index t > ::type e index=getedge index,g; graph traits < GraphZ::Graph > ::edges size type edge count=0; graph traits < GraphZ::Graph > ::edge iteratorei,ei end ; for boost::tuples::tieei,ei end=edgesg;ei!= ei end;++ei f pute index, ei,edge count++; Logger::Instance )]TJ/F19 11.9552 Tf 7.556 0 Td [(> writeToLogFilesource ei,g ,target ei,g; 114

PAGE 125

ss << source ei,g << "," << target ei,g << std::endl; g Logger::Instance )]TJ/F19 11.9552 Tf 7.556 0 Td [(> writeToLogFile"Testing for Planarity",NULL; ss << "Testing for Planarity" << std::endl; kgraphgraphType=testGraphg; switch graphType f case planar: Logger::Instance )]TJ/F19 11.9552 Tf 7.556 0 Td [(> writeToLogFile"Input graph is planar",NULL; ss << "Input graph is planar" << std::endl; planar graphs++; break ; case k 3 3: Logger::Instance )]TJ/F19 11.9552 Tf 7.556 0 Td [(> writeToLogFile"The graph contains a kuratowski subgraph of K3,3",NULL ; Logger::Instance )]TJ/F19 11.9552 Tf 7.556 0 Td [(> writeToLogFile"The graph is therefore 4 )]TJ/F15 11.9552 Tf 10.792 0 Td [(colorable according to Hadwiger", NULL; ss << "The graph contains a kuratowski subgraph of K3,3" << std::endl; 115

PAGE 126

ss << "The graph is therefore 4 )]TJ/F15 11.9552 Tf 10.791 0 Td [(colorable according to Hadwiger" << std::endl; k 3 3 graphs++; break ; case k 5: Logger::Instance )]TJ/F19 11.9552 Tf 7.556 0 Td [(> writeToLogFile"The graph contains a kuratowski subgraph of K5",NULL; ss << "The graph contains a kuratowski subgraph of K5" << std::endl; //Hereiswherewewillisolatesomeverticesand continuewithsome //testingandcoloring ss << GraphOps::isolateOneg,0; break ; g g else f Logger::Instance )]TJ/F19 11.9552 Tf 7.556 0 Td [(> writeToLogFile"The graph is not toroidal. It has no toroidal embedding according to Yu",NULL; ss << "The graph is not toroidal. It has no toroidal embedding according to Yu" << std::endl; non toroidal graphs++; g LogStatistics; 116

PAGE 127

return ss.str; g void GraphOps::runtest random int graph size, double inPercentage, bool defaultPercentage f //Calculategraphpercentagebasedonsomeawesomemath double graph percentage; if defaultPercentage graph percentage=getDefaultEdgePercentage graph size; else graph percentage=inPercentage; //Nowwecaninitializeourgraphusingiteratorsfrom ourabovevector GraphZ::Graphg=generateRandomGraphgraph size, graph percentage; runtest graphg; g bool GraphOps::testColoringGraphZ::Graphg,std::vector < graph traits < GraphZ::Graph > ::edge descriptor > removed edges, std::vector < graph traits < GraphZ::Graph > :: vertex descriptor > removed vertices 117

PAGE 128

f //Canthegraphbecoloredwithfourcolorsnowandifso whatarethey? ColorGraphcg; int colors=4; //thisiswherevertex colorsgetspopulated,solet's clearitnow. GraphOps::vertex colors.clear; if cg.graphColoringg,4,GraphOps::vertex colors f //coloredwith4colors. //colortheisolatedvertexorverticeswith //thenextcolors. for std::vector < int > ::size typei=0;i!= removed vertices.size;i++ f GraphOps::vertex colors[removed vertices[i]]=++ colors; g //restoretheremovededges for std::vector < int > ::size typei=0;i!= removed edges.size;i++ f add edgesourceremoved edges[i],g,target removed edges[i],g,g; g //verifythecoloringofthegraph 118

PAGE 129

graph traits < GraphZ::Graph > ::edge iteratorei2, ei end2; for boost::tuples::tieei2,ei end2=edgesg;ei2 !=ei end2;++ei2 f if vertex colors[source ei2,g]== vertex colors[target ei2,g] f Logger::Instance )]TJ/F19 11.9552 Tf 7.556 0 Td [(> writeToLogFile"The following vertices are the same color", NULL; Logger::Instance )]TJ/F19 11.9552 Tf 7.556 0 Td [(> writeToLogFilesource ei2,g,target ei2,g; returnfalse ; g g //Logthecolors graph traits < GraphZ::Graph > ::vertex iteratorvi2, vi end2; for boost::tuples::tievi2,vi end2=verticesg; vi2!=vi end2;++vi2 f Logger::Instance )]TJ/F19 11.9552 Tf 7.556 0 Td [(> writeToLogFile"Vertex: ", vi2; Logger::Instance )]TJ/F19 11.9552 Tf 7.556 0 Td [(> writeToLogFile"Color: ", vertex colors[ vi2]; 119

PAGE 130

g g else f Logger::Instance )]TJ/F19 11.9552 Tf 7.556 0 Td [(> writeToLogFile"Could not color with 4 colors.",NULL; returnfalse ; g returntrue ; g std::vector < std::pair < graph traits < GraphZ::Graph > :: vertex descriptor, graph traits < GraphZ::Graph > ::vertex descriptor >> GraphOps::K6Combinations std::vector < graph traits < GraphZ::Graph > :: vertex descriptor > kuratowski vertices f std::vector < std::pair < graph traits < GraphZ::Graph > :: vertex descriptor,graph traits < GraphZ::Graph > :: vertex descriptor >> return value; for std::vector < int > ::size typei=0;i!= kuratowski vertices.size;i++ f for std::vector < int > ::size typej=i+1;j!= kuratowski vertices.size;j++ f std::pair < graph traits < GraphZ::Graph > :: vertex descriptor,graph traits < GraphZ::Graph 120

PAGE 131

> ::vertex descriptor > the pair kuratowski vertices[i],kuratowski vertices[j ]; return value.push backthe pair; g g return return value; g std::vector < boost::tuple < graph traits < GraphZ::Graph > :: vertex descriptor, graph traits < GraphZ::Graph > ::vertex descriptor, graph traits < GraphZ::Graph > ::vertex descriptor >> GraphOps ::K7Combinations std::vector < graph traits < GraphZ::Graph > :: vertex descriptor > kuratowski vertices f std::vector < boost::tuple < graph traits < GraphZ::Graph > :: vertex descriptor, graph traits < GraphZ::Graph > ::vertex descriptor, graph traits < GraphZ::Graph > ::vertex descriptor >> return value; for std::vector < int > ::size typei=0;i!= kuratowski vertices.size;i++ f for std::vector < int > ::size typej=i+1;j!= kuratowski vertices.size;j++ f 121

PAGE 132

for std::vector < int > ::size typek=j+1;k!= kuratowski vertices.size;k++ f boost::tuple < graph traits < GraphZ::Graph > :: vertex descriptor, graph traits < GraphZ::Graph > :: vertex descriptor, graph traits < GraphZ::Graph > :: vertex descriptor > the tuple kuratowski vertices[i], kuratowski vertices[j], kuratowski vertices[k]; return value.push backthe tuple; g g g return return value; g std::stringGraphOps::CreateGraphStringGraphZ::Graphg f std::stringstreamss; //vertexnumberfollowedbyedgenumber ss << g.m vertices.size << " << g.m edges.size << "; //edgeiterators graph traits < GraphZ::Graph > ::edge iteratorei,ei end; 122

PAGE 133

std::vector < graph traits < GraphZ::Graph > ::edge descriptor > theEdges; //placetheedgesinavector for boost::tuples::tieei,ei end=edgesg;ei!= ei end;++ei f theEdges.push back ei; g //Sortthevector for std::vector < graph traits < GraphZ::Graph > :: edge descriptor > ::size typei=1;i < theEdges.size ;i++ f graph traits < GraphZ::Graph > ::edge descriptortheEdge =theEdges[i]; int k=i; while k > 0&&sourcetheEdges[k )]TJ/F15 11.9552 Tf 17.307 0 Td [(1],g > source theEdge,g f theEdges[k]=theEdges[k )]TJ/F15 11.9552 Tf 17.742 0 Td [(1]; k=k )]TJ/F15 11.9552 Tf 17.212 0 Td [(1; g theEdges[k]=theEdge; g 123

PAGE 134

for std::vector < graph traits < GraphZ::Graph > :: edge descriptor > ::size typei=0;i!=theEdges.size ;i++ f ss << sourcetheEdges[i],g << " << target theEdges[i],g << "; //std::cout << sourcetheEdges[i],g << "" << targettheEdges[i],g << "" << std::endl; g return ss.str; g std::stringGraphOps::GetRotationSystemGraphZ::Graphg f std::stringgraph=CreateGraphStringg; std::stringembedding=""; if embedgraph,embedding,EmbedderAlg::Tor JY return embedding; else return "Not Toroidal"; g 124

PAGE 135

REFERENCES [1]MichaelO.AlbertsonandJoanP.Hutchinson.Onsix-chromatictoroidalgraphs. Proc.LondonMath.Soc. ,41:533{556,1980. [2]KennethAppel,WolfgangHaken,etal.Everyplanarmapisfourcolorable.part i:Discharging. IllinoisJournalofMathematics ,21:429{490,1977. [3]JozsefBaloghand SarkaPetrckova.Thenumberofthemaximaltriangle-free graphs. Bull.Lond.Math.Soc. ,46:1003{1006,2014. [4]ChrisBiemann.Chinesewhispers:Anecientgraphclusteringalgorithm anditsapplicationtonaturallanguageprocessingproblems.In Proceedings oftheFirstWorkshoponGraphBasedMethodsforNaturalLanguageProcessing ,TextGraphs-1,pages73{80,Stroudsburg,PA,USA,2006.Associationfor ComputationalLinguistics. [5]ThomasBohmeandAlexandrKostochka.Disjoint K r -minorsinlargegraphs withgivenaveragedegree. EuropeanJ.Combin. ,26-4:289{292,2005. [6]StephanBrandt,JochenHarant,andSteNaumann.Ondegreesumsofa triangle-freegraph. DiscreteMath. ,337:76{82,2014. [7]A.Cayley.Xxviii.onthetheoryoftheanalyticalformscalledtrees. Philosophical MagazineSeries4 ,13:172{176,1857. [8]G.A.Dirac.Map-colourtheorems. CanadianJ.Math. ,4:480{490,1952. [9]StephaneDurocher,DavidS.Gunderson,PakChingLi,andMatthewSkala. Cycle-maximaltriangle-freegraphs. DiscreteMath. ,338:274{290,2015. [10]P.Erd}osandA.Renyi.Ontheevolutionofrandomgraphs. MagyarTud.Akad. Mat.KutatoInt.Kozl. ,5:17{61,1960. [11]LeonhardEuler.Solutioproblematisadgeometriamsituspertinentis. CommentariiAcademiaeScientiarumImperialisPetropolitanae ,8:128{140,1736. [12]AndreiGagarin,GilbertLabelle,andPierreLeroux.Thestructureof K 3 ; 3 subdivision-freetoroidalgraphs. DiscreteMath. ,307:2993{3005,2007. [13]H.Hadwiger. UbereineKlassikationderStreckenkomplexe. Vierteljschr. Naturforsch.Ges.Zurich ,88:133{142,1943. [14]FrankHarary. Graphtheory .Addison-WesleyPublishingCo.,Reading,Mass.MenloPark,Calif.-London,1969. 125

PAGE 136

[15]FHavet.Graphcolouringandapplications. [16]P.J.Heawood.Map-colourtheorem. Proc.LondonMath.Soc. ,51:161{175, 1949. [17]DenesKonig. TheoriederendlichenundunendlichenGraphen .AmericanMathematicalSoc.,2001. [18]TomaszKrawczyk,ArkadiuszPawlik,andBartoszWalczak.ColoringTriangleFreeRectangleOverlapGraphswith O loglog n Colors. DiscreteComput. Geom. ,53:199{220,2015. [19]HudsonV.KronkandArthurT.White.A4-colortheoremfortoroidalgraphs. Proc.Amer.Math.Soc. ,34:83{86,1972. [20]KristinaKunert,MattiasWecksten,andMagnusJonsson.Algorithmforthe choiceoftopologyinrecongurableon-chipnetworkswithreal-timesupport.In Proceedingsofthe2NdInternationalConferenceonNano-Networks ,Nano-Net '07,pages13:1{13:7,ICST,Brussels,Belgium,Belgium,2007.ICSTInstitutefor ComputerSciences,Social-InformaticsandTelecommunicationsEngineering. [21]KasimierzKuratowski.Ontheproblemofskewcurvesintopology.In GraphtheoryLagow,1981 ,volume1018of LectureNotesinMath. ,pages1{13.Springer, Berlin,1983.TranslatedfromtheFrenchbyJanJaworowski. [22]MichelleAnneLastrina. List-coloringandsum-list-coloringproblemsongraphs ProQuestLLC,AnnArbor,MI,2012.ThesisPh.D.{IowaStateUniversity. [23]Chun-HeeLeeandChin-WanChung.Ecientsearchingraphdatabasesusing crossltering. Inform.Sci. ,286:1{18,2014. [24]FrankThomsonLeighton.Agraphcoloringalgorithmforlargeschedulingproblems. J.Res.Nat.Bur.Standards ,84:489{506,1979. [25]AudeMarzuoli,VladPopescu,andEricFeron.Twoperspectivesongraph-based tracowmanagement. FirstSESARInnovationDays ,2011. [26]BojanMoharandCarstenThomassen. Graphsonsurfaces .JohnsHopkins StudiesintheMathematicalSciences.JohnsHopkinsUniversityPress,Baltimore,MD,2001. [27]YelenaNakhimovsky,AndrewTMiller,TomDimopoulos,andMichaelSiliski. Behindthescenesofgooglemapsnavigation:enablingactionableuserfeedback atscale.In CHI'10ExtendedAbstractsonHumanFactorsinComputingSystems ,pages3763{3768.ACM,2010. [28]EugeneNeufeldandWendyMyrvold.Practicaltoroidalitytesting.In Proc.of theEighthAnnualACM-SIAMSymposiumonDiscreteAlgorithms ,pages574{ 580,1996. 126

PAGE 137

[29]DavidS.Richeson. Euler'sgem .PrincetonUniversityPress,Princeton,NJ, 2008.Thepolyhedronformulaandthebirthoftopology. [30]NeilRobertson,DanielP.Sanders,PaulSeymour,andRobinThomas.Anew proofofthefour-colourtheorem. Electron.Res.Announc.Amer.Math.Soc. 2:17{25,1996. [31]NeilRobertson,PaulSeymour,andRobinThomas.Hadwiger'sconjecturefor K 6 -freegraphs. Combinatorica ,13:279{361,1993. [32]Wen-yaoSong,Lian-yingMiao,andShu-jieZhang.Listedgeandlisttotal coloringoftriangle-free1-planargraphs. J.EastChinaNorm.Univ.Natur.Sci. Ed. ,:40{44,2014. [33]YuriN.Sotskov,VjacheslavS.Tanaev,andFrankWerner.Schedulingproblems andmixedgraphcolorings. Optimization ,51:597{624,2002. [34]J.J.Sylvester.OnanApplicationoftheNewAtomicTheorytotheGraphical RepresentationoftheInvariantsandCovariantsofBinaryQuantics,WithThree Appendices,[Continued]. Amer.J.Math. ,1:105{125,1878. [35]K.Wagner. UbereineEigenschaftderebenenKomplexe. Math.Ann. 114:570{590,1937. [36]BartoszWalczak.Triangle-FreeGeometricIntersectionGraphswithNoLarge IndependentSets. DiscreteComput.Geom. ,53:221{225,2015. [37]JiahuaYu.Apracticaltorusembeddingalgorithmanditsimplementation.Master'sthesis,SimonFrasierUniversity,June2014. 127