Planární

Planární je termín používaný především v geometrii a teorii grafů. Označuje vlastnost objektu nebo souboru objektů, která umožňuje jejich vložení do roviny tak, aby se jejich prvky – zejména hrany grafu – navzájem nepřekrývaly. V praxi se pojem vztahuje na planární grafy, planární mapy a obecně na rovinné uspořádání geometrických útvarů.

Planární graf je graf, který lze zobrazit na rovině bez překřížení hran. Základní poznání o neplanaritě shrnuje Kuratowského věta: graf je planární právě tehdy, že neobsahuje subdivizi (podgrafovou substanci) grafů K5 nebo K3,3. Eulerova charakteristika pro spojité planární grafy říká, že pokud graf G má počet vrcholů V, hran E a ploch F, pak pro spojitý graf platí V − E + F = 2; pro C komponent platí V − E + F = 1 + C, kdy F zahrnuje i vnější plochu.

Planarity testování: existují algoritmy, které určují planárnost v čase lineárním (např. Hopcroft a Tarjan). Planární objekty se také studují v souvislosti s planárními zobrazeními (embedování) a jejich mapami.

Použití: plánární struktury nacházejí uplatnění v návrhu obvodů a sítí (např. VLSI), kartografii a vizualizaci grafů, kde je důležité zobrazit struktury bez zbytečných průsečíků a srozumitelně vyjádřit jejich spojitost.