Boka inbäddning - Book embedding
Inom grafteori är en bokinbäddning en generalisering av plan inbäddning av en graf till inbäddningar i en bok , en samling halvplan som alla har samma linje som deras gräns. Vanligtvis krävs att hörn i grafen ligger på denna gränslinje, kallad ryggraden , och kanterna krävs för att hålla sig inom ett enda halvplan. Den bok tjocklek av ett diagram är den minsta möjliga antal halvplan för varje bok inbäddning av grafen. Boktjocklek kallas också sidnummer , stacknummer eller fast yttertjocklek . Bokinbäddningar har också använts för att definiera flera andra grafinvarianter, inklusive sidbredd och bokövergångsnummer.
Varje graf med n hörn har högst boktjocklek , och denna formel ger den exakta boktjockleken för kompletta grafer . Graferna med boktjocklek ett är de yttre plana graferna . Graferna med boktjocklek högst två är de subhamiltoniska graferna , som alltid är plana ; mer allmänt har varje plan graf högst fyra tjocklekar. Alla mindre stängda graffamiljer , och i synnerhet graferna med begränsad trädbredd eller begränsat släkte , har också begränsad boktjocklek. Det är NP-svårt att bestämma den exakta boktjockleken för en given graf, med eller utan att veta en fast toppunkt som ordnar längs bokens ryggrad.
En av de ursprungliga motivationerna för att studera bokinbäddningar involverade applikationer inom VLSI -design, där hörnen på en bokinbäddning representerar komponenter i en krets och trådarna representerar förbindelser mellan dem. Bokinbäddning har också applikationer inom grafritning , där två av de vanliga visualiseringsstilarna för grafer, bågdiagram och cirkulära layouter kan konstrueras med hjälp av bokinbäddningar.
I transportplanering kan de olika källorna och destinationerna för fot- och fordonstrafik som möts och interagerar vid ett trafikljus matematiskt modelleras som hörn i en graf, med kanter som förbinder olika käll-destination-par. En bok som bäddar in denna graf kan användas för att utforma ett schema som låter all trafik röra sig över korsningen med så få signalfaser som möjligt. I bioinformatikproblem som involverar RNA -vikningsstrukturen representerar enkelsidiga bokinbäddningar klassiska former av nukleinsyras sekundära struktur och tvåsidiga bokinbäddningar representerar pseudoknoter . Andra tillämpningar av bokinbäddningar inkluderar abstrakt algebra och knutteori .
Det finns flera öppna problem när det gäller boktjocklek. Det är okänt om boktjockleken för ett godtyckligt diagram kan begränsas av en funktion av boktjockleken för dess underavdelningar . Att testa förekomsten av en tre sidor lång inbäddning av en graf, med tanke på en fast ordning av hörnen längs ryggraden av inbäddningen, har okänd beräkningskomplexitet: det är varken känt att det kan lösas på polynomtid eller är känt för att vara NP-hårt .
Historia
Föreställningen om en bok, som ett topologiskt utrymme, definierades av CA Persinger och Gail Atneosen på 1960 -talet. Som en del av detta arbete övervägde Atneosen redan inbäddning av grafer i böcker. De inbäddningar han studerade använde samma definition som inbäddningar av grafer i något annat topologiskt utrymme: hörn representeras av distinkta punkter, kanter representeras av kurvor och det enda sättet som två kanter kan skärs av är att de möts vid en gemensam slutpunkt.
I början av 1970 -talet utvecklade Paul C. Kainen och L. Taylor Ollmann en mer begränsad typ av inbäddning som kom att användas i de flesta efterföljande undersökningar. I sin formulering måste grafens hörn placeras längs med ryggraden i boken, och varje kant måste ligga på en enda sida. Viktiga milstolpar i den senare utvecklingen av bokinbäddningar inkluderar beviset från Mihalis Yannakakis i slutet av 1980 -talet på att plana grafer har boktjocklek som högst fyra, och upptäckten i slutet av 1990 -talet av nära samband mellan bokinbäddningar och bioinformatik .
Definitioner
En bok är en särskild typ av topologiskt utrymme , även kallat ett fan av halvplan. Den består av en enda rad ℓ , kallad ryggraden eller baksidan av boken, tillsammans med en samling av ett eller flera halvplan , kallade bokens sidor eller blad , var och en med ryggraden som gräns. Böcker med ett begränsat antal sidor kan bäddas in i tredimensionellt utrymme, till exempel genom att välja ℓ för att vara z- axeln för ett kartesiskt koordinatsystem och välja sidorna som de k- halvplanen vars dihedrala vinkel i förhållande till xz -plan är en heltalsmultipel av 2 π / k .
En bokritning av ett ändligt diagram G på en bok B är en ritning av G på B så att varje toppunkt av G ritas som en punkt på B -ryggraden och varje kant av G ritas som en kurva som ligger inom en enda sida av B . Den k -sida Bookcrossing antal av G är det lägsta antalet korsningar i en k -sida bok ritning.
En bok inbäddning av G på B är en bok ritningen att bildar en graf inbäddning av G till B . Det vill säga det är en bokritning av G på B som inte har några kantkorsningar. Varje ändlig graf har en bok inbäddad i en bok med ett tillräckligt stort antal sidor. Till exempel är det alltid möjligt att bädda in varje kant i grafen på sin egen separata sida. Den bok tjocklek , sidnummer , eller stapel antal av G är det lägsta antalet sidor som krävs för en bok inbäddning av G . En annan parameter som mäter kvaliteten på en inbäddning av en bok, utöver dess antal sidor, är dess sidbredd . Detta är det maximala antalet kanter som kan korsas av en stråle vinkelrätt mot ryggraden inom en enda sida. På motsvarande sätt (för bokinbäddningar där varje kant ritas som en monoton kurva) är det den maximala storleken på en delmängd av kanter inom en enda sida så att intervallerna som definieras på ryggraden av par med ändpunkter i kanterna alla skär varandra .
Det är avgörande för dessa definitioner att kanterna bara får ligga inom en enda sida av boken. Som Atneosen redan observerat, om kanter istället kan passera från en sida till en annan över ryggraden i boken, kan varje graf vara inbäddad i en tre sidor lång bok. För en sådan tre sidor hög topologisk inbäddning där ryggradskorsningar är tillåtna kan varje graf bäddas in med högst ett logaritmiskt antal ryggradskryssningar per kant, och vissa grafer behöver så många ryggradskorsningar.
Specifika grafer
Så som visas i den första figuren, boken tjockleken av den fullständiga grafen K 5 är tre: som en icke-plan graf dess bok tjocklek är större än två, men en bok inbäddning med tre sidor finns. Mer allmänt är boktjockleken för varje komplett graf med n ≥ 4 hörn exakt . Detta resultat ger också en övre gräns för den maximala boktjockleken för alla n -vertexgrafer.
Det tvåsidiga korsningsnumret för hela grafen K n är
matcha en fortfarande obevisad gissning av Anthony Hill om vad det obegränsade korsningsnumret för denna graf ska vara. Det vill säga, om Hills gissning är korrekt, är ritningen av denna graf som minimerar antalet korsningar en tvåsidig ritning.
Boktjockleken för den fullständiga bipartitgrafen K a , b är högst min ( a , b ) . För att konstruera en ritning med denna boktjocklek, för varje hörn på den mindre sidan av delningen, kan man placera kanterna som infaller med den hörnet på sin egen sida. Denna gräns är inte alltid stram; till exempel har K 4,4 boktjocklek tre, inte fyra. Men när grafens två sidor är mycket obalanserade, med b > a ( a - 1) , är boktjockleken för K a , b exakt a .
För Turán -grafen T ( kr , r ) (en komplett flerdelad graf K k , k , ... bildad av r oberoende uppsättningar av k hörn per oberoende uppsättning, med en kant mellan varannan hörn från olika oberoende uppsättningar) boktjockleken t är inklämt mellan
och när r är udda kan den övre gränsen förbättras till
Boktjockleken för binära de Bruijn-grafer , shuffle-exchange-grafer och kubkopplade cykler (när dessa grafer är tillräckligt stora för att vara icke-plana) är exakt tre.
Egenskaper
Planaritet och yttre planaritet
Boktjockleken för en given graf G är högst en om och bara om G är en yttre plan graf . En yttre plan graf är en graf som har en plan inbäddning där alla hörn hör till inbäddningens yttre yta. För en sådan graf ger placeringen av hörnen i samma ordning längs ryggraden som de visas i ytterytan en bok på en sida som bäddar in det givna diagrammet. (En artikuleringspunkt i grafen kommer nödvändigtvis att visas mer än en gång i den cykliska ordningen av hörn runt ytterytan, men endast en av dessa kopior bör ingå i bokens inbäddning.) Omvänt är en en-sidig inbäddning automatiskt en yttre plan inbäddning. Om en graf är inbäddad på en enda sida och ett annat halvplan är fäst vid ryggraden för att förlänga sidan till ett komplett plan, så inkluderar inbäddningens yttre yta hela det tillagda halvplanet, och alla hörn ligger på detta yttre ansikte.
Varje tvåsidig bokinbäddning är ett specialfall av en plan inbäddning, eftersom föreningen av två sidor i en bok är ett utrymme topologiskt ekvivalent med hela planet. Därför är varje graf med boktjocklek två automatiskt en plan graf . Mer exakt är boktjockleken för en graf G högst två om och bara om G är en delgraf av en plan graf som har en Hamiltonisk cykel . Om en graf får en inbäddning på två sidor kan den utökas till en plan Hamiltonsk graf genom att lägga till (på valfri sida) extra kanter mellan två på varandra följande hörn längs ryggraden som inte redan ligger intill, och mellan den första och sista ryggraden hörn. Den Goldner-Harary graf ger ett exempel på en plan kurva som inte har boken tjocklek två: det är en maximal planär graf , så det är inte möjligt att lägga till några kanter till det samtidigt bevara planhet, och det har inte en Hamiltoncykel . På grund av denna karaktärisering av Hamiltoniska cykler, är grafer som har tvåsidiga bokinbäddningar också kända som subhamiltoniska grafer .
Alla plana grafer vars högsta grad är högst fyra har boktjocklek högst två. Plana 3-träd har boktjocklek högst tre. Mer allmänt har alla plana grafer boktjocklek fyra. Det har hävdats av Mihalis Yannakakis 1986 att det finns några plana grafer som har boktjocklek exakt fyra. Ett detaljerat bevis på detta påstående, som meddelades i ett efterföljande tidningspapper, var dock inte känt förrän 2020, då Bekos et al. presenterade plana grafer med trebredd 4 som kräver fyra sidor i vilken bokinbäddning som helst.
Beteende under underavdelningar
Kan boktjockleken på en graf övergränsas av en funktion av boktjockleken i dess underavdelning?
Att dela upp varje kant i en graf i tvåkantiga banor genom att lägga till nya hörn inom varje kant kan ibland öka dess boktjocklek. Till exempel, den diamantgraf har bok tjocklek ena (det är outerplanar) men dess underindelning har bok tjocklek två (det är plant och subhamiltonian men inte outerplanar). Emellertid kan denna indelningsprocess ibland också avsevärt minska boktjockleken för den uppdelade grafen. Till exempel är boktjockleken för den fullständiga grafen K n proportionell mot dess antal hörn, men att dela upp var och en av dess kanter i en tvåkantig bana ger en underavdelning vars boktjocklek är mycket mindre, bara . Trots att det finns exempel som denna, Blanken & Oporowski (1999) gissade att en underavdelning bok tjocklek kan vara för mycket mindre än den ursprungliga grafen. Specifikt gissade de att det finns en funktion f så att för varje graf G och för grafen H som bildas genom att ersätta varje kant i G med en tvåkantig bana, om boktjockleken för H är t så är boktjockleken för G är högst f ( t ) . Från och med 2013 förblir gissningen Blankenship – Oporowski obevisad.
Relation till andra grafinvarianter
Boktjocklek är relaterad till tjocklek , antalet plana grafer som behövs för att täcka kanterna på det givna diagrammet. En graf G har tjocklek θ om den kan ritas i planet, och dess kanter färgas med θ färger, på ett sådant sätt att kanter med samma färg som varandra inte korsas. Analogt har en graf G boktjocklek θ om den kan ritas i ett halvplan , med dess hörn på gränsen för halvplanet, med kanterna färgade med θ färger utan att korsa mellan två kanter av samma färg. I denna formulering av boktjocklek motsvarar kanternas färger sidorna i bokens inbäddning. Tjocklek och boktjocklek kan dock vara väldigt olika från varandra: det finns grafer ( underavdelningar av kompletta grafer ) som har obegränsad boktjocklek, trots att de har tjocklek två.
Grafer över trädbredden k har högst boktjocklek k + 1 och denna gräns är tätt för k > 2 . Grafer med m -kanter har boktjocklek och grafer av släktet g har boktjocklek . Mer generellt har varje mindre stängd graffamilj begränsat boktjockleken. Å andra sidan har de 1-plana graferna , som inte är stängda under minderåriga, också begränsat boktjocklek, men några 1-plana grafer inklusive K 2,2,2,2 har boktjocklek minst fyra.
Varje ytlig minor i en graf med begränsad boktjocklek är en gles graf , vars förhållande mellan kanter och hörn begränsas av en konstant som endast beror på minorens djup och på boktjockleken. Det vill säga i terminologin hos Nešetřil & Ossona de Mendez (2012) har graferna över begränsad boktjocklek begränsat expansionen . Men även graferna med begränsad grad , ett mycket starkare krav än att ha begränsad expansion, kan ha obegränsad boktjocklek.
Eftersom grafer med boktjocklek två är plana grafer, följer de planavgränsningssatsen : de har separatorer, delmängder av hörn vars borttagning delar grafen i bitar med högst 2 n /3 hörn vardera, med endast hörn i avgränsaren. Här hänvisar n till antalet hörn i grafen. Det finns emellertid grafer över boktjocklek tre som inte har separatorer med sublinjär storlek.
Kanterna på en enda sida av en inbäddning av en bok beter sig på vissa sätt som en stapeldatastruktur . Detta kan formaliseras genom att betrakta en godtycklig sekvens av push- och popoperationer på en stapel och bilda en graf där stapeloperationerna motsvarar grafens hörn, placerade i sekvensordning längs ryggraden i en bokinbäddning. Om man sedan ritar en kant från varje popoperation som lägger ett objekt x från stapeln till den föregående push-operationen som tryckte x , kommer den resulterande grafen automatiskt att ha en inbäddning på en sida. Av denna anledning har sidnumret i en graf också kallats dess stacknummer . På samma sätt kan man överväga en godtycklig sekvens av enqueue och dequeue -operationer i en ködatastruktur och bilda en graf som har dessa operationer som sina hörn, placerade i ordning på ryggraden på en enda sida, med en kant mellan varje enqueue -drift och motsvarande dequeue. Sedan, i denna graf, kommer var och en av kanterna att antingen korsa eller täcka oskiljaktiga intervall på ryggraden. Analogt sett har forskare definierat att en köinbäddning av en graf är en inbäddning i en topologisk bok så att varje hörn ligger på ryggraden, varje kant ligger på en enda sida och varje två kanter på samma sida antingen korsar eller täcker disjoint intervall på ryggraden. Det minsta antal sidor som behövs för att en kö ska bädda in en graf kallas dess könummer .
Beräkningskomplexitet
Att hitta boktjockleken på en graf är NP-svår . Detta följer av det faktum att det är NP-komplett att hitta Hamiltonian-cykler i maximala plana grafer . I en maximal plan graf är boktjockleken två om och bara om det finns en Hamiltonisk cykel. Därför är det också NP-komplett att testa om boktjockleken för en given maximal plan graf är två.
Om en ordning av hörn i en graf längs ryggraden i en inbäddning är fixerad, kan en inbäddning på två sidor (om den existerar) hittas i linjär tid , som en instans av planaritetstestning för en graf som bildas genom att förstärka den givna diagram med en cykel som förbinder hörnen i deras ryggrad. Unger (1992) hävdade att att hitta tresidiga inbäddningar med en fast ryggradsservering också kan utföras under polynomtid, även om hans uppskrivning av detta resultat utelämnar många detaljer. För grafer som kräver fyra eller fler sidor förblir dock problemet med att hitta en inbäddning med minsta möjliga antal sidor NP-hårt, via en ekvivalens till NP-hårda problemet med att måla cirkeldiagram , skärningskurvorna för ackord i en cirkel . Givet en graf G med en fast ryggrad beställning av dess hörn, dra dessa hörn i samma ordning runt en cirkel och dra kanterna av G som linjesegment producerar en samling av ackord representerar G . Man kan sedan bilda ett cirkeldiagram som har ackorden i detta diagram som hörn och korsande ackord som kanter. En färgning av cirkeldiagrammet representerar en uppdelning av kanterna på G i delmängder som kan ritas utan att korsas på en enda sida. Därför motsvarar en optimal färgning en optimal inbäddning av böcker. Eftersom cirkeldiagramfärgning med fyra eller fler färger är NP-hård och eftersom alla cirkeldiagram kan bildas på detta sätt från något bokinbäddningsproblem, följer det att optimal bokinbäddning också är NP-hård. För en fast toppunktsbeställning på ryggraden i en tvåsidig bokritning är det också NP-svårt att minimera antalet korsningar när detta nummer är noll.
Om ryggradens ordning är okänd men en uppdelning av kanterna på två sidor ges, är det möjligt att hitta en inbäddning på två sidor (om den finns) i linjär tid av en algoritm baserad på SPQR-träd . Det är dock NP-komplett att hitta en inbäddning på två sidor när varken ryggraden eller kantpartitionen är känd. Att hitta bokens korsningsnummer i en graf är också NP-svårt, på grund av NP-fullständigheten i det speciella fallet att testa om det 2-sidiga korsningsnumret är noll.
Som en konsekvens av begränsad expansion kan subgrafens isomorfismproblem , att hitta om ett mönsterdiagram med begränsad storlek existerar som en undergraf av en större graf, lösas i linjär tid när den större grafen har begränsat boktjockleken. Detsamma gäller för att upptäcka om mönsterdiagrammet är en inducerad delgraf av den större grafen, eller om den har en grafhomomorfism till den större grafen. Av samma skäl, problemet med att testa om en graf av avgränsas bok tjockleks lyder en given formel av första ordningens logik är fast-parametern lätthanterlig .
Bekos, Kaufmann & Zielke (2015) beskriver ett system för att hitta optimala inbäddningar av böcker genom att omvandla problemet till en instans av det booleska tillfredsställelsesproblemet och tillämpa en SAT -lösare på det resulterande problemet. De uppger att deras system kan hitta en optimal inbäddning för 400-vertex maximala plana grafer på ungefär 20 minuter.
Ansökningar
Feltolerant multiprocessering
En av de främsta motiveringarna för att studera inbäddning av bok som citeras av Chung, Leighton & Rosenberg (1987) innefattar en applikation i VLSI- design, för att organisera fel-toleranta multiprocessorer . I DIOGENES -systemet som utvecklats av dessa författare är CPU: erna i ett multiprocessorsystem anordnade i en logisk sekvens som motsvarar ryggraden i en bok (även om denna sekvens kanske inte nödvändigtvis placeras längs en linje i det systemets fysiska layout ). Kommunikationslänkar som förbinder dessa processorer grupperas i "buntar" som motsvarar sidorna i en bok och fungerar som staplar : att ansluta en av processorerna till starten av en ny kommunikationslänk driver alla tidigare länkar uppåt i bunten och ansluta en annan processorn till slutet av en kommunikationslänk ansluter den till den längst ner i bunten och dyker upp alla andra. På grund av detta stackbeteende kan ett enda paket hantera en uppsättning kommunikationslänkar som bildar kanterna på en enda sida i en inbäddning av en bok. Genom att organisera länkarna på detta sätt kan en mängd olika nätverkstopologier implementeras, oavsett vilka processorer som har blivit felaktiga, så länge tillräckligt med icke-defekta processorer återstår för att implementera nätverket. Nätverkstopologierna som kan implementeras av detta system är exakt de som har boktjocklek högst lika med antalet buntar som har gjorts tillgängliga. Bokinbäddning kan också användas för att modellera placeringen av ledningar som ansluter VLSI -komponenter till lagren i en krets.
Stacksortering
En annan applikation citerad av Chung, Leighton & Rosenberg (1987) gäller sortering av permutationer med hjälp av staplar . Ett inflytelserikt resultat av Donald Knuth ( 1968 ) visade att ett system som bearbetar en dataström genom att trycka inkommande element på en stapel och sedan, vid lämpligt valda tider, poppa dem från stapeln till en utdataström kan sortera data om och bara om dess ursprungliga ordning beskrivs av en permutation som undviker permutationsmönstret 231. Sedan dess har det varit mycket arbete med liknande problem med att sortera dataströmmar efter mer allmänna system av staplar och köer. I systemet som behandlas av Chung, Leighton & Rosenberg (1987) måste varje element från en ingångsdataström skjutas in på en av flera staplar. Sedan, när all data har pushats på detta sätt, läggs objekten från dessa staplar (i lämplig ordning) på en utdataström. Som Chung et al. observera, en given permutation kan sorteras av detta system om och bara om en viss graf, härledd från permutationen, har en bok inbäddad med hörnen i en viss fast ordning längs ryggraden och med ett antal sidor som är högst lika till antalet staplar.
Trafik kontroll
Som Kainen (1990) beskrev kan en bokinbäddning användas för att beskriva faserna av en trafiksignal vid en kontrollerad korsning. Vid en korsning kan inkommande och utgående trafikfält (inklusive ändarna av övergångsställen och cykelbanor samt körfält för motorfordon) representeras som hörnen i en graf, placerad på ryggraden i en bok som inbäddas i deras medurs beställning runt korsningen. Banorna genom korsningen som trafiken tar för att komma från ett inkommande körfält till ett utgående körfält kan representeras som kanterna på en oriktad graf. Till exempel kan den här grafen ha en kant från ett inkommande till ett utgående trafikfält som båda tillhör samma vägsegment, vilket representerar en U-sväng från det segmentet tillbaka till det segmentet, bara om U-svängar är tillåtna vid korsning. För en given delmängd av dessa kanter representerar delmängden en samling vägar som alla kan passeras utan störningar från varandra om och bara om delmängden inte innehåller några kanterpar som skulle korsas om de två kanterna placerades i en enda sida i en inbäddning av en bok. Således beskriver en inbäddning av denna graf en delning av vägarna till icke-störande delmängder, och bokens tjocklek (med dess fasta inbäddning på ryggraden) ger det minsta antalet distinkta faser som behövs för ett signaleringsschema som inkluderar alla möjliga trafikvägar genom korsningen.
Diagramritning
Bokinbäddning har också ofta tillämpats vid visualisering av nätverksdata. Två av standardlayouterna i grafritning , bågdiagram och cirkulära layouter kan ses som bokinbäddningar, och bokinbäddning har också tillämpats i konstruktionen av grupperade layouter, samtidiga inbäddningar och tredimensionella diagramritningar.
Ett bågdiagram eller linjär inbäddning placerar hörn av en graf längs en linje och ritar diagrammets kanter som halvcirklar antingen ovanför eller under denna linje, vilket ibland också tillåter kanter att dras på segment av linjen. Denna ritstil motsvarar en bok som bäddar in antingen 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 grafens överskridande antal . Plana grafer som inte har inbäddningar i två sidor kan också ritas på ett liknande sätt genom att låta deras kanter representeras av flera halvcirkler ovanför och under linjen. En sådan teckning är inte en bok som inbäddar enligt den vanliga definitionen, utan har kallats en topologisk bokinbäddning . För varje plant diagram är det alltid möjligt att hitta en sådan inbäddning där varje kant korsar ryggraden högst en gång.
I en annan ritstil, cirkulär layout , hörn i en graf placeras på en cirkel och kanterna ritas antingen inuti eller utanför cirkeln. Återigen motsvarar en placering av kanterna i cirkeln (till exempel som raka linjesegment) en boksritning på en sida, medan en placering både inuti och utanför cirkeln motsvarar en bokboksteckning på två sidor.
För teckningar på en sida av endera stilen är det viktigt att hålla antalet korsningar litet för att minska det visuella röran i ritningen. Minimering av antalet korsningar är NP-komplett , men kan approximeras med ett approximationsförhållande på O (log 2 n ) där n är antalet hörn. Minimering av en sida eller två sidor korsningsnumret är fast-parameter lätthanterlig när parametriseras med cyklomatisk antalet av det givna grafen, eller genom en kombination av korsningen numret och treewidth av grafen. Heuristiska metoder för att minska korsningskomplexiteten har också utformats, baserade på t.ex. en noggrann infogningsordning för vertex och lokal optimering .
Två sidors bokinbäddningar med en fast delning av kanterna i sidor kan tolkas som en form av grupperad planaritet , där den givna grafen måste ritas på ett sådant sätt att delar av grafen (de två delmängderna av kanter) placeras på ritningen på ett sätt som återspeglar deras gruppering. Två sidors bokinbäddning har också använts för att hitta samtidiga inbäddningar av grafer, där två grafer ges på samma hörnuppsättning och man måste hitta en placering för hörnen där båda graferna ritas plant med raka kanter.
Bokinbäddningar med mer än två sidor har också använts för att konstruera tredimensionella ritningar av grafer. I synnerhet använde Wood (2002) en konstruktion för bokinbäddningar som håller graden av varje hörn på varje sida låg, som en del av en metod för att bädda in grafer i ett tredimensionellt rutnät med låg volym.
RNA -vikning
I studien av hur RNA -molekyler viker för att bilda sin struktur kan standardformen för nukleinsyras sekundära struktur beskrivas schematiskt som en baskedja (RNA -sekvensen själv), ritad längs en linje, tillsammans med en samling bågar ovanför linje som beskriver strukturens baspar . Det vill säga, även om dessa strukturer faktiskt har en komplicerad tredimensionell form, kan deras anslutning (när det finns en sekundär struktur) beskrivas av en mer abstrakt struktur, en en-sidig bokinbäddning. Men inte alla RNA -veck uppför sig på detta enkla sätt. Haslinger & Stadler (1999) har föreslagit en så kallad "bi-sekundär struktur" för vissa RNA- pseudoknoter som har formen av en inbäddning på två sidor: RNA-sekvensen ritas igen längs en linje, men basparen ritas som bågar både ovanför och under denna rad. För att bilda en bi-sekundär struktur måste en graf ha högsta graden högst tre: varje bas kan bara delta i en båge i diagrammet, förutom de två länkarna till sina grannar i grundsekvensen. Fördelarna med denna formulering inkluderar fakta att den utesluter strukturer som faktiskt är knutna i rymden, och att den matchar de flesta kända RNA -pseudoknoter.
Eftersom ryggradsbeställningen är känd i förväg för den här applikationen är det enkelt att testa om det finns en bi-sekundär struktur för en given basparning. Problemet med att tilldela kanter till de två sidorna på ett kompatibelt sätt kan formuleras antingen som en instans av 2-tillfredsställelse , eller som ett problem med att testa tvåpartigheten hos cirkeldiagrammet vars hörn är baspar och vars kanter beskriver korsningar mellan baspar. Alternativt och mer effektivt, som Haslinger & Stadler (1999) visar, finns det en bi-sekundär struktur om och bara om diagrammet för ingången (en graf som bildas genom att ansluta baserna till en cykel i sin sekvensordning och lägga till de angivna basparen som kanter) är en plan graf . Denna karakterisering gör att bi-sekundära strukturer kan erkännas i linjär tid som en instans av planaritetstestning .
Blin et al. (2007) använde kopplingen mellan sekundära strukturer och bokinbäddningar som en del av ett bevis på NP-hårdheten hos vissa problem i RNA-sekundärstrukturjämförelse. Och om en RNA-struktur är tertiär snarare än bi-sekundär (det vill säga om det kräver mer än två sidor i diagrammet), är det sedan NP-hårt att bestämma sidnumret.
Beräkningskomplexitetsteori
Pavan, Tewari & Vinodchandran (2012) använde bokinbäddning för att studera beräkningskomplexitetsteorin om tillgänglighetsproblemet i riktade grafer . Som de har observerat kan nåbarhet för tvåsidiga riktade grafer lösas i ett entydigt logaritmiskt utrymme (analogt, för logaritmisk rymdkomplexitet , i klassen UP av entydiga polynomtidsproblem). Tillgänglighet för tre sidor riktade grafer kräver emellertid full effekt av ett icke-bestämt logaritmiskt utrymme . Således verkar inbäddningar i boken intimt kopplade till skillnaden mellan dessa två komplexitetsklasser.
Förekomsten av expandergrafer med konstant sidnummer är det viktigaste steget för att bevisa att det inte finns någon subkvadratisk tidssimulering av icke-deterministiska Turing-maskiner med två band med en-band icke-deterministiska Turing-maskiner.
Andra matematikområden
McKenzie & Overbay (2010) studerar tillämpningar av boktjocklek i abstrakt algebra , med hjälp av grafer definierade från nolldelarna för en ändlig lokal ring genom att göra en toppunkt för varje nollavdelare och en kant för varje par värden vars produkt är noll.
I en sekvens med flera papper har Dynnikov studerat de topologiska inbäddningarna av knutar och länkar , vilket visar att dessa inbäddningar kan beskrivas med en kombinatorisk sekvens av symboler och att den topologiska ekvivalensen av två länkar kan demonstreras genom en sekvens av lokala förändringar av inbäddningarna.