ในทฤษฎีกราฟกราฟสี่เหลี่ยมคางหมูคือกราฟที่เกิดจากการตัดกันของรูปสี่เหลี่ยมคางหมูระหว่างเส้นแนวนอนสองเส้น กราฟสี่เหลี่ยมคางหมูเป็นกลุ่มของกราฟที่เปรียบเทียบกันได้ (co-comparability graphs) ซึ่งประกอบด้วยกราฟช่วง (interval graphs)และกราฟการเรียงสับเปลี่ยน (permutation graphs ) เป็นกลุ่มย่อย กราฟหนึ่งจะเป็นกราฟสี่เหลี่ยมคางหมูได้ก็ต่อเมื่อมีเซตของรูปสี่เหลี่ยมคางหมูที่สอดคล้องกับจุดยอดของกราฟนั้น โดยที่จุดยอดสองจุดจะเชื่อมต่อกันด้วยเส้นขอบก็ต่อเมื่อรูปสี่เหลี่ยมคางหมูที่สอดคล้องกันนั้นตัดกัน กราฟสี่เหลี่ยมคางหมูได้รับการแนะนำโดยDagan , GolumbicและPinterในปี 1988 นอกจากนี้ยังมีอัลกอริทึมสำหรับหาจำนวนสี (chromatic number), เซตอิสระถ่วงน้ำหนัก (weighted independent set) , การปกคลุมคลิก (clique cover) และคลิกถ่วงน้ำหนักสูงสุด (maximum weighted clique) ${\displaystyle {O}(n\log n)}$

กำหนดให้ช่องทางหนึ่งเป็นเส้นตรงแนวนอนสองเส้น และรูปสี่เหลี่ยมคางหมูระหว่างเส้นตรงทั้งสองนี้ถูกกำหนดโดยจุดสองจุดบนเส้นบนและจุดสองจุดบนเส้นล่าง กราฟหนึ่งเรียกว่ากราฟสี่เหลี่ยมคางหมู ถ้ามีเซตของรูปสี่เหลี่ยมคางหมูที่สอดคล้องกับจุดยอดของกราฟนั้น โดยที่จุดยอดสองจุดจะเชื่อมต่อกันด้วยขอบก็ต่อเมื่อรูปสี่เหลี่ยมคางหมูที่สอดคล้องกันนั้นตัดกัน มิติของลำดับช่วงของเซตที่มีลำดับบางส่วนP = ( X , <)คือจำนวนขั้นต่ำdของลำดับช่วงP ₁ … P _dโดยที่P = P ₁ ∩ … ∩ P _dกราฟความไม่สามารถเปรียบเทียบกันได้ของเซตที่มีลำดับบางส่วนP = ( X , <)คือกราฟแบบไม่มีทิศทางG = ( X , E )โดยที่xอยู่ติดกับyในGก็ต่อเมื่อxและyไม่สามารถเปรียบเทียบกันได้ในPกราฟที่ไม่มีทิศทางเป็นกราฟรูปสี่เหลี่ยมคางหมูก็ต่อเมื่อเป็นกราฟที่ไม่สามารถเปรียบเทียบกันได้ของลำดับบางส่วนที่มีมิติลำดับช่วงไม่เกิน 2 ^{[ 1 ]}

ปัญหาการค้นหาคลิกสูงสุดและการระบายสีกราฟรูปสี่เหลี่ยมคางหมูมีความเกี่ยวข้องกับปัญหาการกำหนดเส้นทางช่องสัญญาณใน การออกแบบ VLSIเมื่อมีขั้วต่อที่มีป้ายกำกับอยู่ด้านบนและด้านล่างของช่องสัญญาณสองด้าน ขั้วต่อที่มีป้ายกำกับเดียวกันจะเชื่อมต่อกันในเน็ตเดียวกัน เน็ตนี้สามารถแสดงได้ด้วยรูปสี่เหลี่ยมคางหมูที่ประกอบด้วยขั้วต่อขวาสุดและขั้วต่อซ้ายสุดที่มีป้ายกำกับเดียวกัน เน็ตสามารถกำหนดเส้นทางได้โดยไม่ตัดกันก็ต่อเมื่อรูปสี่เหลี่ยมคางหมูที่เกี่ยวข้องไม่ตัดกันเท่านั้น ดังนั้น จำนวนเลเยอร์ที่จำเป็นในการกำหนดเส้นทางเน็ตโดยไม่ตัดกันจึงเท่ากับจำนวนสีของกราฟ

สามารถใช้รูปสี่เหลี่ยมคางหมูในการแสดงกราฟสี่เหลี่ยมคางหมูได้ โดยใช้คำจำกัดความของกราฟสี่เหลี่ยมคางหมู การแสดงกราฟสี่เหลี่ยมคางหมูด้วยรูปสี่เหลี่ยมคางหมูสามารถดูได้ในรูปที่ 1

สี่เหลี่ยมที่ครอบงำ หรือการแสดงแบบกล่อง จะแมปจุดบนเส้นล่างของเส้นสองเส้นของการแสดงแบบสี่เหลี่ยมคางหมูให้อยู่บน แกน xและจุดบนเส้นบนให้อยู่บน แกน yของระนาบยุคลิด สี่เหลี่ยมคางหมูแต่ละอันจะสอดคล้องกับกล่องขนานแกนในระนาบ โดยใช้แนวคิดของลำดับการครอบงำ (ใน⁠ ⁠ ${\displaystyle \mathbb {R} ^{K}}$xกล่าวได้ว่าถูกครอบงำโดยyซึ่งเขียนแทนด้วยx < yถ้าx _iน้อยกว่าy _iสำหรับi = 1, …, k ) เรากล่าวว่ากล่องbครอบงำกล่องb'ถ้ามุมล่างของbครอบงำมุมบนของb'ยิ่งไปกว่านั้น ถ้ากล่องหนึ่งในสองกล่องครอบงำอีกกล่องหนึ่ง เรากล่าวว่ากล่องทั้งสองนั้นเปรียบเทียบกันได้ มิฉะนั้น กล่องทั้งสองนั้นเปรียบเทียบกันไม่ได้ ดังนั้น สี่เหลี่ยมคางหมูสองอันจะไม่ทับซ้อนกันอย่างแน่นอนก็ต่อเมื่อกล่องที่สอดคล้องกันของพวกมันเปรียบเทียบกันได้ การแสดงแบบกล่องมีประโยชน์เพราะลำดับการครอบงำที่เกี่ยวข้องทำให้สามารถใช้อัลกอริธึมเส้นกวาดได้^{[ 2 ]}

กราฟบิโทเลอแรนซ์เป็นกราฟความไม่สามารถเปรียบเทียบกันได้ของลำดับบิโทเลอแรนซ์ ลำดับจะเป็นลำดับบิโทเลอแรนซ์ก็ต่อเมื่อมีช่วงI _xและจำนวนจริงt ₁ ( x )และt _r ( x )ที่กำหนดให้กับจุดยอดแต่ละจุดxในลักษณะที่x < yก็ต่อเมื่อการทับซ้อนของI _xและI _yน้อยกว่าทั้งt _r ( x )และt ₁ ( y )และจุดศูนย์กลางของI _xน้อยกว่าจุดศูนย์กลางของI _y ^{[ 3} ] ในปี 1993 Langley แสดงให้เห็นว่ากราฟบิโทเลอแรนซ์แบบจำกัด ^นั้น เทียบเท่ากับคลาสของกราฟรูปสี่เหลี่ยมคางหมู^{[ 4 ]}

กราฟรูปสี่เหลี่ยมคางหมูประกอบด้วยการรวมกันของกราฟช่วงและกราฟการเรียงสับเปลี่ยน และเทียบเท่ากับกราฟที่ไม่สามารถเปรียบเทียบกันได้ของเซตที่มีลำดับบางส่วนซึ่งมีมิติของลำดับช่วงไม่เกินสอง กราฟการเรียงสับเปลี่ยนสามารถมองได้ว่าเป็นกรณีพิเศษของกราฟรูปสี่เหลี่ยมคางหมูเมื่อรูปสี่เหลี่ยมคางหมูทุกรูปมีพื้นที่เป็นศูนย์ ซึ่งเกิดขึ้นเมื่อจุดทั้งสองของรูปสี่เหลี่ยมคางหมูบนช่องทางด้านบนอยู่ในตำแหน่งเดียวกัน และจุดทั้งสองบนช่องทางด้านล่างอยู่ในตำแหน่งเดียวกัน

เช่นเดียวกับกราฟที่แสดงถึงความไม่สามารถเปรียบเทียบได้ทั้งหมด กราฟรูปสี่เหลี่ยมคางหมูเป็นกราฟที่สมบูรณ์แบบ

กราฟสี่เหลี่ยมคางหมูวงกลมเป็นกลุ่มของกราฟที่เสนอโดย Felsner และคณะในปี 1993 กราฟเหล่านี้เป็นซูเปอร์คลาสของกลุ่มกราฟสี่เหลี่ยมคางหมู และยังรวมถึงกราฟวงกลมและกราฟส่วนโค้งวงกลมด้วย สี่เหลี่ยมคางหมูวงกลมคือบริเวณในวงกลมที่อยู่ระหว่างคอร์ดสองเส้นที่ไม่ตัดกัน และกราฟสี่เหลี่ยมคางหมูวงกลมคือกราฟจุดตัดของกลุ่มสี่เหลี่ยมคางหมูวงกลมบนวงกลมเดียวกัน มีอัลกอริทึมสำหรับปัญหาเซตอิสระที่มีน้ำหนักสูงสุด และ อัลกอริทึมสำหรับ ปัญหาคลิกที่ มีน้ำหนักสูงสุด${\displaystyle O(n^{2})}$${\displaystyle {O}(n^{2}\log n)}$

กราฟ k -trapezoid เป็นส่วนขยายของกราฟ trapezoid ไปสู่มิติที่สูงขึ้น Felsner เป็นผู้เสนอกราฟประเภทนี้เป็นครั้งแรก และอาศัยนิยามของกล่องครอบงำ (dominating boxes) ที่ถ่ายทอดไปยังมิติที่สูงขึ้น โดยที่จุดxถูกแทนด้วยเวกเตอร์ โดยใช้ต้นไม้ช่วง ( k  − 1) มิติในการจัดเก็บและสอบถามพิกัด อัลกอริทึมของ Felsner สำหรับจำนวนสี (chromatic number) กลุ่มสูงสุด (maximum clique) และเซตอิสระสูงสุด (maximum independent set) สามารถนำไปใช้กับกราฟk -trapezoid ได้ใน เวลา ไม่นาน${\displaystyle (x_{1},\ldots ,x_{k})}$${\displaystyle {O}(n\log ^{k-1}n)}$

ควรเปรียบเทียบอัลกอริธึมสำหรับกราฟรูปสี่เหลี่ยมคางหมูกับอัลกอริธึมสำหรับกราฟที่เปรียบเทียบร่วมกันได้ทั่วไป สำหรับกราฟกลุ่มใหญ่กว่านี้ ปัญหาเซตอิสระสูงสุดและปัญหาการครอบคลุมคลิกขั้นต่ำสามารถแก้ไขได้ในเวลา^{[ 5 ]} Dagan และคณะได้เสนออัลกอริธึมสำหรับการระบายสีกราฟรูปสี่เหลี่ยมคางหมูเป็นครั้งแรก โดยที่ n คือจำนวนโหนดและ k คือจำนวนสีของกราฟ ต่อมา Felsner ได้เผยแพร่อัลกอริธึมสำหรับจำนวนสี เซตอิสระที่มีน้ำหนัก การครอบคลุมคลิก และคลิกที่มีน้ำหนักสูงสุด โดยใช้การแสดงแบบกล่องของกราฟรูปสี่เหลี่ยมคางหมู อัลกอริธึมเหล่านี้ทั้งหมดต้องการพื้นที่ อัลกอริธึมเหล่านี้อาศัยความเด่นที่เกี่ยวข้องในการแสดงแบบกล่องที่อนุญาตให้ใช้อัลกอริธึมเส้นกวาด Felsner เสนอให้ใช้ต้นไม้สมดุลที่สามารถดำเนินการแทรก ลบ และสอบถามได้ในเวลา ซึ่งส่งผลให้เกิดอัลกอริธึม ${\displaystyle {O}(n^{2}\log n)}$${\displaystyle {O}(nk)}$${\displaystyle {O}(n\log n)}$${\displaystyle {O}(n)}$${\displaystyle {O}(\log n)}$${\displaystyle {O}(n\log n)}$

เพื่อตรวจสอบว่ากราฟเป็นกราฟสี่เหลี่ยมคางหมูหรือไม่ ให้ค้นหาการวางแนวแบบทรานซิทีฟบนส่วนเติมเต็มของกราฟ เนื่องจากกราฟสี่เหลี่ยมคางหมูเป็นเซตย่อยของกราฟโค-คอมพาริบิลิตี้ ถ้ากราฟเป็นกราฟสี่เหลี่ยมคางหมู ส่วนเติมเต็ม ของกราฟ จะต้องเป็นกราฟคอมพาริบิลิตี้ ถ้าการวางแนวแบบทรานซิทีฟของส่วนเติมเต็มไม่มีอยู่กราฟจะไม่ใช่กราฟสี่เหลี่ยมคางหมู ถ้ามีอยู่ ให้ทดสอบว่าลำดับที่กำหนดโดยกราฟเป็นลำดับสี่เหลี่ยมคางหมูหรือไม่ อัลกอริทึมที่เร็วที่สุดสำหรับการจดจำลำดับสี่เหลี่ยมคางหมูได้รับการเสนอโดย McConnell และ Spinrad ในปี 1994 โดยมีเวลาทำงานกระบวนการนี้ลดคำถามเกี่ยวกับมิติช่วง 2 ให้เป็นปัญหาของการครอบคลุมกราฟสองส่วน ที่เกี่ยวข้อง โดยกราฟลูกโซ่ (กราฟที่ไม่มี 2K ₂ ที่เหนี่ยวนำ ) ^{[ 6 ]} โดยใช้การแยกจุดยอด ปัญหาการจดจำกราฟสี่เหลี่ยมคางหมูได้รับการแสดงโดย Mertzios และ Corneil ให้ประสบความสำเร็จในเวลา โดยที่แทนจำนวนขอบ กระบวนการนี้เกี่ยวข้องกับการเพิ่มกราฟที่กำหนดจากนั้นแปลงกราฟที่เพิ่มเข้ามาโดยการแทนที่จุดยอดแต่ละจุดของกราฟเดิมด้วยจุดยอดใหม่สองจุด กราฟแยกนี้เป็นกราฟการเรียงสับเปลี่ยนที่มีคุณสมบัติพิเศษก็ต่อเมื่อเป็นกราฟรูปสี่เหลี่ยมคางหมู^{[ 7 ]}${\displaystyle {G}}$${\displaystyle {F}}$${\displaystyle {G}}$${\displaystyle {G}}$${\displaystyle {G'}}$${\displaystyle {F}}$${\displaystyle {G'}}$${\displaystyle {G}}$${\displaystyle {F}}$${\displaystyle {F}}$${\displaystyle O(n^{2})}$${\displaystyle O(n(n+m))}$${\displaystyle m}$${\displaystyle {G}}$${\displaystyle {G}}$