ในทฤษฎีกราฟซึ่งเป็นสาขาหนึ่งของคณิตศาสตร์ส่วนประกอบที่เชื่อมต่อสามจุดของกราฟที่เชื่อมต่อสองจุดคือ ระบบของกราฟขนาดเล็กที่อธิบายการตัดจุดยอด 2 จุดทั้งหมดในกราฟต้นไม้ SPQRเป็น โครงสร้างข้อมูลแบบต้นไม้ที่ใช้ในวิทยาศาสตร์คอมพิวเตอร์และโดยเฉพาะอย่างยิ่งในอัลกอริทึมกราฟเพื่อแสดงส่วนประกอบที่เชื่อมต่อสามจุดของกราฟ ต้นไม้ SPQR ของกราฟสามารถสร้างได้ในเวลาเชิงเส้น^{[ 1 ]}และมีการใช้งานหลายอย่างในอัลกอริทึมกราฟแบบไดนามิกและ การ วาด กราฟ

โครงสร้างพื้นฐานที่อยู่เบื้องหลังต้นไม้ SPQR ส่วนประกอบที่เชื่อมต่อกันสามจุดของกราฟ และความเชื่อมโยงระหว่างการแยกส่วนนี้กับการฝังระนาบของกราฟระนาบได้รับการศึกษาครั้งแรกโดยSaunders Mac Lane  ( 1937 ) โครงสร้างเหล่านี้ถูกนำไปใช้ในอัลกอริทึมที่มีประสิทธิภาพโดยนักวิจัยคนอื่นๆ อีกหลายคน^{[ 2 ]}ก่อนที่จะได้รับการกำหนดรูปแบบอย่างเป็นทางการเป็นต้นไม้ SPQR โดย Di Battista และ Tamassia ( 1989 , 1990 , 1996 )

ต้นไม้ SPQR มีลักษณะเป็นต้นไม้ที่ไม่มีรากโดยที่แต่ละโหนดxจะมีกราฟแบบไม่มีทิศทางหรือมัลติกราฟG _x ที่เกี่ยวข้อง โหนดและกราฟที่เกี่ยวข้องกับโหนดนั้นอาจมีประเภทใดประเภทหนึ่งจากสี่ประเภท โดยใช้ตัวย่อ SPQR:

• ในโหนด S กราฟที่เกี่ยวข้องจะเป็นกราฟวงจรที่มีจุดยอดและขอบตั้งแต่สามจุดขึ้นไป กรณีนี้คล้ายคลึงกับการประกอบอนุกรมในกราฟอนุกรม-ขนานโดยที่ S ย่อมาจาก "อนุกรม" ^{[ 3 ]}
• ในโหนด P กราฟที่เกี่ยวข้องคือกราฟไดโพลซึ่งเป็นมัลติกราฟที่มีสองจุดยอดและสามขอบขึ้นไปเป็นคู่ระนาบของกราฟวงจร กรณีนี้คล้ายคลึงกับการประกอบแบบขนานในกราฟอนุกรม-ขนาน โดยที่ P ย่อมาจาก "ขนาน" ^{[ 3 ]}
• ในโหนด Q กราฟที่เกี่ยวข้องจะมีขอบจริงเพียงเส้นเดียว กรณีที่เรียบง่ายนี้จำเป็นต่อการจัดการกับกราฟที่มีขอบเพียงเส้นเดียว ในงานวิจัยบางชิ้นเกี่ยวกับต้นไม้ SPQR โหนดประเภทนี้จะไม่ปรากฏในต้นไม้ SPQR ของกราฟที่มีขอบมากกว่าหนึ่งเส้น ในขณะที่งานวิจัยอื่นๆ กำหนดให้ขอบที่ไม่ใช่ขอบเสมือนทั้งหมดต้องแสดงด้วยโหนด Q ที่มีขอบจริงหนึ่งเส้นและขอบเสมือนหนึ่งเส้น และขอบในโหนดประเภทอื่นๆ จะต้องเป็นขอบเสมือนทั้งหมด
• ในโหนด R กราฟที่เกี่ยวข้องจะเป็นกราฟที่เชื่อมต่อ 3 จุด ซึ่งไม่ใช่วัฏจักรหรือไดโพล R ย่อมาจาก "rigid" (แข็ง) ในการประยุกต์ใช้ต้นไม้ SPQR ในการฝังกราฟระนาบ กราฟที่เกี่ยวข้องของโหนด R จะมีการฝังระนาบที่ไม่ซ้ำกัน^{[ 3 ]}

แต่ละขอบxyระหว่างสองโหนดของต้นไม้ SPQR จะเชื่อมโยงกับขอบเสมือนแบบมี ทิศทางสองขอบ โดยขอบหนึ่งเป็นขอบในกราฟG _xและอีกขอบหนึ่งเป็นขอบใน กราฟ G _yแต่ละขอบในกราฟG _xอาจเป็นขอบเสมือนสำหรับขอบของต้นไม้ SPQR ได้เพียงหนึ่งขอบเท่านั้น

ต้นไม้ SPQR Tแทนกราฟ 2-เชื่อมต่อG _Tซึ่งสร้างขึ้นดังนี้ เมื่อใดก็ตามที่ขอบxy ของต้นไม้ SPQR เชื่อมต่อขอบเสมือนabของG _xกับขอบเสมือนcdของG _yให้สร้างกราฟขนาดใหญ่ขึ้นโดยการรวมaและcเข้าเป็นซูเปอร์เวอร์เท็กซ์เดียว รวมbและdเข้าเป็นซูเปอร์เวอร์เท็กซ์อีกอันหนึ่ง และลบขอบเสมือนทั้งสองออก นั่นคือ กราฟขนาดใหญ่ขึ้นคือผลรวมของคลิก 2 จุดของG _xและG _yการดำเนินการขั้นตอนการเชื่อมต่อนี้กับขอบแต่ละขอบของต้นไม้ SPQR จะสร้างกราฟG _Tขึ้นมา ลำดับของการดำเนินการขั้นตอนการเชื่อมต่อไม่มีผลต่อผลลัพธ์ จุดยอดแต่ละจุดในกราฟG _x จุดใดจุดหนึ่ง อาจถูกเชื่อมต่อด้วยวิธีนี้กับจุดยอดที่ไม่ซ้ำกันในG _Tซึ่งเป็นซูเปอร์เวอร์เท็กซ์ที่ถูกรวมเข้าไป

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

ต้นไม้ SPQR ของกราฟที่เชื่อมต่อจุดยอด 2 จุดที่กำหนด สามารถสร้างได้ในเวลาเชิงเส้น^{[ 1 ]}

ปัญหาการสร้างส่วนประกอบเชื่อมต่อสามทางของกราฟได้รับการแก้ไขในเวลาเชิงเส้นเป็นครั้งแรกโดยHopcroft & Tarjan (1973)โดยอิงจากอัลกอริทึมนี้Di Battista & Tamassia (1996)เสนอว่าโครงสร้างต้นไม้ SPQR ทั้งหมด ไม่ใช่แค่รายการส่วนประกอบ ควรจะสามารถสร้างได้ในเวลาเชิงเส้น หลังจากที่มีการนำอัลกอริทึมที่ช้ากว่าสำหรับต้นไม้ SPQR มาใช้ในไลบรารี GDToolkit แล้วGutwenger & Mutzel (2001)ก็ได้นำเสนอการใช้งานในเวลาเชิงเส้นเป็นครั้งแรก ในกระบวนการนำอัลกอริทึมนี้มาใช้ พวกเขายังได้แก้ไขข้อผิดพลาดบางประการในงานก่อนหน้าของHopcroft & Tarjan (1973)ด้วย

อัลกอริทึมของGutwenger & Mutzel (2001)ประกอบด้วยขั้นตอนโดยรวมดังต่อไปนี้

1. เรียงลำดับขอบของกราฟตามคู่ดัชนีตัวเลขของจุดปลาย โดยใช้การเรียงลำดับแบบRadix Sortที่ทำการเรียงลำดับแบบBucket Sort สองรอบ รอบละหนึ่งจุดปลาย หลังจากขั้นตอนการเรียงลำดับนี้ ขอบคู่ขนานระหว่างจุดยอดสองจุดเดียวกันจะอยู่ติดกันในรายการที่เรียงลำดับแล้ว และสามารถแยกออกเป็นโหนด P ของต้นไม้ SPQR ในที่สุด ทำให้กราฟที่เหลือเป็นกราฟแบบง่าย
2. แบ่งกราฟออกเป็นส่วนประกอบย่อย ซึ่งสามารถสร้างขึ้นได้โดยการหาคู่จุดยอดที่แยกออกจากกัน แบ่งกราฟที่จุดยอดทั้งสองนี้ออกเป็นกราฟย่อยสองกราฟ (โดยมีขอบเสมือนคู่หนึ่งที่เชื่อมต่อกันโดยมีจุดยอดที่แยกออกจากกันเป็นจุดปลาย) และทำซ้ำกระบวนการแบ่งนี้จนกว่าจะไม่มีคู่จุดยอดที่แยกออกจากกันอีกต่อไป การแบ่งส่วนที่พบในลักษณะนี้ไม่ได้ถูกกำหนดอย่างเฉพาะเจาะจง เนื่องจากส่วนของกราฟที่ควรจะกลายเป็นโหนด S ของต้นไม้ SPQR จะถูกแบ่งย่อยออกเป็นรูปสามเหลี่ยมหลายรูป
3. กำหนดป้ายกำกับให้กับส่วนประกอบที่แยกออกแต่ละส่วนด้วย P (ส่วนประกอบที่แยกออกที่มีสองจุดยอดและมีขอบหลายเส้น), S (ส่วนประกอบที่แยกออกในรูปทรงสามเหลี่ยม) หรือ R (ส่วนประกอบที่แยกออกอื่นๆ) หากมีส่วนประกอบที่แยกออกสองส่วนที่ใช้ขอบเสมือนร่วมกัน และทั้งสองส่วนมีประเภท S หรือทั้งสองส่วนมีประเภท P ให้รวมส่วนประกอบทั้งสองเข้าเป็นส่วนประกอบขนาดใหญ่เพียงส่วนเดียวที่มีประเภทเดียวกัน

เพื่อค้นหาส่วนประกอบที่แยกออกGutwenger & Mutzel (2001)ใช้การค้นหาแบบเจาะลึก (depth-first search)เพื่อค้นหาโครงสร้างที่พวกเขาเรียกว่าต้นปาล์ม ซึ่งเป็นต้นไม้จากการค้นหาแบบเจาะลึกที่มีขอบหันออกจากรากของต้นไม้สำหรับขอบที่อยู่ในต้นไม้ และหันเข้าหารากสำหรับขอบอื่นๆ ทั้งหมด จากนั้นพวกเขาก็ค้นหาการ กำหนดหมายเลข แบบพรีออร์เดอร์ พิเศษ ของโหนดในต้นไม้ และใช้รูปแบบบางอย่างในการกำหนดหมายเลขนี้เพื่อระบุคู่ของจุดยอดที่สามารถแยกกราฟออกเป็นส่วนประกอบที่เล็กลงได้ เมื่อพบส่วนประกอบด้วยวิธีนี้แล้ว จะใช้ โครงสร้างข้อมูลแบบสแต็ก (stack data structure)เพื่อระบุขอบที่ควรเป็นส่วนหนึ่งของส่วนประกอบใหม่

ด้วยโครงสร้างต้นไม้ SPQR ของกราฟG (ที่ไม่มีโหนด Q) เราสามารถหาคู่ของจุดยอดuและvในG ได้อย่างง่ายดาย โดยที่เมื่อลบuและv ออก จากGแล้วจะได้กราฟที่ไม่เชื่อมต่อกัน และยังสามารถหาองค์ประกอบที่เชื่อมต่อกันของกราฟที่เหลืออยู่ได้อีกด้วย:

• จุดยอดuและvอาจเป็นจุดปลายทั้งสองของขอบเสมือนในกราฟที่เชื่อมโยงกับโหนด R และโหนด S หรือ R ซึ่งในกรณีนี้ ส่วนประกอบทั้งสองจะถูกแทนด้วยต้นไม้ย่อยสองต้นของต้นไม้ SPQR ที่เกิดจากการลบขอบต้นไม้ SPQR ที่เกี่ยวข้องออก
• จุดยอดuและvอาจเป็นจุดยอดสองจุดในกราฟที่เชื่อมโยงกับโหนด P ซึ่งมีขอบเสมือนสองเส้นขึ้นไป ในกรณีนี้ ส่วนประกอบที่เกิดจากการลบuและvจะถูกแทนด้วยต้นไม้ย่อยของต้นไม้ SPQR โดยแต่ละต้นไม้ย่อยแทนขอบเสมือนแต่ละเส้นในโหนดนั้น
• จุดยอดuและvอาจเป็นจุดยอดสองจุดในกราฟที่เชื่อมโยงกับโหนด S โดยที่uและvไม่ติดกัน หรือขอบuvเป็นขอบเสมือน หากขอบเป็นขอบเสมือน คู่ ( u , v ) ก็จะอยู่ในโหนดประเภท P หรือ R ด้วย และส่วนประกอบจะเป็นไปตามที่อธิบายไว้ข้างต้น หากจุดยอดสองจุดไม่ติดกัน ส่วนประกอบทั้งสองจะถูกแทนด้วยเส้นทางสองเส้นของกราฟวงจรที่เชื่อมโยงกับโหนด S และด้วยโหนดต้นไม้ SPQR ที่เชื่อมต่อกับเส้นทางทั้งสองนั้น

จำนวนการตัด 2 จุดยอดของGกำหนดโดยจำนวนขอบในต้นไม้ SPQR บวกกับจำนวนคู่จุดยอดที่ไม่ติดกันในวงจรที่สอดคล้องกัน สำหรับทุกโหนด S ที่มี k จุดยอด (เช่น k ( k − 3)/2)

ถ้ากราฟระนาบเชื่อมต่อแบบ 3 จุด จะมีการฝังตัวแบบระนาบที่ไม่ซ้ำกัน ขึ้นอยู่กับการเลือกหน้าที่จะเป็นหน้านอกและทิศทางของการฝังตัว: หน้าของการฝังตัวคือวงจรที่ไม่แยกออกจากกันของกราฟ อย่างไรก็ตาม สำหรับกราฟระนาบ (ที่มีจุดยอดและขอบที่มีป้ายกำกับ) ที่เชื่อมต่อแบบ 2 จุดแต่ไม่เชื่อมต่อแบบ 3 จุด อาจมีอิสระมากขึ้นในการค้นหาการฝังตัวแบบระนาบ โดยเฉพาะอย่างยิ่ง เมื่อใดก็ตามที่โหนดสองโหนดในต้นไม้ SPQR ของกราฟเชื่อมต่อกันด้วยขอบเสมือนคู่หนึ่ง ก็สามารถพลิกทิศทางของโหนดหนึ่ง (แทนที่ด้วยภาพสะท้อน) เทียบกับอีกโหนดหนึ่งได้ นอกจากนี้ ในโหนด P ของต้นไม้ SPQR ส่วนต่างๆ ของกราฟที่เชื่อมต่อกับขอบเสมือนของโหนด P อาจถูกสลับตำแหน่ง ได้ตามอำเภอใจ การแสดงแบบระนาบทั้งหมดสามารถอธิบายได้ด้วยวิธีนี้^{[ 4 ]}

• ต้นไม้ตัดบล็อก (Block-cut tree)เป็นโครงสร้างต้นไม้ที่คล้ายกันสำหรับส่วนประกอบที่เชื่อมต่อกันด้วย 2 จุดยอด
• ต้นไม้โกโมรี-ฮู (Gomory–Hu tree)เป็นโครงสร้างต้นไม้ที่แตกต่างออกไป ซึ่งใช้ในการอธิบายการเชื่อมต่อของขอบในกราฟ
• การแบ่งย่อยต้นไม้ซึ่งเป็นการขยายความ (ไม่ใช่สิ่งเฉพาะอีกต่อไป) ไปสู่การแบ่งย่อยที่ใหญ่ขึ้น

• การนำโครงสร้างข้อมูลแบบ SPQR tree มาใช้ใน Open Graph Drawing Framework
• โครงสร้างต้นไม้ของส่วนประกอบที่เชื่อมต่อกันสามทาง (Triconnected Components)ในการใช้งาน Java โดยใช้ไลบรารี jBPT (ดูคลาส TCTree)