V topologické teorii grafů je 1-rovinný graf graf , který lze nakreslit v euklidovské rovině tak, že každá hrana má nanejvýš jeden průsečík pouze s jednou další hranou.
1-rovinné grafy byly poprvé uvažovány Ringelem, který ukázal, že je lze obarvit nejvýše sedmi barvami [1] . Později byl přesný počet barev potřebný k vybarvení těchto grafů (v nejhorším případě) snížen na šest [2] . Příklad úplného grafu K 6 , který je 1-rovinný, ukazuje, že 1-rovinné grafy mohou někdy vyžadovat k vybarvení šest barev. Důkaz dostatku šesti barev však není snadný.
Důvodem Ringelova uvažování o 1-rovinných grafech byl pokus vyřešit variantu úlohy úplného vybarvení pro rovinné grafy , ve které jsou vrcholy a plochy rovinného grafu obarveny tak, že žádné dva sousední vrcholy nemají stejné barva a jakékoli dvě sousední plochy musí být také obarveny různými barvami. Barvy, stejně jako barvy vrcholů a ploch sousedících s nimi, se musí lišit. Je zřejmé, že to lze provést s osmi barvami, pokud použijeme teorém o čtyřech barvách pro graf a jeho duální graf samostatně, pomocí dvou nesouvislých sad čtyř barev. Můžete však získat méně barev, pokud vytvoříte pomocný graf, který má vrchol pro každý vrchol a plochu původního rovinného grafu a ve kterém dva vrcholy pomocného grafu sousedí, pokud odpovídají sousedním objektům daného rovinného grafu. . Vrcholové zbarvení pomocného grafu odpovídá obarvení původního rovinného grafu. Pomocný graf je 1-rovinný, což znamená, že Ringelův problém zbarvení vrcholu a obličeje lze vyřešit pomocí šesti barev [2] . Graf K 6 nelze tímto způsobem získat jako pomocný graf, ale přesto problém barvení vrcholů a ploch někdy vyžaduje šest barev. Pokud například obarvíte rovinný graf trojúhelníkového hranolu , jeho 6 vrcholů + 5 ploch vyžaduje šest barev [3] .
Každý 1-rovinný graf s n vrcholy má nejvýše 4n − 8 hran [4] . Přesněji řečeno, každý výkres 1-rovinného grafu má nejvýše n − 2 průsečíků . Odstraněním jedné hrany z každé protínající se dvojice hran zůstane rovinný graf, který má nejvýše 3n − 6 hran, což okamžitě implikuje limit 4n − 8 hran původního 1-rovinného grafu [5] . Na rozdíl od rovinných grafů (pro které mají všechny maximální rovinné grafy na dané množině vrcholů stejný počet hran) však existují maximální 1 rovinné grafy (grafy, ke kterým nelze přidat hranu při zachování 1 rovinnosti), které mají podstatně méně než 4 n − 8 hran [6] . Vazba 4 n − 8 na maximální možný počet hran v 1-rovinném grafu může být použita k ukázce, že úplný graf K 7 se sedmi vrcholy není 1-rovinný, protože tento graf má 21 hran a pak 4 n − 8 = 20 < 21 [7] .
O 1 rovinném grafu se říká, že je optimálním 1 rovinným grafem , pokud má přesně 4n − 8 hran, což je maximální možný počet. V 1-rovinném vnoření optimálního 1-rovinného grafu, neprotínající se hrany nutně tvoří dlaždici do čtyřúhelníků (tj. tvoří polyedrický graf , ve kterém je každá plocha čtyřúhelník ). Jakýkoli kvadrant generuje 1-rovinný graf přidáním dvou úhlopříček ke každé čtvercové ploše. Z toho vyplývá, že každý optimální 1-rovinný graf je eulerovský (všechny jeho vrcholy mají sudý stupeň ), že nejmenší stupeň v takových grafech je 6 a že každý optimální 1-rovinný graf má alespoň osm vrcholů s přesně šesti stupni. Navíc každý optimální 1-rovinný graf je spojen se 4 vrcholy a každý 4-vrcholový úsek v takovém grafu je řezný cyklus v pod ním ležícím čtyřúhelníku [8] .
Grafy, které mají přímočaré 1-rovinné kresby (tj. kresby, ve kterých je každá hrana reprezentována úsečkou a každý segment protíná nejvýše jedna další hrana), mají o něco silnější vazbu 4 n − 9 na maximálním počtu hran, kterých je dosaženo na nekonečném počtu grafů [9] .
Je známa úplná klasifikace 1-rovinných úplných grafů , úplných bipartitních grafů a obecnějších úplných vícedílných grafů . Jakýkoli úplný bipartitní graf tvaru K 2, n je 1-rovinný, stejně jako jakýkoli úplný tripartitní graf tvaru K 1,1, n . Kromě těchto nekonečných množin jsou kompletní vícedílné 1-rovinné grafy K 6 , K 1,1,1,6 , K 1,1,2,3 , K 2,2,2,2 , K 1,1,1, 2,2 a jejich podgrafy. Minimální kompletní vícedílné grafy , které nejsou 1- rovinné , jsou K3,7 , K4,5 , K1,3,4 , K2,3,3 a K1,1,1,1,3 . Například úplný bipartitní graf K 3,6 je 1-rovinný, protože je podgrafem K 1,1,1,6 , ale K 3,7 není 1-rovinný [7] .
Kontrola, zda je graf 1-rovinný, je NP-úplný [10] [11] a problém zůstává NP-úplný i pro grafy získané z rovinných grafů přidáním jedné hrany [12] a pro grafy omezené šířky [ 13] .
Problém je pevně-parametricky řešitelný , pokud je parametrizován cyklomatickým číslem nebo hloubkou stromu , takže může být vyřešen v polynomiálním čase , pokud jsou tyto parametry omezeny [13] .
Na rozdíl od Fareeho teorému pro rovinné grafy nelze všechny 1-rovinné grafy nakreslit jako 1-rovinné s úsečkami jako hranami [14] [15] . Kontrolu, zda lze nakreslit 1-rovinný graf s rovnými hranami, však lze provést v polynomiálním čase [16] . Navíc každý 1-rovinný graf spojený s vrcholem-3 má 1-rovinnou kresbu, ve které má nejvýše jedna hrana na vnější ploše zalomení . Takový výkres lze sestavit v lineárním čase na základě vložení 1 rovinného grafu [17] . 1-rovinné grafy mají omezenou tloušťku knihy [18] , ale některé 1-rovinné grafy, včetně K 2,2,2,2 , mají tloušťku knihy alespoň čtyři [19] .
1-rovinné grafy mají omezenou místní šířku stromu , což znamená, že existuje (lineární) funkce f taková, že 1-rovinné grafy o průměru d mají šířku stromu nanejvýš f ( d ). Stejná vlastnost platí pro obecnější grafy, které lze vložit do plochy ohraničeného rodu s omezeným počtem průsečíků na hranu. Mají také oddělovače , malou sadu vrcholů, jejichž odstranění rozbije graf na spojené složky, jejichž velikost je konstantní zlomek celého grafu. Na základě těchto vlastností lze řadu algoritmů planárních grafů, jako je technika Brendy Sue Bakerové pro konstrukci aproximačních algoritmů , rozšířit na 1-rovinné grafy. Tato metoda například vede k přibližnému polynomiálnímu časovému schématu pro nalezení největší nezávislé množiny 1-rovinného grafu [20] .
Třída grafů, která je analogická s vnějším rovinným grafem pro 1-planaritu, se nazývá vnější-1-rovinné grafy . Jedná se o grafy, které lze kreslit na disk s vrcholy na hranici disku a s hranami, které mají nejvýše jeden průsečík na hranu. Tyto grafy lze vždy kreslit (jako externě 1-rovinný graf) s rovnými hranami a pravoúhlými průsečíky [21] . Pomocí dynamického programování na SPQR stromu daného grafu je možné zkontrolovat, zda je graf externě 1-rovinný v lineárním čase [22] [23] . Komponenty tri-propojeného grafu (uzly stromu SPQR) se mohou skládat pouze z cyklů , bondgraphs a úplných grafů se čtyřmi vrcholy, což znamená, že externě 1-planární grafy jsou rovinné a mají šířku stromu maximálně tři. Na rozdíl od 1-rovinných grafů mají vnější 1-rovinné grafy charakteristiku z hlediska grafových minoritních grafů — graf je vnější 1-planární právě tehdy, když neobsahuje žádnou z pěti zakázaných minoritních skupin [23] .
Třída 1-rovinných grafů zahrnuje 4-mapové grafy , grafy vytvořené ze sousedních oblastí roviny s podmínkou, že žádný bod neleží na hranici více než čtyř oblastí (vrcholy (oblasti) jsou spojeny hranou, pokud hranice regionů). Naopak každý optimální 1-rovinný graf je 4-mapový graf. Avšak 1-rovinné grafy, které nejsou optimální 1-rovinné, nemusí být mapovými grafy [24] .
1-rovinné grafy jsou zobecněny na k -rovinné grafy, ve kterých každou hranu protínají jiné hrany nejvýše kkrát . Ringel definoval číslo lokálního průsečíku grafu G jako nejmenší nezáporné k takové, že G má k -rovinnou kresbu. Protože místní počet průsečíků je roven největšímu stupni průsečíkového grafu hran optimálního vzoru, a tloušťku (minimální počet rovinných grafů, na které lze rozložit hrany) lze považovat za chromatický počet grafu průsečíku příslušného obrazce, z Brooksovy věty vyplývá, že tloušťka je nejvýše o jednu větší než lokální počet průsečíků [25] . k -rovinné grafy s n vrcholy mají maximálně O ( k 1/2 n ) hran [26] a šířku stromu O (( kn ) 1/2 [27 ] . Mělký moll k -rovinného grafu s hloubkou d je sám ( 2d + 1) k -rovinný, takže mělké moll 1-rovinných grafů a k -rovinných grafů jsou řídké grafy , což znamená, že 1-rovinný a k- rovinné grafy mají omezenou příponu [28] .
U nerovinných grafů můžete také nastavit parametr počet průsečíků , minimální počet hran, které se protínají v jakémkoli výkresu grafu. Graf s k průsečíky je nutně k -rovinný, ale obráceně to nemusí být nutně pravda. Například Heawoodův graf má 3 průsečíky, ale tyto průsečíky nemusí být s jednou hranou, je 1-rovinný a lze jej kreslit se současnou optimalizací celkového počtu průsečíků a průsečíků na jednu hranu.
Dalším souvisejícím konceptem pro nerovinné grafy je skew , minimální počet hran, které musí být odstraněny, aby byl graf rovinný.