Planarisering

Inom det matematiska området grafteori är planarisering en metod för att utöka grafritningsmetoder från plana grafer till grafer som inte är plana, genom att bädda in de icke-planära graferna i en större plan graf .

Planarisering kan utföras genom att använda vilken metod som helst för att hitta en ritning (med korsningar) för den givna grafen, och sedan ersätta varje korsningspunkt med en ny konstgjord vertex , vilket gör att varje korsad kant delas in i en bana . Den ursprungliga grafen kommer att representeras som en nedsänkning av dess planarisering.

I inkrementell planarisering är planariseringsprocessen uppdelad i två steg. Först hittas en stor plan subgraf inom den givna grafen. Sedan läggs de återstående kanterna som inte redan är en del av denna subgraf tillbaka en i taget och dirigeras genom en inbäddning av den plana subgrafen. När en av dessa kanter korsar en redan inbäddad kant ersätts de två kanterna som korsar av tvåkantsbanor, med en ny konstgjord vertex som representerar korsningspunkten placerad i mitten av båda banorna. I vissa fall läggs ett tredje lokalt optimeringssteg till planariseringsprocessen, där kanter med många korsningar tas bort och återläggs i ett försök att förbättra planariseringen.

Hitta den största plana subgrafen

Att använda inkrementell planarisering för grafritning är mest effektivt när det första steget i processen hittar en så stor plan graf som möjligt. Tyvärr är det NP-hårt att hitta den plana subgrafen med maximalt möjliga antal kanter (det maximala plana subgrafproblemet ) och MaxSNP-hårt , vilket antyder att det förmodligen inte finns en polynomtidsalgoritm som löser problemet exakt eller som approximerar det godtyckligt bra.

I en n -vertex ansluten graf har den största plana subgrafen högst 3 n − 6 kanter, och varje spännande träd bildar en plan subgraf med n − 1 kanter. Således är det lätt att approximera den maximala plana subgrafen inom ett approximationsförhållande på en tredjedel, helt enkelt genom att hitta ett spännträd. Ett bättre approximationsförhållande, 9/4, är känt, baserat på en metod för att hitta ett stort partiellt 2-träd som en subgraf till den givna grafen. Alternativt, om det förväntas att den plana subgrafen kommer att inkludera nästan alla kanterna på den givna grafen, vilket bara lämnar ett litet antal k icke-plana kanter för den inkrementella planariseringsprocessen, då kan man lösa problemet exakt genom att använda en fast -parameter hanteringsbar algoritm vars körtid är linjär i grafstorleken men icke-polynom i parametern k . Problemet kan också lösas exakt med en gren- och skäralgoritm , utan garantier för körtid, men med bra prestanda i praktiken. Denna parameter k är känd som skevheten i grafen.

Det har också gjorts en del studier av ett relaterat problem, att hitta den största planinducerade subgrafen i en given graf. Återigen, detta är NP-hårt, men med fasta parametrar hanteras när alla utom ett fåtal hörn tillhör den inducerade subgrafen. Edwards & Farr (2002) visade en snäv gräns på 3 n /(Δ + 1) på storleken av den största planinducerade subgrafen, som en funktion av n , antalet hörn i den givna grafen och Δ, dess maximala grad ; deras bevis leder till en polynomisk tidsalgoritm för att hitta en inducerad subgraf av denna storlek.

Lägga till kanter till en planarisering

När en stor plan subgraf har hittats fortsätter den inkrementella planariseringsprocessen genom att betrakta de återstående kanterna en efter en. När den gör det upprätthåller den en planarisering av subgrafen som bildas av kanterna som redan har beaktats. Den lägger till varje ny kant till en plan inbäddning av denna subgraf, bildar en ritning med korsningar, och ersätter sedan varje korsningspunkt med en ny konstgjord vertex som delar upp de två kanterna som korsar. I vissa versioner av denna procedur är ordningen för att lägga till kanter godtycklig, men det är också möjligt att välja ordningen att vara en slumpmässig permutation , köra samma algoritm flera gånger och returnera den bästa planariseringen som den hittar.

I den enklaste formen av denna process tillåts inte den plana inbäddningen av den planariserade subgrafen att ändras medan nya kanter läggs till. För att lägga till varje ny kant på ett sätt som minimerar antalet korsningar den bildar, kan man använda en kortaste vägalgoritm i den dubbla grafen för den aktuella inbäddningen, för att hitta den kortaste sekvensen av ytor av inbäddningen och kanter till korsas som förbinder den nya kantens ändpunkter med varandra. Denna process tar polynomtid per kant.

Att fixa inbäddningen av den planariserade subgrafen är inte nödvändigtvis optimal när det gäller antalet korsningar som blir resultatet. Faktum är att det finns grafer som bildas genom att lägga till en kant till en plan subgraf, där den optimala ritningen bara har två korsningar men där fixering av den plana inbäddningen av subgrafen tvingar fram ett linjärt antal korsningar. Som en kompromiss mellan att hitta den optimala planariseringen av en plan subgraf plus en kant, och att behålla en fast inbäddning, är det möjligt att söka över alla inbäddningar av den planariserade subgrafen och hitta den som minimerar antalet korsningar som bildas av den nya kanten.