Circle graph
வரைபடக் கோட்பாட்டில், வட்ட வரைபடம் என்பது ஒரு நாணல் வரைபடத்தின் குறுக்குவெட்டு வரைபடமாகும். அதாவது, இது ஒரு திசைதிருப்பப்படாத வரைபடமாகும், அதன் செங்குத்துகள் ஒரு வட்டத்தின் வளையங்களின் வரையறுக்கப்பட்ட அமைப்புடன் தொடர்புபடுத்தப்படலாம், அதாவது தொடர்புடைய வளையங்கள் ஒன்றையொன்று கடந்தால் மட்டுமே இரண்டு செங்குத்துகள் அருகில் இருக்கும். வழிமுறை சிக்கலானது ஒரு O (n2)-நேர வழிமுறையை வழங்குகிறது, இது கொடுக்கப்பட்ட n-வெர்டெக்ஸ் திசைதிருப்பப்படாத வரைபடம் ஒரு வட்ட வரைபடமா என்பதை சோதிக்கிறது, அப்படியானால், அதைக் குறிக்கும் வளையங்களின் தொகுப்பை உருவாக்குகிறது. பொது வரைபடங்களில் NP-முழுமையான பல சிக்கல்கள் வட்ட வரைபடங்களுக்கு மட்டுப்படுத்தப்படும்போது பல்லுறுப்புக்கோவை நேர வழிமுறைகளைக் கொண்டுள்ளன. உதாரணமாக, ஒரு வட்ட வரைபடத்தின் மூன்று அகலத்தை தீர்மானிக்க முடியும் என்பதைக் காட்டியது, மேலும் O (n3) நேரத்தில் ஒரு உகந்த மர சிதைவு கட்டப்பட்டது. கூடுதலாக, குறைந்தபட்ச நிரப்புதல் (அதாவது, கொடுக்கப்பட்ட வட்ட வரைபடத்தை ஒரு துணை வரைபடமாகக் கொண்ட முடிந்தவரை சில விளிம்புகளைக் கொண்ட ஒரு கார்டல் வரைபடம்) O (n3) நேரத்தில் காணலாம். ஒரு வட்ட வரைபடத்தின் அதிகபட்ச கிளிக்கை O (n log2n) நேரத்தில் காணலாம் என்று காட்டப்பட்டுள்ளது, அதே நேரத்தில் ஒரு எடை இல்லாத வட்ட வரைபடத்தின் அதிகபட்ச சுயாதீன தொகுப்பை O (n குறைந்தபட்சம் {d, α}) நேரத்தில் காணலாம், அங்கு d என்பது அதன் அடர்த்தி என்று அழைக்கப்படும் வரைபடத்தின் அளவுரு, மற்றும் α என்பது வட்ட வரைபடத்தின் சுதந்திர எண். இருப்பினும், வட்ட வரைபடங்களுக்கு மட்டுப்படுத்தப்படும்போது NP-முழுமையான சிக்கல்களும் உள்ளன. இவற்றில் குறைந்தபட்ச மேலாதிக்க செட், குறைந்தபட்ச இணைக்கப்பட்ட மேலாதிக்க செட் மற்றும் குறைந்தபட்ச மொத்த மேலாதிக்க செட் சிக்கல்கள் ஆகியவை அடங்கும். ஒரு வட்ட வரைபடத்தின் நிற எண் என்பது அதன் வளையங்களுக்கு வண்ணம் பூச பயன்படுத்தக்கூடிய குறைந்தபட்ச வண்ணங்களின் எண்ணிக்கையாகும், இதனால் இரண்டு குறுக்கு வளையங்கள் ஒரே நிறத்தைக் கொண்டிருக்காது. வட்ட வரைபடங்களை உருவாக்க முடியும் என்பதால், இதில் தன்னிச்சையாக பெரிய செட் வளையங்கள் அனைத்தும் ஒன்றையொன்று கடக்கின்றன, ஒரு வட்ட வரைபடத்தின் நிற எண் தன்னிச்சையாக பெரியதாக இருக்கலாம், மேலும் ஒரு வட்ட வரைபடத்தின் நிற எண்ணை தீர்மானிப்பது NP-முழுமையானது. ஒரு வட்ட வரைபடத்தை நான்கு வண்ணங்களால் வண்ணமயமாக்க முடியுமா என்பதை சோதிக்க இது NP-முழுமையானதாக உள்ளது. மூன்று வண்ணங்களைக் கொண்ட ஒரு வண்ணத்தைக் கண்டுபிடிப்பது பல்லுறுப்புக்கோவை நேரத்தில் செய்யப்படலாம் என்று அவர் கூறினார், ஆனால் இந்த முடிவைப் பற்றிய அவரது எழுத்து பல விவரங்களைத் தவிர்க்கிறது. வட்ட வரைபடங்களின் வரையறுக்கப்பட்ட துணைப்பிரிவுகளை சில வண்ணங்களுடன் வண்ணமயமாக்குவதில் உள்ள சிக்கல்களை பல ஆசிரியர்கள் ஆராய்ந்துள்ளனர். குறிப்பாக, k அல்லது அதற்கு மேற்பட்ட வளையங்களின் தொகுப்புகள் அனைத்தும் ஒன்றையொன்று கடக்காத வட்ட வரைபடங்களுக்கு, வரைபடத்தை குறைவான வண்ணங்களுடன் வண்ணமயமாக்க முடியும். இதைக் குறிப்பிடுவதற்கான ஒரு வழி என்னவென்றால், வட்ட வரைபடங்கள்-வரம்புக்குட்பட்டவை. குறிப்பிட்ட விஷயத்தில் k = 3 (அதாவது, முக்கோணம் இல்லாத வட்ட வரைபடங்களுக்கு) நிற எண் அதிகபட்சம் ஐந்து ஆகும், இது இறுக்கமானதுஃ அனைத்து முக்கோணம் இல்லாத வட்ட வரைபடங்களும் ஐந்து வண்ணங்களால் வண்ணமயமாக்கப்படலாம், மேலும் முக்கோணம் இல்லாத வட்ட வரைபடங்கள் உள்ளன ஐந்து வண்ணங்கள் தேவை. ஒரு வட்ட வரைபடத்தில் குறைந்தபட்சம் ஐந்து சுற்றளவு இருந்தால் (அதாவது, அது முக்கோணம் இல்லாதது மற்றும் நான்கு-வெர்டெக்ஸ் சுழற்சிகள் இல்லை) அது அதிகபட்சம் மூன்று வண்ணங்களுடன் வண்ணமயமாக்கப்படலாம். முக்கோணம் இல்லாத சதுர வரைபடங்களை வண்ணமயமாக்கும் சிக்கல் சதுர வரைபடங்களை மரங்களின் கார்ட்டீசியன் தயாரிப்புகளின் ஐசோமெட்ரிக் துணை வரைபடங்களாகக் குறிக்கும் சிக்கலுக்கு சமம்; இந்த கடிதத்தில், நிறத்தில் உள்ள வண்ணங்களின் எண்ணிக்கை தயாரிப்பு பிரதிநிதித்துவத்தில் உள்ள மரங்களின் எண்ணிக்கையுடன் ஒத்திருக்கிறது. "இரண்டு முனைய சுவிட்ச்பாக்ஸ் ரூட்டிங்" என்று அழைக்கப்படும் கம்பி ரூட்டிங்கிற்கான ஒரு சிறப்பு வழக்குக்கான சுருக்க பிரதிநிதித்துவமாக வி. எல். எஸ். ஐ இயற்பியல் வடிவமைப்பில் பயன்பாடுகள் வட்டம் வரைபடங்கள் எழுகின்றன. இந்த விஷயத்தில் ரூட்டிங் பகுதி ஒரு செவ்வகமாகும், அனைத்து வலைகளும் இரண்டு முனைகளாக உள்ளன, மேலும் முனையங்கள் செவ்வகத்தின் சுற்றளவில் வைக்கப்படுகின்றன. இந்த வலைகளின் குறுக்குவெட்டு வரைபடம் ஒரு வட்ட வரைபடம் என்பதை எளிதில் காணலாம். கம்பி ரூட்டிங் படிநிலையின் குறிக்கோள்களில் ஒன்று, வெவ்வேறு வலைகள் மின்சார ரீதியாக துண்டிக்கப்படுவதை உறுதி செய்வதாகும், மேலும் அவற்றின் சாத்தியமான குறுக்குவெட்டு பாகங்கள் வெவ்வேறு கடத்தும் அடுக்குகளில் அமைக்கப்பட வேண்டும். எனவே வட்ட வரைபடங்கள் இந்த ரூட்டிங் சிக்கலின் பல்வேறு அம்சங்களைப் பிடிக்கிறது. வட்ட வரைபடங்களின் வண்ணங்கள் தன்னிச்சையான வரைபடங்களின் புத்தக உட்பொதிப்புகளைக் கண்டறியவும் பயன்படுத்தப்படலாம்ஃ கொடுக்கப்பட்ட வரைபடம் G இன் செங்குத்துகள் ஒரு வட்டத்தில் அமைக்கப்பட்டிருந்தால், G இன் விளிம்புகள் வட்டத்தின் வளையங்களை உருவாக்கினால், இந்த வளையங்களின் குறுக்குவெட்டு வரைபடம் ஒரு வட்ட வரைபடம் மற்றும் இந்த வட்ட வரைபடத்தின் வண்ணங்கள் கொடுக்கப்பட்ட வட்ட அமைப்பை மதிக்கும் புத்தக உட்பொதிப்புகளுக்கு சமம். இந்த சமநிலையில், வண்ணத்தில் உள்ள வண்ணங்களின் எண்ணிக்கை புத்தக உட்பொதிப்பில் உள்ள பக்கங்களின் எண்ணிக்கையுடன் ஒத்திருக்கிறது. தொடர்புடைய வரைபட வகுப்புகள் ஒரு வரியில் உள்ள இடைவெளிகளின் தொகுப்பின் ஒன்றுடன் ஒன்று வரைபடமாக இருந்தால் மட்டுமே வரைபடம் என்பது ஒரு வட்ட வரைபடமாகும். இது ஒரு வரைபடமாகும், இதில் செங்குத்துகள் இடைவெளிகளுடன் ஒத்திருக்கின்றன, மேலும் இரண்டு செங்குத்துகளும் ஒரு விளிம்பால் இணைக்கப்பட்டுள்ளன, இரண்டு இடைவெளிகள் ஒன்றுடன் ஒன்று இருந்தால், மற்றொன்று இல்லை. ஒரு கோட்டில் உள்ள இடைவெளிகளின் தொகுப்பின் குறுக்குவெட்டு வரைபடம் இடைவெளி வரைபடம் என்று அழைக்கப்படுகிறது. சரம் வரைபடங்கள், தளத்தில் வளைவுகளின் குறுக்குவெட்டு வரைபடங்கள், வட்ட வரைபடங்களை ஒரு சிறப்பு நிகழ்வாக உள்ளடக்கியது. ஒவ்வொரு வரிசைமாற்ற வரைபடமும் ஒவ்வொரு அலட்சிய வரைபடமும் போலவே, ஒவ்வொரு தூர-பரம்பரை வரைபடமும் ஒரு வட்ட வரைபடமாகும். ஒவ்வொரு வெளிப்புற பிளானர் வரைபடமும் ஒரு வட்ட வரைபடமாகும். வட்ட வரைபடங்கள் பலகோண-வட்ட வரைபடங்களால் பொதுமைப்படுத்தப்படுகின்றன, பலகோணங்களின் குறுக்குவெட்டு வரைபடங்கள் அனைத்தும் ஒரே வட்டத்தில் பொறிக்கப்பட்டுள்ளன. குறிப்புகள் குறிப்புகள். . . . . . . மேற்கோள் காட்டியபடி. . மேற்கோள் காட்டியபடி. . மேற்கோள் காட்டியபடி. . . . . மேற்கோள் காட்டியபடி. . . . . . . . மேற்கோள் காட்டியபடி. வட்டங்கள் குறுக்குவெட்டு வகுப்புகளின் வரைபடங்கள் வடிவியல் வரைபடங்கள்