Монопланарни граф
У тополошкој теорији графова, монопланарни граф је граф који може бити нацртан у еуклидској равни тако да једна грана може имати највише једно пресецање, и то са само једном граном графа.

Бојење 
Монопланарне графове први је проучавао , који је доказао да они могу бити обојени са највише седам боја. Касније је показано да је тачан број боја потребних за бојење ових графова, у најгорем случају, шест. Пример комплетног графа К6, који је монопланаран, показује да монопланарни графови понекад захтевају 6 боја за бојење. Ипак, доказ да је 6 боја увек довољно је знатно компликованији.

Рингелова мотивација је био покушај да реши варијацију тоталног бојења за планарне графове, код које се чворови и површи планарног графа боје тако да никоја два суседна чвора, никоја две суседне површи нити чвор и површ суседна њему, немају исту боју. Ово се, свакако може извршити помоћу 8 боја имплементирајући теорему о 4 боје на дати граф и његов дуални граф одвојено, користећи два дисјунктна скупа од по 4 боје. Ипак, мање боја се може добити формирајући помоћни граф који има чвор за сваки чвор или површ датог планарног графа, и у коме су два чвора суседна кадгод они представљају два суседна чвора или површи датог графа. Бојење помоћног графа одговара чвор-површ бојењу оригиналног графа. Добијени помоћни граф је монопланаран, из чега следи да Рингелов проблем чвор-површ бојења може бити решен и са 6 боја. Граф K6' не може бити формиран као помоћни граф на овај начин, али се ипак проблем чвор-површ бојења понекад може решити са 6 боја; на пример, ако је планарни граф који треба обојити троугаона призма, онда њених 11 чворова и површи захтева 6 боја, зато што се не може трима од њих дати једна боја.

Густина грана 

Сваки монопланарни граф са n чворова има највише 4n − 8 грана. Ова чињеница се може искористити да покаже да комплетан граф К7 са 7 чворова није монопланаран, зато што овај граф има 21 грану и у том случају 4n − 8 = 20 < 21. Монопланарни граф са 4n − 8 грана може бити формиран помоћу планарног графа, нацртан на тај начин да је свака површ четвороугаона, додајући две пресечне дијагонале у сваки четвороугао. Ипак, за разлику од планарних графова, постоји максимални монопланарни граф (графови којима се не може додати грана а да се задржи монопланарност) који има знатно мање грана од 4n − 8.

Комплентни мултипартитивни графови 

Потпуна класификација монопланарних комплетних графова, комплетних бипартитивних графова, и још општије- комплетних мултипартитивних графова је позната. Сваки бипартитивни граф форме K2,n је монопланаран, као и сваки комплетни трипартитивни граф форме K1,1,n. Поред ових небројених примера, једини комплетни мултипартитивни монопланарни графови су K6, K1,1,1,6, K1,1,2,3, K2,2,2,2, K1,1,1,2,2, и њихови подграфови. Минимални немонопланарни комплетни мултипартитивни графови су 
K3,7, K4,5, K1,3,4, K2,3,3, and K1,1,1,1,3. На пример, комплетан бипартитивни граф K3,6 је монопланаран зато што је подграф графа K1,1,1,6, али K3,7 није монопланаран.

Рачунарска сложеност 
Тестирати да ли је дати граф монопланаран је НП-комплетан проблем, и остаје НП-комплетан чак и за графове добијене додавањем гране планарном графу.
У супротности са Феријевом теоремом за планарне графове, не може се сваки монопланарни граф нацртати буквално доцртавањем појединачних грана; ипак, тестирање да ли се монопланарни цртеж кориговати на овај начин може бити урађено у полиномијалном времену.

Генерализација и повезани концепти 
Монопланарни графови су проширени до к-планарних графова, графова код којих је свака грана пресечена највише к пута. К-планарни графови са n чворова имају највише O(n√k) грана.

Непланарни графови могу такође бити параметризовани помоћу њиховог броја укрштања, минималног броја парова грана које се укрштају у графу. Граф са бројем укрштања к је неминовно к-планаран, али обрнуто не мора да важи. На пример, Хивудов граф има број укрштања 3, али није неминовно да ће сва 3 укрштања бити на једној грани, тако да је тај граф монопланаран, и може бити нацртан на начин да се симултано оптимизује укупан број пресецања и број пресецања по грани.

Референце 

Тополошка теорија графова
Планарни графови
У тополошкој теорији графова , монопланарни граф је граф који може бити нацртан у еуклидској равни тако да једна грана може имати највише једно пресецање , и то са само једном граном графа . Бојење Монопланарне графове први је проучавао , који је доказао да они могу бити обојени са највише седам боја . Касније је показано да је тачан број боја потребних за бојење ових графова , у најгорем случају , шест . Пример комплетног графа К6 , који је монопланаран , показује да монопланарни графови понекад захтевајубоја за бојење . Ипак , доказ да јебоја увек довољно је знатно компликованији . Рингелова мотивација је био покушај да реши варијацију тоталног бојења за планарне графове , код које се чворови и површи планарног графа боје тако да никоја два суседна чвора , никоја две суседне површи нити чвор и површ суседна њему , немају исту боју . Ово се , свакако може извршити помоћубоја имплементирајући теорему обоје на дати граф и његов дуални граф одвојено , користећи два дисјунктна скупа од побоје . Ипак , мање боја се може добити формирајући помоћни граф који има чвор за сваки чвор или површ датог планарног графа , и у коме су два чвора суседна кадгод они представљају два суседна чвора или површи датог графа . Бојење помоћног графа одговара чвор-површ бојењу оригиналног графа . Добијени помоћни граф је монопланаран , из чега следи да Рингелов проблем чвор-површ бојења може бити решен и сабоја . Граф K6 ' не може бити формиран као помоћни граф на овај начин , али се ипак проблем чвор-површ бојења понекад може решити сабоја ; на пример , ако је планарни граф који треба обојити троугаона призма , онда њенихчворова и површи захтевабоја , зато што се не може трима од њих дати једна боја . Густина грана Сваки монопланарни граф са n чворова има највише −грана . Ова чињеница се може искористити да покаже да комплетан граф К7 сачворова није монопланаран , зато што овај граф имаграну и у том случају −=< Монопланарни граф са −грана може бити формиран помоћу планарног графа , нацртан на тај начин да је свака површ четвороугаона , додајући две пресечне дијагонале у сваки четвороугао . Ипак , за разлику од планарних графова , постоји максимални монопланарни граф ( графови којима се не може додати грана а да се задржи монопланарност ) који има знатно мање грана од − Комплентни мултипартитивни графови Потпуна класификација монопланарних комплетних графова , комплетних бипартитивних графова , и још општије- комплетних мултипартитивних графова је позната . Сваки бипартитивни граф форме K2,n је монопланаран , као и сваки комплетни трипартитивни граф форме K1,1,n . Поред ових небројених примера , једини комплетни мултипартитивни монопланарни графови су K6 , K1,1,1,6 , K1,1,2,3 , K2,2,2,2 , K1,1,1,2,2 , и њихови подграфови . Минимални немонопланарни комплетни мултипартитивни графови су K3,7 , K4,5 , K1,3,4 , K2,3,3 , and K1,1,1,1,3 . На пример , комплетан бипартитивни граф K3,6 је монопланаран зато што је подграф графа K1,1,1,6 , али K3,7 није монопланаран . Рачунарска сложеност Тестирати да ли је дати граф монопланаран је НП-комплетан проблем , и остаје НП-комплетан чак и за графове добијене додавањем гране планарном графу . У супротности са Феријевом теоремом за планарне графове , не може се сваки монопланарни граф нацртати буквално доцртавањем појединачних грана ; ипак , тестирање да ли се монопланарни цртеж кориговати на овај начин може бити урађено у полиномијалном времену . Генерализација и повезани концепти Монопланарни графови су проширени до к-планарних графова , графова код којих је свака грана пресечена највише к пута . К-планарни графови са n чворова имају највише O( n√k ) грана . Непланарни графови могу такође бити параметризовани помоћу њиховог броја укрштања , минималног броја парова грана које се укрштају у графу . Граф са бројем укрштања к је неминовно к-планаран , али обрнуто не мора да важи . На пример , Хивудов граф има број укрштања али није неминовно да ће сваукрштања бити на једној грани , тако да је тај граф монопланаран , и може бити нацртан на начин да се симултано оптимизује укупан број пресецања и број пресецања по грани . Референце Тополошка теорија графова Планарни графови