Boka investering

En bokinbäddning i grafteori  är en generalisering av en plan inbäddning av en graf till en inbäddning i en bok  - en uppsättning halvplan som har samma räta linje som en gräns. Det krävs vanligtvis att grafens hörn ligger på denna gräns, och kanterna måste vara innanför samma sida. Boktjockleken (eller antalet sidor ) för en graf är det minsta antalet halvplan för alla bokinbäddningar av grafen. [1] Bokinbäddning används för flera andra grafinvarianter , inklusive sidbredd [2] och bokantal av kryss [3] .

Varje graf med n hörn har högst en bokbredd . Denna gräns är nära för kompletta grafer [1] . Men om du delar upp varje kant kan boktjockleken minskas till en mängd som är proportionell mot kvadratroten av n . [4] Grafer med boktjocklek ett är ytterplanära grafer , [1] och grafer med boktjocklek högst två är sub-Hamiltoniska , som alltid är plana [2] . Varje plan graf har en boktjocklek som inte överstiger fyra [5] . Alla mindre slutna familjer av grafer , och i synnerhet grafer med avgränsad trädbredd eller avgränsat släkte , har också avgränsad boktjocklek [6] . Att bestämma den exakta boktjockleken för en given graf är ett NP-hårt problem , oavsett om ordningen på hörnen på ryggraden är känd eller inte [7] [8] .

En av de första anledningarna till att studera bokkapsling var dess tillämpning i VLSI-design , där bokhäckande hörn representerar komponenter och kanter representerar kopplingar mellan komponenter [7] [9] . När du visualiserar grafer kan två standardstilar av grafrepresentation, bågdiagram [10] och cirkulära arrangemang [11] , byggas med bokkapsling. De olika start- och slutpunkterna för trafiken för fotgängare och fordon som regleras av ett trafikljus kan modelleras matematiskt som grafiska hörn, med kanter som representerar start-slut-par, och boken kapsling av denna graf kan användas för att skapa ett trafikljus beteende för att ge trafikreglering med minimalt antal trafikljuslägen [12] . I bioinformatikproblem som handlar om RNA- strukturer representerar en bokinbäddning på en sida den klassiska formen av en sekundär nukleinsyrastruktur , och en tvåsidig inbäddning representerar pseudoknoter [13] . Bokinbäddning används också i allmän algebra [14] och knutteori [15] [16] .

De öppna frågorna om bokinvesteringar är

Historik

Namnet "bok" introducerades av Persinger och Atneosen (CA Persinger, Gail Atneosen) på 1960-talet [21] [22] [23] . Atneosen hade redan använt inbäddning av grafer i böcker, men det formella konceptet med bokinbäddning formulerades av C. Kainen och L. Taylor Ollman i början av 1970-talet, och några ytterligare restriktioner lades till för inbäddningsmetoden - i deras formulering, hörn av grafen måste ligga på ryggraden av en bok, varje kant måste ligga på en sida (korsar inte ryggraden) och eventuella två kanter skär endast vid gemensamma ändhörn [24] [25] .

Viktiga milstolpar i vidareutvecklingen av bokinbäddning är beviset av Michalis Giannakakis i slutet av 1980-talet att boktjockleken på plana grafer inte överstiger fyra [26] [5] , och upptäckten i slutet av 1990-talet av ett nära samband mellan bok inbäddning och bioinformatik . [13]

Definitioner

En bok är en speciell sorts topologiska rymd (även kallad en fläkt halvplan) [21] [27] . Den består av en enda rak linje ℓ som kallas bokens ryggrad [28] tillsammans med en uppsättning av ett eller flera halvplan som kallas bokens sidor eller blad . Varje halvplan måste ha samma linje ℓ som dess gräns. Böcker med ett ändligt antal ( k ) sidor kan kapslas i tredimensionellt utrymme, till exempel genom att välja ett rektangulärt koordinatsystem som linjen ℓ på z - axeln och som den i- :te sidan (av k ) en kan ta en uppsättning punkter p så att det kortaste segmentet , som förbinder p med z -axeln , har en vinkel på 2π i / k med avseende på xz -planet [1] .

Visualiseringen av en bok med ändlig graf G till bok B är en ritning av graf G i B , så att vilken vertex av G som helst ritas på ryggraden B , och varje kant av G ritas som en kurva som ligger inom en sida av B. Bokantalet på k -sidor av skärningspunkter i en graf G  är det minsta antalet skärningar i en ritning på en bok med k -sidor [3] .

En bokinbäddning av en graf G i B  är en inbäddning av en graf G i ett mellanslag B . Det vill säga, det är en ritning av en graf G i B där kanterna inte skär varandra. Varje finit graf har en bok inbäddad i en bok med ett tillräckligt stort antal sidor. Det är till exempel alltid möjligt att kapsla varje kant på sin egen sida. Tjockleken på boken , antalet sidor eller stacken av graf G  är det minsta antal sidor som krävs för en bokkapsling av graf G. En annan parameter som mäter kvaliteten på en bokbilaga, förutom antalet sidor, är sidbredd . Detta är det maximala antalet kanter som korsar strålen vinkelrätt mot ryggraden inuti en enda sida. På motsvarande sätt (för bokinbäddningar, där varje kant är ritad som en monoton kurva), är detta den maximala storleken på en undergrupp av kanter så att intervallen som definieras på ryggraden av kanternas ändpunkter alla skär varandra [2] [29] [30] .

Det är väsentligt för dessa definitioner att kanterna kan ligga på endast en sida. Som Ameosen redan noterat, om kanterna kan gå från sida till sida (genom ryggraden), så kan vilken graf som helst bäddas in i en tresidig bok [22] [31] [20] . Men för en tresidig topologisk bokinbäddning , där ryggradsskärning är tillåten, förblir det ett intressant problem att bestämma det minsta ryggradsskärningsnumret som gör att grafen kan bäddas in i en bok [20] [32] .

Specifika grafer

Som visas i den första figuren är boktjockleken på hela grafen tre. Eftersom den inte är plan är boktjockleken större än två, men det finns en bokkapsel med tre sidor. Boktjockleken på en komplett vertexgraf är exakt . Detta resultat ger en övre gräns för den maximala boktjockleken för alla grafer med hörn [1] . Det tvåsidiga skärningsnumret för hela grafen är

vilket stämmer överens med Anthony Hills obevisade gissning . Det vill säga, om Hills gissning är sann, så är ritningen av denna graf som minimerar antalet skärningar en tvåsidig ritning [33] .

Tjockleken på boken för en komplett tvådelad graf är nästan lika stor  - för varje vertex i en mindre del kan du ordna kanterna som faller in mot dessa hörn på sin egen sida. Denna gräns är inte alltid strikt. Den har till exempel en boktjocklek på tre, inte fyra. Men när de två sidorna av grafen är mycket obalanserade, c , är bokens tjocklek exakt . [1] [34] Tjockleken på böckerna med binära de Bruijn- grafer, blandade utbytesgrafer och kubiska nätverk med cykler (när dessa grafer är tillräckligt stora för att inte vara plana) är exakt tre. [35]

Egenskaper

Subdivision Behavior

Olösta problem i matematik : Kan boktjockleken för en graf begränsas av en funktion av boktjockleken för underavdelningar?

Att dela upp varje kant av en graf i tvåkantsbanor genom att lägga till nya hörn för varje kant kan ibland öka bokens tjocklek (till exempel har en diamant en boktjocklek på ett, men dess underavdelning har en boktjocklek på två). En sådan underpartition kan dock också avsevärt minska grafens boktjocklek efter partitionen. Till exempel är boktjockleken för en komplett graf K n är Θ( n ) proportionell mot antalet av dess hörn, men att dela upp varje kant i två ger en underavdelning med en mycket mindre boktjocklek, bara O(√ n ). [4] . Trots förekomsten av exempel som det ovan antog Blankenship och Oporowski [31] att boktjockleken för underavdelningar inte kan vara väsentligt mindre än den för den ursprungliga grafen. Speciellt antog de att det finns någon funktion f , som för varje graf G och graf H som erhålls genom att ersätta varje kant på G med en bana med två kanter, om boktjockleken på graf H är t , då boktjockleken på grafen G överstiger inte f ( t ). [31] År 2013 förblev Blankenship-Oporowski-förmodan obevisad. [17]

Planaritet och yttre planaritet

Boktjockleken för en given graf G överstiger inte 1 om och endast om G är yttre plan . En ytterplanär graf är en graf som har en plan inbäddning där alla hörn hör till den yttre ytan av inbäddningen. För sådana grafer, om du placerar hörnen i samma ordning längs ryggraden som de visas på den yttre ytan (när en vertex återkommer på den yttre ytan tas bara en kopia av vertexen) en ensidig grafinbäddning. Omvänt är en bokkapsling på en sida automatiskt yttre plan - om grafen är kapslad på en sida, ger ett helt plan att lägga till ett andra halvplan, och den yttre ytan kommer att innehålla hela det tillagda halvplanet, med alla hörn liggande på denna yttre yta [1] [2] .

Varje bokinbäddning med två sidor är ett specialfall av en plan inbäddning, eftersom föreningen av två boksidor är ett utrymme som topologiskt motsvarar ett plan. Varje graf med boktjocklek två är alltså automatiskt plan . Närmare bestämt är boktjockleken på en graf G högst två om och endast om G är en subgraf till en plan graf som har en Hamiltonsk cykel [1] . Givet en graf med en bokinbäddning på två sidor, kan grafen utökas till en plan Hamiltonsk graf genom att lägga till (på valfri sida) ytterligare kanter mellan två på varandra följande hörn längs ryggraden, om de inte redan är förbundna med en kant, och mellan ryggradens första och sista vertex. Goldner–Harari-grafen ger ett exempel på en plan graf som inte har boktjocklek två - det är en maximal plan graf , så det är omöjligt att lägga till någon kant med bibehållen plan, och grafen har inte en Hamiltonian cykel [1] . På grund av kravet på att ha Hamiltonska cykler, är grafer som tillåter tvåsidiga kapslingar kända som sub-Hamiltonska grafer [2] .

Alla plana grafer med maximal grad fyra har ett bokinbäddningsdjup som högst två. [36] . Planar 3-trees har en maximal bokbredd på tre [37] . Alla plana grafer har en boktjocklek som inte överstiger fyra [26] [5] . Som Michalis Yannakakis påstod 1986 [26] finns det plana grafer med en bokinbäddningstjocklek som är exakt lika med fyra, men ett detaljerat bevis på detta påstående, meddelat i [5] , har aldrig publicerats. Av denna anledning markerade Duimovich [19] problemet med att bestämma den maximala tjockleken på en bokinbäddning av plana grafer som olöst [19] .

Relation med andra grafinvarianter

Tjockleken på boken är relaterad till tjockleken på grafen , antalet plana grafer som behövs för att täcka kanterna på en given graf. En graf G har tjockleken θ om den kan bäddas in i ett plan, och kanterna kan färgas i θ-färger på ett sådant sätt att kanter av samma färg inte skär varandra. På liknande sätt har en graf G bokbredd θ om den kan ritas i ett halvplan med hörn på halvplanets gräns och kantfärgad i θ-färger utan att korsa kanter av samma färg. Med denna formulering motsvarar kanterna av samma färg sidorna i bokbilagan. Tjockleken på grafen och bokens tjocklek kan dock skilja sig markant - det finns uppdelningar av kompletta grafer som har en obegränsad boktjocklek [31] [20] [4] , trots att grafens tjocklek är lika stor till två [4] .

Grafer med trädbredd k har en bokbredd som mest k + 1 [19] [38] och denna gräns nås för k > 2. [19] . Grafer med m kanter har bokbredd O(√ m ) [39] , och grafer med släkte g har  bokbredd O(√ g ) [40] . Mer allmänt har alla små slutna grafer en avgränsad boktjocklek [6] [41] .

Varje sammandragande moll av en graf med avgränsad boktjocklek är en gles graf vars kant-till-vertex-förhållande begränsas av en konstant som endast beror på djupet av mollen och boktjockleken. Det vill säga, i terminologin för Nexetril [6] har grafer med avgränsad boktjocklek begränsad tillväxt [6] . Men även grafer med en avgränsad grafgrad , ett väsentligt starkare tillväxtrestriktionskrav, kan ha en ogränsad boktjocklek [42] .

Eftersom två grafer med boktjocklek är plana grafer, uppfyller de planar partitioneringssatsen  — de har separatorer, delmängder av hörn vars borttagning delar upp grafen i bitar med högst 2 n /3 hörn i varje stycke, med endast O(√ n ) hörn i separator. Här betyder n antalet grafens hörn. Det finns dock grafer med boktjocklek tre som inte har sublinjära storleksseparatorer [43] .

Kanterna på en sida av en bifogad bok beter sig som en hög . Detta kan formaliseras genom att överväga en godtycklig sekvens av push- och pop-operationer (skjuta och poppa) på stapeln och bilda en graf där stackoperationerna motsvarar toppen av grafen som finns på ryggraden av bokinlägget i boken. ordningen på operationerna. Om vi ​​nu ritar en kant från varje pop-operation som poppar ett objekt x från stacken till push-operationen som trycker in det elementet på stacken, kommer den resulterande grafen automatiskt att ha en ensidig kapsling. Av denna anledning kallas antalet sidor i en graf också för dess stacknummer . I analogi definierar forskare en nästa grafinbäddning som en ritning av en graf i en bok där två kanter på sidan antingen korsar eller spänner över icke-korsande intervall på ryggraden. Sådana inbäddningar motsvarar på något sätt köer , och det minsta antal sidor som krävs för varje grafinbäddning kallas dess antal köer [6] [44] [45] .

Beräkningskomplexitet

Att bestämma tjockleken på en bokinbäddning är ett NP-hårt problem . Detta följer av det faktum att hitta en Hamilton-cykel i maximala plana grafer är ett NP-komplett problem . Tjockleken på bokinbäddningen av en maximal plan graf är två om och endast om det finns en Hamiltonsk bana. Att fastställa att tjockleken på bokinbäddningen av en given maximal plan graf är två är därför också ett NP-komplett problem. [7]

Om ordningen på hörnen längs ryggraden i bokkapsling är förutbestämd, kan en tvåsidig kapsling (om en sådan finns) hittas i linjär tid som ett planaritetstestalternativ för en graf som erhålls genom att förlänga en given graf genom att skapa en loop som förbinder hörn längs ryggraden [13] . Unger hävdade att hitta en tresidig inbäddning med en förutbestämd vertexordning kunde göras i polynomtid , även om hans beskrivning av detta resultat saknar ett antal väsentliga detaljer [18] . Men för grafer som kräver fyra eller fler sidor förblir problemet med att hitta en inbäddning med minsta möjliga antal sidor NP-hårt på grund av motsvarigheten till det NP-hårda problemet med att färglägga cirkeldiagram , skärningsgrafer för cirkelackord . Givet en graf G med en fast ordning av hörn på ryggraden, att placera dessa hörn i samma ordning på cirkeln och representera kanterna på G som segment ger en uppsättning ackord som representerar grafen G . Man kan nu bilda en cirkulär graf med ackorden i detta diagram som hörn och korsande par av ackord som kanter. Att färglägga en cirkelgraf ger en uppdelning av grafens G -kanter i delmängder som kan ritas utan skärningspunkter på en sida. En optimal färgsättning motsvarar således en optimal bokinbäddning. Eftersom att färga en cirkelgraf med fyra eller fler färger är NP-svårt, och eftersom vilken cirkelgraf som helst kan genereras på detta sätt från något problem med att hitta en bokinbäddning, är det också ett NP-hårt problem att hitta den optimala bokinbäddningen [8] [46] [47] . För en fast ordning av hörn på ryggraden under ett tvåsidigt häckande är det ett NP-svårt problem att minimera antalet korsningar om detta nummer inte är noll [46] .

Om ordningen på hörnen på ryggraden är okänd, men sökningen av kanter är given, är det möjligt att hitta ett 2-sidigt häckande (om det finns) i linjär tid genom att tillämpa en algoritm baserad på SPQR-träd [48] [ 49] . Men att hitta ett 2-sidigt häckande är NP-komplett om varken ordningen på hörnen på ryggraden eller sökningen av kanter är känd. Att hitta boknumret för skärningspunkter i en graf är också NP-svårt på grund av NP-fullständigheten i problemet med att kontrollera om det tvåsidiga boknumret för korsningar är noll.

Problemet med subgrafisomorfism , som går ut på att avgöra om en storleksbegränsad graf av något slag återfinns som en subgraf till en större graf, kan lösas i linjär tid om den större grafen har en inbäddningstjocklek för en avgränsad bok. Detsamma gäller för att avgöra om en graf av något slag är en genererad subgraf till en större graf, eller om den har en homeomorfism med den större grafen [50] [51] . Av samma anledning är problemet med att kontrollera om en graf med begränsad boktjocklek uppfyller en given logisk formel av första ordningen lösbart med avseende på en fast parameter [52] .

Applikationer

Feltolerant multiprocessorberäkning

En av huvudskälen till att studera bokinbäddning (enligt Chang, Leighton och Rosenberg [7] ) är dess användning i utvecklingen av VLSI för att skapa feltoleranta multiprocessorsystem . I DIOGENES-systemet som utvecklats av dessa författare är processorerna i ett multiprocessorsystem organiserade i en logisk kedja som motsvarar bokens ryggrad (även om de inte behöver vara placerade i en rak linje fysiskt på diagrammet ). Kommunikationslänkarna för dessa processorer är grupperade i "buntar" som motsvarar sidorna i en bok och fungerar som staplar  - att ansluta en av processorerna till början av kommunikationslinjen pressar upp alla tidigare anslutningar i bunten, och ansluter en annan processor till slutet av kommunikationslinjen ansluter den till en av de nedre processorerna i strålen och trycker alla kvarvarande nedåt. På grund av detta staplingsbeteende kan ett enda paket tjäna en uppsättning kommunikationslinjer som bildar kanterna på en enda sida i en bokbilaga. Genom att arrangera länkar på detta sätt kan ett brett utbud av topologier implementeras där det inte spelar någon roll vilken processor som misslyckas så länge det finns tillräckligt med processorer kvar i nätverket. Nätverkstopologierna som kan organiseras av ett sådant system är exakt de som är boktjocka och inte överstiger antalet paket som ska göras tillgängliga [7] .

Stack sortering

En annan tillämpning, som påpekats av Chang, Leighton och Rosenberg [7] , gäller sortering av permutationer med hjälp av stackar . Knuth visade att ett system som bearbetar en ström av data genom att trycka in ingångselement till stacken och sedan poppa dem på utgångsströmmen vid rätt tidpunkt kan sortera data om och bara om det inte finns några mönsterpermutationer i den ursprungliga elementordningen [ 53 ] . Sedan dess har det varit mycket arbete med detta och liknande problem med att sortera en dataström med mer generella stack- och kösystem. I det system som Chang, Leighton och Rosenberg betraktar måste varje element från ingångsströmmen skjutas upp på en av stackarna. Efter att all data har skjutits upp på stackarna, skjuts elementen bort från dessa stackar (i lämplig ordning) till utgångsströmmen. Som Chang et al noterade kan en given permutation sorteras med ett sådant system om och endast om någon graf som erhålls från permutationen har en bokinbäddning med en fast ordning av hörn längs ryggraden och antalet sidor som inte överstiger antalet staplar [7] .

Rörelsekontroll

Som Kainen [12] beskriver , kan bokinbäddning användas för att beskriva faserna av trafikljus vid en kontrollerad korsning. I en korsning kan inkommande och utgående körfält (inklusive ändarna av övergångsställen och cykelbanor) representeras som grafiska hörn placerade på ryggraden av en boktillbehör i den ordning som motsvarar ordningen för in-/utfart av trafik längs med korsning (medurs). Stigarna genom korsningen, där trafiken rör sig, och fotgängare från infartspunkten till utgångspunkten, kan representeras som kanterna på en oriktad graf. Till exempel kan den här grafen ha en kant från ett ingångsfält till ett utgångsfält som tillhör samma vägsegment, vilket representerar en U-sväng om U-svängar är tillåtna i korsningen. En given delmängd av sådana kanter representerar en uppsättning vägar som kan följas utan korsningar om och endast om delmängden inte innehåller ett par skärande kanter som finns på samma sida i en bokkapsling. Sålunda beskriver bokinbäddningen av grafen uppdelningen av banor i delmängder där rörelsen inte skär varandra, och boktjockleken på denna graf (med en fast inbäddning på ryggraden) ger det minsta antal olika trafikljusfaser som krävs för ett trafikljusschema som inkluderar alla möjliga vägar genom korsningen [ 12] . Denna modell är dock inte tillämpbar på mer komplexa trafikledningssystem som inte har ett fast schema.

Grafvisualisering

Bokinbäddning används också ofta för att visualisera nätverksdataflödet. De två standarddiagrammen för grafvisualisering , bågdiagram [10] och cirkeldiagram [11] , kan betraktas som bokinvesteringar. Bokinbäddning kan också användas för att bygga klusterscheman [48] , samtidiga inbäddningar [54] och 3D-grafritningar [55] .

Ett bågdiagram [10] eller en linjeinbäddning [46] placerar grafens hörn på en linje, och grafens kanter ritas som halvcirklar över och under den linjen, vilket ibland tillåter kanterna att vara linjesegment. Denna ritstil motsvarar en bok som kapslar med en sida (om alla halvcirklar är ovanför linjen) eller två sidor (om båda sidorna av linjen används) och introducerades ursprungligen som ett sätt att studera skärningsantalet av grafer. [56] [57] Plana grafer som inte har en tvåsidig bokkapsling kan ritas på liknande sätt genom att tillåta kanter att representeras av två halvcirklar ovanför och under en rät linje. Sådana ritningar är inte bokinbäddningar i termer av den vanliga definitionen och kallas topologiska bokinbäddningar [58] . För vilken plan graf som helst är det alltid möjligt att hitta en inbäddning som korsar ryggraden högst en gång. [59] .

I en annan ritstil, det cirkulära arrangemanget , placeras grafens hörn på en cirkel, och kanterna ritas inuti eller utanför cirkeln [11] . Återigen, arrangemanget av kanter inom cirkeln (t.ex. som linjesegment) motsvarar en ensidig bokteckning, medan arrangemanget av kanter på vardera sidan av cirkeln motsvarar en tvåsidig bokteckning [60] .

För ensidiga ritningar av alla stilar är det viktigt att hålla antalet korsningar lågt för att minska det visuella kaoset i ritningen. Att minimera antalet skärningar är ett NP-komplett problem [46] , men problemet kan approximeras med relationen O (log 2 n ), där n är antalet hörn [61] . Minimering av ensidigt eller tvåsidigt skärningsnummer kan avgöras med avseende på en fast parameter när den parametreras av det cyklomatiska numret för den givna grafen [62] . Heuristiska metoder har också utvecklats för att reducera komplexiteten i korsningar, baserade till exempel på noggrann vertexinsättningsordning och på lokal optimering [11] .

En tvåsidig bokinbäddning med en fast fördelning av kanter över sidorna kan representeras som en slags klusterplanaritet , där en given graf måste ritas så att delar av grafen (två underuppsättningar av kanter) är ordnade i figuren för att återspegla deras klustring [48] . En bokinbäddning på två sidor används också för att hitta en samtidig grafinbäddning, där två grafer ges på samma uppsättning hörn, och du måste hitta platsen för hörnen, där båda graferna är ritade i plan med rak linje segment [54] .

Bokbilagor som har mer än två sidor används för att bygga tredimensionella ritningar av grafer. I synnerhet använde Wood konstruktionen av bokinbäddningar, som bevarar den låga graden av varje vertex inom varje sida, som en metod för att bädda in grafer i ett tredimensionellt gitter med liten volym [55] .

Folding RNA

När man studerar hur RNA- molekyler viker sig för att bilda en RNA-struktur, kan standardvyn av den sekundära strukturen av en nukleinsyra beskrivas med hjälp av ett diagram som en kedja av baser (RNA-sekvens) ritad längs en rak linje tillsammans med en uppsättning av bågar ovanför linjen som beskriver strukturens parade baser . . Det vill säga, även om denna struktur har ett komplext tredimensionellt utseende, kan dess samband (om en sekundär struktur finns) beskrivas med en mer abstrakt struktur, en ensidig bokinlaga. Men inte alla RNA beter sig på ett så enkelt sätt. Haslinger och Stadler föreslog en så kallad "bisekundär struktur" för vissa RNA- pseudoknots , som har formen av en tvåsidig bokkapsling - RNA-sekvensen är återigen ritad längs en rak linje, men de parade baserna är ritade som bågar ovanför och under denna linje. För att bilda en bisekundär struktur måste grafen ha en grad som inte överstiger tre - varje bas kan vara i endast en kant av diagrammet, såväl som i två länkar med närliggande baser i sekvensen. Fördelen med denna formulering inkluderar det faktum att den utesluter strukturer som faktiskt är knutna i rymden, och att den täcker de flesta av de kända RNA-pseudoknoterna [13] .

Eftersom ordningen på ryggraden är känd initialt, kontrolleras förekomsten av en bisekondär struktur för givna parade baser direkt. Uppgiften att fördela kanter över två sidor kan formuleras som ett specialfall av problemet med tillfredsställelse av booleska formler i 2-konjunktiv normalform eller som ett problem att kontrollera tvådeladheten hos en cirkulär graf vars hörn är parade baser, och kanterna beskriver korsningen mellan parade baser [13] . Ett annat och mer effektivt sätt, som visas av Haslinger och Stadler [13] , för att fastställa att en bisekundär struktur existerar är genom det faktum att det sker om och endast om ingångsgrafen (grafen som bildas genom att loopa baserna i ordningen efter och lägga till parade baser som kanter) är plan [13] . Detta faktum gör det möjligt att känna igen en bisekondär struktur i linjär tid som ett specialfall av planaritetstestet .

Blin, Fertin, Rusu och Sinokvet använde förhållandet mellan sekundära strukturer och boktillbehör som en del av beviset på att vissa problem med att jämföra sekundära RNA-strukturer är NP-hårda [63] . Och om strukturen av RNA:t är tertiär snarare än bisekondär (det vill säga om mer än två sidor krävs i dess diagram), så är det återigen ett NP-hårt problem att bestämma antalet sidor [64] .

Computational complexity theory

Paian, Tewari och Vinodsoandran använde bokinbäddning för att studera beräkningskomplexiteten hos nåbarhetsproblemet i riktade grafer . Som de noterade kan nåbarhetsproblemet för tvåsidiga riktade grafer lösas i ett logaritmiskt utrymme med ett värde (analogt med den deterministiska logaritmiska minneskomplexiteten för problem i klass UP ). Emellertid ger nåbarhetsproblemet för tresidiga riktade grafer icke- deterministisk logaritmisk minneskomplexitet . Således verkar bokinbäddning vara nära relaterad till skillnaderna mellan dessa två komplexitetsklasser [65] .

Förekomsten av expanderare med ett konstant antal sidor [43] är ett nyckelsteg för att bevisa att det inte finns någon tidssubquadratisk simulering av tvåbands icke- deterministiska Turing-maskiner med enkelbands icke-deterministiska maskiner [66] .

Andra områden inom matematiken

Mackenzie och Overbey [14] studerade boktjocklekstillämpningar i allmän algebra med hjälp av grafer härledda från nolldivisorerna i en finit lokal ring genom att skapa en vertex för varje nolldelare och en kant för varje värdepar vars produkt är noll [14] .

I en rad artiklar studerade Dynnikov topologiska bokinbäddningar av knutar och länkar , vilket visade att dessa inbäddningar kan beskrivas med en kombinatorisk sekvens av symboler och att den topologiska ekvivalensen av två länkar kan visas genom en sekvens av lokala förändringar i inbäddningar [15 ] [16] .

Anteckningar

  1. ↑ 1 2 3 4 5 6 7 8 9 Bernhart och Kainen, 1979 , s. 320–331.
  2. ↑ 1 2 3 4 5 Heath, 1987 , s. 198–218.
  3. ↑ 12 Shahrokhi et al, 1996 , sid. 413–424.
  4. ↑ 1 2 3 4 Eppstein, 2001 .
  5. ↑ 1 2 3 4 Yannakakis, 1989 , s. 36–67.
  6. ↑ 1 2 3 4 5 Nešetřil, Ossona de Mendez, 2012 , s. 321–328.
  7. ↑ 1 2 3 4 5 6 7 Chung et al, 1987 , sid. 33–58.
  8. ↑ 12 Unger , 1988 , s. 61–72.
  9. ↑ Arnold L. Rosenberg. Proceedings från den sjuttonde sydöstra internationella konferensen om kombinatorik, grafteori och beräkningar (Boca Raton, Fla., 1986). - 1986. - T. 54. - S. 217-224. — (Congressus Numerantium). .
  10. ↑ 1 2 3 Wattenberg, 2002 , s. 111–116.
  11. ↑ 1 2 3 4 Baur, Brandes, 2005 , s. 332–343.
  12. ↑ 1 2 3 Kainen, 1990 , s. 127–132.
  13. ↑ 1 2 3 4 5 6 7 Haslinger et al, 1999 , s. 437–467.
  14. ↑ 1 2 3 McKenzie, Overbay, 2010 , s. 55–63.
  15. ↑ 1 2 Dynnikov, 1999 , s. 25–37, 96.
  16. ↑ 1 2 Dynnikov, 2001 , s. 243–283.
  17. ↑ 12 Blankenship , Oporowski, 2009 .
  18. ↑ 1 2 Walter Unger. STACS 92: 9th Annual Symposium on Theoretical Aspects of Computer Science, Cachan, Frankrike, 13–15 februari 1992, Proceedings. - Berlin: Springer, 1992. - T. 577. - S. 389-400. — (Föreläsningsanteckningar i datavetenskap). - doi : 10.1007/3-540-55210-3_199 . .
  19. ↑ 1 2 3 4 5 Dujmović, Wood, 2007 , s. 641–670.
  20. ↑ 1 2 3 4 Enomoto, Miyauchi, 1999 , s. 337–341.
  21. ↑ 12 Persinger , 1966 , s. 169–173.
  22. ↑ 1 2 Atneosen, 1968 , sid. 79.
  23. ↑ Gail H. Atneosen. Endimensionell n - bladig kontinua // Fundamenta Mathematicae . - 1972. - T. 74 , nr. 1 . — s. 43–45 . .
  24. ↑ Paul C. Kainen. Grafer och kombinatorik (Proceedings of the Capital Conference on Graph Theory and Combinatorics vid George Washington University 18–22 juni 1973) / Ruth A. Bari, Frank Harary. - 1974. - T. 406. - S. 76-108. — (Föreläsningsanteckningar i matematik). .
  25. ↑ L. Taylor Ollmann. Proc. 4th Southeastern Conference on Combinatorics, Graph Theory and Computing / Frederick Hoffman, Roy B. Levow, Robert SD Thomas. - 1973. - T. VIII. - S. 459. - (Congressus Numerantium). .
  26. ↑ 1 2 3 Yannakakis, 1986 , s. 104–108.
  27. ↑ T. C. Hales. Sfärförpackningar. II // Diskret & beräkningsgeometri. - 1997. - T. 18 , nr. 2 . — S. 135–149 . - doi : 10.1007/PL00009312 . .
  28. ↑ Ursprungligen rygg eller rygg
  29. ↑ Elena Stohr. En avvägning mellan sidnummer och sidbredd för bokinbäddningar av grafer // Information and Computation. - 1988. - T. 79 , nr. 2 . — S. 155–162 . - doi : 10.1016/0890-5401(88)90036-3 . .
  30. ↑ Elena Stohr. Sidbredden för trivalenta plana grafer // Diskret matematik . - 1991. - T. 89 , nr. 1 . — s. 43–49 . - doi : 10.1016/0012-365X(91)90398-L . .
  31. ↑ 1 2 3 4 Blankenship, Oporowski, 1999 .
  32. ↑ Hikoe Enomoto, Miki Shimabara Miyauchi, Katsuhiro Ota. Nedre gränser för antalet kantkorsningar över ryggraden i en topologisk bok inbäddning av en graf // Diskret tillämpad matematik. - 1999. - T. 92 , nr. 2-3 . — S. 149–155 . - doi : 10.1016/S0166-218X(99)00044-X . .
  33. ↑ Bernardo M. Ábrego, Oswin Aichholzer, Silvia Fernández-Merchant, Pedro Ramos, Gelasio Salazar. Proceedings of the 28th Annual Symposium on Computational Geometry (SCG'12). - ACM, New York, 2012. - S. 397-403. - doi : 10.1145/2261250.2261310 . .
  34. ↑ För ytterligare resultat om boktjockleken för Complete Bipartite Graphs, se Etienne de Klerk, Dmitrii V. Pasechnik, Gelasio Salazar. Bokritningar av kompletta tvådelade grafer // Diskret tillämpad matematik. - 2014. - T. 167 . — S. 80–93 . - doi : 10.1016/j.dam.2013.11.001 . .
  35. ↑ Toru Hasunuma, Yukio Shibata. Inbäddning av de Bruijn, Kautz och shuffle-exchange-nätverk i böcker // Discrete Applied Mathematics. - 1997. - T. 78 , nr. 1-3 . — S. 103–116 . - doi : 10.1016/S0166-218X(97)00009-7 . Yuuki Tanaka, Yukio Shibata På sidnumret för de kubkopplade cyklerna // Mathematics in Computer Science. - 2010. - Vol. 3 , nummer. 1 . — S. 109–117 . - doi : 10.1007/s11786-009-0012-y . Se även Bojana Obrenic. Inbäddning av de Bruijn och shuffle-exchange-grafer på fem sidor // SIAM Journal on Discrete Mathematics. - 1993. - T. 6 , nr. 4 . — S. 642–654 . - doi : 10.1137/0406049 . .
  36. ↑ Bekos et al, 2014 , s. 137–148.
  37. ↑ Lenny Heath. Proceedings of the 25th Annual Symposium on Foundations of Computer Science. - 1984. - S. 74-83. - doi : 10.1109/SFCS.1984.715903 .
  38. ↑ Joseph L. Ganley, Lenwood S. Heath. Sidnumret för k -träd är O ( k ) // Diskret tillämpad matematik. - 2001. - T. 109 , nummer. 3 . — S. 215–221 . - doi : 10.1016/S0166-218X(00)00178-5 . .
  39. ↑ Seth M. Malitz. Grafer med E -kanter har sidnummer O (√ E ) // Journal of Algorithms : journal. - 1994. - Juli ( vol. 17 , nummer 1 ). — s. 71–84 . - doi : 10.1006/jagm.1994.1027 .
  40. ↑ Seth M. Malitz. Genus g -grafer har sidnummer O (√ g ) // Journal of Algorithms. - 1994. - T. 17 , nr. 1 . — S. 85–109 . - doi : 10.1006/jagm.1994.1028 . .
  41. ↑ R. Blankenship. Bokinbäddningar av grafer. — Institutionen för matematik, Louisiana State University, 2003. . Som citerats av Neshetri.
  42. ↑ János Barát, Jiří Matoušek, David R. Wood. Grafer med avgränsade grader har godtyckligt stor geometrisk tjocklek // Electronic Journal of Combinatorics. - 2006. - T. 13 , nr. 1 . — C. R3 . .
  43. ↑ 1 2 Vida Dujmovic, Anastasios Sidiropoulos, David R. Wood. 3-monotone expanderare. - arXiv : 1501.05020 . , en förbättring jämfört med ett tidigare resultat av Jean Bourgain. Expanderare och dimensionell expansion // Comptes Rendus Mathematique. - 2009. - T. 347 , nr. 7-8 . — S. 357–362 . - doi : 10.1016/j.crma.2009.02.009 . ; Jean Bourgain, Amir Yehudayoff. Expansion i och monotona expanderare // Geometrisk och funktionell analys. - 2013. - T. 23 , nr. 1 . — S. 1–41 . - doi : 10.1007/s00039-012-0200-9 . . Se även Zvi Gali, Ravi Kannan, Endre Szemerédi. På 3-pushdown-grafer med stora separatorer  // Combinatorica. - 1989. - T. 9 , nr. 1 . — S. 9–19 . - doi : 10.1007/BF02122679 . ; Zeev Dvir, Avi Wigderson. Monotone expanderare: konstruktioner och tillämpningar // Theory of Computing. - 2010. - T. 6 . — S. 291–308 . - doi : 10.4086/toc.2010.v006a012 . .
  44. ↑ Lenwood S. Heath, Arnold L. Rosenberg. Lägga ut grafer med hjälp av köer // SIAM Journal on Computing. - 1992. - T. 21 , nr. 5 . — S. 927–958 . - doi : 10.1137/0221055 . .
  45. ↑ Vida Dujmovic, David R. Wood. Om linjära layouter av grafer // Diskret matematik & teoretisk datavetenskap. - 2004. - T. 6 , nr. 2 . — S. 339–357 . .
  46. ↑ 1 2 3 4 Masuda et al, 1990 , sid. 124–127.
  47. ↑ MR Garey, DS Johnson, GL Miller, CH Papadimitriou. Komplexiteten i att färga cirkulära bågar och ackord // SIAM Journal on Algebraic and Discrete Methods. - 1980. - Vol. 1 , nummer. 2 . — S. 216–227 . - doi : 10.1137/0601025 . .
  48. ↑ 1 2 3 Hong, Nagamochi, 2009 .
  49. ↑ Patrizio Angelini, Marco Di Bartolomeo, Giuseppe Di Battista. Grafritning: 20th International Symposium, GD 2012, Redmond, WA, USA, 19–21 september 2012, Revised Selected Papers. - Springer, 2013. - T. 7704. - S. 79–89. — (Föreläsningsanteckningar i datavetenskap). - doi : 10.1007/978-3-642-36763-2_8 . .
  50. ↑ Nešetřil, Ossona de Mendez, 2008 , s. 777–791.
  51. ↑ Nešetřil, Ossona de Mendez, 2012 , Corollary 18.1, sid. 401.
  52. ↑ Nešetřil, Ossona de Mendez, 2012 , Theorem 18.7, sid. 405.
  53. ↑ Donald E. Knuth. Konsten att programmera vol. 1 . - Boston: Addison-Wesley, 1968. - ISBN 0-201-89683-4 . .
  54. ↑ 12 Angelini et al, 2012 , s. 150–172.
  55. ↑ 12 Wood , 2002 , s. 312–327.
  56. ↑ Thomas L. Saaty. Minsta antal korsningar i kompletta grafer // Proceedings of the National Academy of Sciences of the United States of America . - 1964. - T. 52 . — S. 688–690 . - doi : 10.1073/pnas.52.3.688 . .
  57. ↑ TAJ Nicholson. Permutationsförfarande för att minimera antalet korsningar i ett nätverk // Proceedings of the Institution of Electrical Engineers. - 1968. - T. 115 . — S. 21–26 . - doi : 10.1049/piee.1968.0004 . .
  58. ↑ Miki Miyauchi. Topologisk bokinbäddning av tvådelade grafer  (engelska)  // IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences. - 2006. - Vol. E89-A , iss. 5 . — S. 1223–1226 . - doi : 10.1093/ietfec/e89-a.5.1223 .
  59. ↑ Francesco Giordano, Giuseppe Liotta, Tamara Mchedlidze, Antonios Symvonis. Algoritmer och beräkningar: 18th International Symposium, ISAAC 2007, Sendai, Japan, 17–19 december 2007, Proceedings. - Springer, 2007. - T. 4835. - S. 172-183. — (Föreläsningsanteckningar i datavetenskap). - doi : 10.1007/978-3-540-77120-3_17 . .
  60. ↑ Hongmei He, Ondrej Sykora. Proceedings of the Workshop on Information Technologies – Applications and Theory (ITAT), Slovakien, 15–19 september 2004. - 2004. .
  61. ↑ Farhad Shahrokhi, Ondrej Sýkora, László A. Székely, Imrich Vrt'o. Graph-Theoretic Concepts in Computer Science: 20th International Workshop, WG '94, Herrsching, Tyskland, 16–18 juni 1994, Proceedings. - Springer, 1995. - T. 903. - S. 256-268. — (Föreläsningsanteckningar i datavetenskap). - doi : 10.1007/3-540-59071-4_53 . .
  62. ↑ Michael J. Bannister, David Eppstein, Joseph A. Simons. Grafritning: 21st International Symposium, GD 2013, Bordeaux, Frankrike, 23–25 september 2013, Revised Selected Papers. - 2013. - T. 8242. - S. 340-351. — (Föreläsningsanteckningar i datavetenskap). - doi : 10.1007/978-3-319-03841-4_30 . .
  63. ↑ Guillaume Blin, Guillaume Fertin, Irena Rusu, Christine Sinoquet. Kombinatorik, algoritmer, probabilistiska och experimentella metoder: First International Symposium, ESCAPE 2007, Hangzhou, Kina, 7-9 april 2007, Revised Selected Papers. - 2007. - T. 4614. - S. 140-151. — (Föreläsningsanteckningar i datavetenskap). - doi : 10.1007/978-3-540-74450-4_13 . .
  64. ↑ Peter Clote, Stefan Dobrev, Ivan Dotu, Evangelos Kranakis, Danny Krizanc, Jorge Urrutia. På sidnumret av RNA sekundära strukturer med pseudoknoter // Journal of Mathematical Biology. - 2012. - T. 65 , nr. 6–7 . - S. 1337-1357 . - doi : 10.1007/s00285-011-0493-6 . .
  65. ↑ A. Pavan, Raghunath Tewari, NV Vinodchandran. Om kraften i entydighet i log-utrymme // Computational Complexity. - 2012. - T. 21 , nr. 4 . — S. 643–670 . - doi : 10.1007/s00037-012-0047-3 . .
  66. ↑ Zvi Galil, Ravi Kannan, Endre Szemerédi. Om icke-triviala separatorer för k-sidors grafer och simuleringar av icke-deterministiska Turing-maskiner med ett band // Journal of Computer and System Sciences. - 1989. - T. 38 , nr. 1 . — S. 134–149 . - doi : 10.1016/0022-0000(89)90036-6 . .

Litteratur