Rank-width
रैंक-चौड़ाई एक ग्राफ चौड़ाई पैरामीटर है जिसका उपयोग ग्राफ सिद्धांत और मानकीकृत जटिलता में किया जाता है, और रैखिक बीजगणित का उपयोग करके परिभाषित किया जाता है। इसे किसी दिए गए ग्राफ के शीर्षों के पदानुक्रमित समूहों से परिभाषित किया गया है, जिन्हें त्रिकोणीय पेड़ों के रूप में देखा जा सकता है जिनके शीर्ष उनके पत्तों के रूप में होते हैं। इस तरह के पेड़ से किसी भी किनारे को हटाने से इसे दो उप-पेड़ों में विभाजित कर दिया जाता है और शीर्षों को दो उपसमूहों में विभाजित कर दिया जाता है। विभाजन के एक तरफ से दूसरी तरफ जाने वाले ग्राफ किनारों को एक बायडजैसेन्सी मैट्रिक्स द्वारा वर्णित किया जा सकता है; रैंक-चौड़ाई के उद्देश्यों के लिए, इस मैट्रिक्स को वास्तविक संख्याओं का उपयोग करने के बजाय परिमित क्षेत्र GF (2) पर परिभाषित किया जाता है। इस अधिकतम को कम करने के लिए चुने गए क्लस्टरिंग के लिए ग्राफ की रैंक-चौड़ाई बायडजैसेन्सी मैट्रिक्स की अधिकतम रैंक होती है। श्रेणी-चौड़ाई समूह-चौड़ाई से निकटता से संबंधित हैः, समूह-चौड़ाई कहाँ है। हालांकि, बड़े गुट-चौड़ाई के ग्राफ के लिए गुट-चौड़ाई की गणना करने के लिए एन. पी.-कठिन है, और इसकी मानकीकृत जटिलता अज्ञात है। इसके विपरीत, यह परीक्षण करने के लिए कि क्या श्रेणी-चौड़ाई अधिक से अधिक एक स्थिरांक है, बहुपद समय लेता है, और तब भी जब श्रेणी-चौड़ाई स्थिर नहीं होती है, तो इसे बहुपद समय में एक स्थिर सन्निकटन अनुपात के साथ अनुमानित किया जा सकता है। इस कारण से, श्रेणी-चौड़ाई का उपयोग क्लीक-चौड़ाई के लिए अधिक आसानी से गणना किए गए विकल्प के रूप में किया जा सकता है। उच्च श्रेणी-चौड़ाई वाले आलेखों के परिवार का एक उदाहरण वर्गाकार ग्रिड आलेखों द्वारा प्रदान किया जाता है। ग्रिड ग्राफ के लिए, रैंक-चौड़ाई बिल्कुल होती है। संदर्भ ग्राफ लघु सिद्धांत रैखिक बीजगणित