有限的擴展

在圖理論中，據說如果其所有淺未成年人都是稀疏的圖，則據說具有界限。許多稀疏圖的自然家庭具有限制的擴展。密切相關但更強的性質，多項式擴展等同於這些家族的分離器定理。具有這些特性的家庭具有有效的算法，包括子圖同構問題和模型檢查圖的一階理論。

定義和等效特徵

圖G的t -showlalow小調定義為通過收縮半徑t的頂點 - 單位子圖的集合，並刪除G的其餘頂點。如果存在一個函數f ，則圖表的擴展是有限的。

有界擴展類別的等效定義是，所有淺層未成年人的色數都由t的函數界定，或者給定的家族具有拓撲參數的有界值。這樣的參數是一個圖形不變的，它是在採用子圖下單調的，因此參數值只能在細分圖時以受控的方式變化，因此有界的參數值意味著圖形有限制的退化。

更強的概念是多項式擴展，這意味著用於結合淺層未成年人邊緣密度的函數F是多項式。如果遺傳圖家族遵守一個分離器定理，則指出該家族中的任何n -vertex圖可以通過除去o （ n ^c ）頂點的最多n / 2頂點分為零件該家庭必然具有多項式擴展。相反，具有多項式擴展的圖具有均方根分離器定理。

由於分離器與擴展之間的聯繫，每個次要的圖形家族（包括平面圖的家族）都具有多項式擴展。對於1平面圖，也是如此，更一般而言，可以將可以嵌入具有每個邊緣數量的交叉數以及無雙質的弦樂圖的圖表，因為這些都遵循相似的分離器定理到平面圖。在較高的歐幾里得空間中，球系統的交點圖與該特性的系統相交圖。

儘管有界書籍厚度的圖沒有sublinear分離器，但它們也有界面的擴展。邊界擴展的其他圖包括有界度的圖， ERDőS–Rényi模型中有界平均度的隨機圖以及有界隊列數的圖。

子圖同構問題的實例是，該目標是找到有界大小的目標圖，作為較大圖的子圖，該圖的大小不限制，可以在較大的圖屬於屬於較大圖的屬於的圖表的範圍的時間段內求解。有限的擴展。尋找固定尺寸的簇，找到固定尺寸的主導集或更一般的測試屬性，可以通過圖形的一階邏輯中的有界大小的公式表示，也是如此。

對於多項式擴展的圖，存在針對設定覆蓋問題的多項式時間近似方案，最大獨立設置問題，主導設置問題以及其他幾個相關的圖形優化問題。