Rank-width
درجہ چوڑائی گراف کی چوڑائی کا ایک پیرامیٹر ہے جو گراف تھیوری اور پیرامیٹرائزڈ پیچیدگی میں استعمال ہوتا ہے، اور لکیری الجبرا کا استعمال کرتے ہوئے اس کی وضاحت کی جاتی ہے۔ اس کی تعریف کسی دیئے گئے گراف کے عمودی حصوں کے درجہ بندی کے کلسٹرنگ سے کی گئی ہے، جسے سہ رخی درختوں کے طور پر دیکھا جا سکتا ہے جن کے عمودی حصے ان کے پتوں کی طرح ہوتے ہیں۔ اس طرح کے درخت سے کسی بھی کنارے کو ہٹانے سے اسے دو ذیلی درختوں میں تقسیم کر دیا جاتا ہے اور عمودی حصوں کو دو ذیلی حصوں میں تقسیم کر دیا جاتا ہے۔ تقسیم کے ایک طرف سے دوسری طرف جانے والے گراف کے کناروں کو بائیوڈجیسینسی میٹرکس کے ذریعے بیان کیا جا سکتا ہے۔ رینک چوڑائی کے مقاصد کے لیے، اس میٹرکس کی تعریف حقیقی اعداد کا استعمال کرنے کے بجائے محدود فیلڈ GF (2) پر کی جاتی ہے۔ اس زیادہ سے زیادہ کو کم کرنے کے لیے منتخب کردہ کلسٹرنگ کے لیے گراف کی رینک چوڑائی بائیوڈیجینسی میٹرکس کی زیادہ سے زیادہ رینک ہوتی ہے۔ درجہ چوڑائی کا قریبی تعلق کلیک چوڑائی سے ہے:، کلیک چوڑائی کہاں ہے۔ تاہم، بڑے کلکس چوڑائی کے گرافوں کے لیے کلکس چوڑائی کا حساب لگانا این پی مشکل ہے، اور اس کی پیرامیٹرائزڈ پیچیدگی نامعلوم ہے۔ اس کے برعکس، یہ جانچنا کہ آیا درجہ چوڑائی زیادہ سے زیادہ مستقل ہے، کثیر الجہتی وقت لیتا ہے، اور یہاں تک کہ جب درجہ چوڑائی مستقل نہیں ہوتی ہے تو بھی کثیر الجہتی وقت میں مستقل تخمینہ تناسب کے ساتھ اس کا تخمینہ لگایا جا سکتا ہے۔ اس وجہ سے، درجہ چوڑائی کو کلیک چوڑائی کے لیے زیادہ آسانی سے شمار کردہ متبادل کے طور پر استعمال کیا جا سکتا ہے۔ اعلی درجہ چوڑائی والے گراف کے خاندان کی ایک مثال مربع گرڈ گراف کے ذریعے فراہم کی جاتی ہے۔ گرڈ گراف کے لیے، رینک چوڑائی بالکل ہوتی ہے۔ حوالہ جات گراف معمولی نظریہ لکیری الجبرا