Графтарды бір мезгілде салу — бұл екі және одан да көп Әр түрлі графтарды белгіленген шыңдардың бір жиынында визуализациялау техникасы. Әртүрлі бағандардың қабырғалары арасындағы қиылысуларға рұқсат етіледі, тек бір бағанның қабырғаларының қиылысуына рұқсат етілмейді[1].

Анықтамасы
Егер қабырғаларды сынық немесе қисық түрінде салуға рұқсат етілсе, онда кез келген планарлы бағанды жазықтықтағы еркін позициялардағы шыңдармен қиылыспай салуға болады. Егер екі баған үшін бір биіктікті қолдансаңыз, бір уақытта екі бағанды салыңыз. Бір мезгілде салыным бойынша зерттеулер қабырғалардың аздаған майысулары (сынықтары) бар, не екі бағанның қабырғалары арасындағы қиылысулар саны аз салымдарды іздеуге шоғырланады[1]. Сонымен қатар бір мезгілде салымдардың шектеулі модельдері де зерттеледі. Бір мезгілде геометриялық салынымда әрбір баған қабырғалар ретінде кесінділері бар планарлы түрде салынуы тиіс. Мұндай салымдардың болуына кепілдік беру үшін планарлық графтардың кіші сыныптарымен шектелуге тура келеді. Басқа шектеулі модельде тіркелген қабырғалары бар бір мезгілде салыным қисықтар мен майысулар рұқсат етілген, бірақ екі графада да болатын кез келген қабырға бағандардың екі көрінісінде бір қисықпен ұсынылуы тиіс. Егер бір уақытта геометриялық тіркеме болса, ол автоматты түрде бекітілген қабырғалармен бір мезгілде тіркеме болып табылады[1].

Бір мезгілде салыным графтың қалыңдығымен, берілген графтың барлық қабырғаларын жабатын планарлық кіші графтардың ең аз санымен және геометриялық қалыңдықтармен, қабырғаларды бояуға арналған түстердің ең аз санымен тығыз байланысты. Атап айтқанда, берілген бағанның қалыңдығы екіге тең, егер баған қабырғаларын бір мезгілде салынымы бар екі кіші бағанға бөлуге болатын болса, ал геометриялық қалыңдығы екіге тең, егер қабырғаларды бір мезгілде геометриялық салынымы бар екі кіші бағанға бөлуге болатын болса.

Бір уақытта екі бағаннан артық бір уақытта салу есептері үшін, әдетте, кіріс бағандарының барлық жұптары бірдей қиылысады деп болжанады. Яғни, көптеген қабырғалар мен шыңдар күнбағыс құрайды [en]. Бұл шектеу күнбағыс қиылысында белгілі [1].

Бір уақытта геометриялық салыным
Бір мезгілде геометриялық салымның көптеген нәтижелері Берілген екі графаның Декарт координаттары осы екі графтың қасиеттерінен алынуы мүмкін идеяға негізделеді. Мұндай үлгінің негізгі нәтижелерінің бірі-бір шыңдардың кез келген екі жолы әрқашан бір мезгілде салынғаны. Мұндай тіркемені табу үшін бірінші жолдағы жоғарғы позицияны x-координаталар ретінде, ал екінші жолдағы жоғарғы позицияны y — координаталар ретінде пайдалануға болады. Бұл жағдайда бірінші жол автоматты түрде қиылыспайтын x-монотонды сынық ретінде салынады, ал екінші жол y-монотонды сынық ретінде боялады[2].

Мұндай сурет өлшемі баған өлшеміне байланысты болатын бүтін тордағы шыңдарды орналастырады. Белгілі бір орналасуы, сондай-ақ жұмыс істейді, егер екі баған шынжыр табақшалары немесе екеуі де циклдар болып табылады, бірақ торлардың мөлшері көп болса да, бірақ Граф өлшемдеріне сызықтық тәуелді болып қалады. Баған өлшемдеріне сызықтық тәуелді торға бір мезгілде салу жұлдыз болып табылатын бағандардың кез келген саны үшін мүмкін. Бір мезгілде салуға мүмкіндік беретін, бірақ торлардың үлкен мөлшерін талап ететін графтардың басқа жұптары-дөңгелек және цикл, ағаш және бу тіркемесі, сондай-ақ ең жоғары дәрежесі екіге тең графтардың жұптары. Алайда, бір мезгілде (геометриялық) тіркемесі жоқ планетарлық баған және бу тіркемесі немесе ағаш және жолдар бар[3][4][5].

Екі баған бір уақытта геометриялық салыным жіберіле ме, тексеру NP-қиын міндет болып табылады[1][6]. Бұл мақаланы толықтырып, дамыту арқылы, Уикипедияға көмектесе аласыз. Бұл нәтиженің дәлелдемелерінен, сондай-ақ графтардың кейбір жұбы үшін, бір мезгілде геометриялық салынымы бар, бағандарды салуға болатын ең аз торлар үшін, графтың өлшеміне екі рет экспоненционалды тәуелді өлшем болады[7][8].

Бекітілген қабырғалармен бір мезгілде салу
Тіркелген қабырғалармен бір мезгілде салу үшін әр түрлі кіріс бағандарының классификациясы, әрқашанда салынымы бар немесе кейде салынымы жоқ, тек екі қатысушы бағанның түріне ғана емес, сонымен қатар олардың қиылысу құрылымына да байланысты. Мысалы, екі баған сыртқы жоспарлау болып табылса және олардың қиылысуы сызықтық орман болып табылса[en], әрқашанда қабырғаға бір сынығы бар, бағанның өлшеміне полиномиальды тәуелді, өлшемі бар тордағы сынық нүктелері бар тіркемені табуға болады. Дегенмен, мұндай тіркемесі жоқ күрделі қиылыстары бар сыртқы жоспарлау графтарының басқа жұптары бар. Сондай-ақ, кез келген жұп жоспарлы баған және ағаш үшін бекітілген қабырғалармен бір мезгілде тіркемені табуға болады[9][10][11].

Question mark2.svg
Математиканың шешілмеген мәселелері: полиномиалдық уақыт ішінде берілген екі графта белгіленген қабырғалармен бір мезгілде салынымды табуға бола ма?
Полиномиалды уақыт ішінде бекітілген қабырғалармен бір мезгілде салынымның болуын тексеруге болады ма ашық проблема болып табылады. Алайда, үш және одан да көп бағандар үшін NP есебі қиын. Тіркелген қабырғалармен бір мезгілде тіркемені (егер бар болса) сыртқы планарлы бағандардың жұбына, сондай-ақ қиылысу екі байланысқан бағандардың жұбына арналған полиномиалды уақыт ішінде табуға болады[1][12][13][14].

Шексіз бір мезгілде тіркеме
Кез келген екі жоспарлы баған бір мезгілде салынады. Бұл торда полиномиальды көлемді жасауға болады, қабырғалары екі сынықтан аспайтын болады. Кез келген екі поддамильтон бағананың қабырғасына ең көп сынған бір мезгілде салынымы бар[1][15].