Whitney planaritetskriteriet är en matroidbeskrivning av plana grafer . Kriteriet är uppkallat efter Hassler Whitney [1] . Kriteriet anger att en graf G är plan om och endast om dess grafiska matroid också är cograph (det vill säga den är den dubbla matroiden en annan grafisk matroid).
I termer av ren grafteori kan detta kriterium formuleras på följande sätt: det måste finnas en annan (dubbel) graf G '=( V ', E ') och en bijektiv överensstämmelse mellan kanterna E ' och kanterna E på den ursprungliga grafen G sådan att en delmängd T av kanterna E bildar ett spännträd i grafen G om och endast om kanterna som motsvarar komplementet av uppsättningen E - T bildar ett spännträd för grafen G '.
Det finns andra kriterier för planaritet , till exempel Pontryagin-Kuratovsky-satsen .
En likvärdig form av Whitneys kriterium säger att en graf G är plan om och endast om den har en dubbel graf vars grafiska matroid är dubbel med den grafiska matroiden för G. En graf vars grafiska matroid är dubbel till den grafiska matroiden av G är känd som den algebraiska dual av G. Sedan kan Whitneys planaritetskriterium omformuleras enligt följande: en graf är plan om och endast om den har en algebraiskt dubbel graf.
Om en graf är inbäddad i en topologisk yta, såsom ett plan, så att varje inbäddningsyta är en topologisk skiva, så definieras den dubbla inbäddningsgrafen som en graf (i vissa fall en multigraf ) H som har en vertex för varje inbäddningsyta och en kant för varje par av intilliggande ytor. Enligt Whitney-kriteriet är följande villkor likvärdiga:
Det är möjligt att definiera dubbla grafer för en graf inbäddad i icke-plana ytor som en torus, men sådana dubbla grafer har i allmänhet inte den överensstämmelse med skärningar, cykler och spännträd som krävs av Whitney-kriteriet.