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

กราฟสี่เหลี่ยมจัตุรัสประกอบด้วยกรณีพิเศษต่างๆ เช่นต้นไม้กราฟตารางกราฟเฟืองและกราฟของโพลีโอมีโน

นอกจากจะเป็นกราฟระนาบแล้วสแควร์กราฟยังเป็นมัธยฐานกราฟด้วย หมายความว่าสำหรับจุดยอดสามจุดu , vและwจะมีจุดยอดมัธยฐานm ( u , v , w ) เพียงจุดเดียวที่อยู่บนเส้นทางที่สั้นที่สุดระหว่างจุดยอดทั้งสามคู่^{[ 1 ]}เช่นเดียวกับมัธยฐานกราฟโดยทั่วไป สแควร์กราฟยังเป็นลูกบาศก์บางส่วน ด้วย กล่าวคือ จุดยอดของสแควร์กราฟสามารถติดป้ายกำกับด้วยสตริงไบนารี ได้ โดยที่ระยะทางแฮมมิงระหว่างสตริงจะเท่ากับระยะทางเส้นทางที่สั้นที่สุดระหว่างจุดยอด

กราฟที่ได้จากกราฟสี่เหลี่ยมโดยการสร้างจุดยอดสำหรับแต่ละโซน (ชั้นสมมูลของขอบขนานของรูปสี่เหลี่ยม) และขอบสำหรับแต่ละสองโซนที่มาบรรจบกันในรูปสี่เหลี่ยม จะเป็นกราฟวงกลมที่กำหนดโดยแผนภาพคอร์ดที่ไม่มีสามเหลี่ยม ของดิสก์หน่วย^{[ 2 ]}

กราฟสี่เหลี่ยมอาจมีลักษณะเฉพาะได้หลายวิธีนอกเหนือจากการฝังแบบระนาบ: ^{[ 2 ]}

• กราฟ เหล่านี้เป็นกราฟมัธยฐานที่ไม่ประกอบด้วยกราฟย่อยเหนี่ยวนำใดๆ ที่เป็นสมาชิกของกลุ่มกราฟต้องห้าม จำนวนอนันต์ กราฟ ต้องห้ามเหล่านี้ได้แก่ ลูกบาศก์ ( กราฟซิมเพล็กซ์ของK ₃ ), ผลคูณคาร์ทีเซียนของขอบและกรงเล็บK _1,3 (กราฟซิมเพล็กซ์ของกรงเล็บ) และกราฟที่เกิดจากกราฟเฟืองโดยการเพิ่มจุดยอดอีกหนึ่งจุดที่เชื่อมต่อกับดุมล้อ (กราฟซิมเพล็กซ์ของการรวมกันแบบไม่ทับซ้อนของวงจรที่มีจุดยอดโดดเดี่ยว)
• กราฟเหล่านี้เป็นกราฟที่เชื่อมต่อกันและ เป็นกราฟ สองส่วนโดยที่ (ถ้าเลือก จุดยอด r ใดๆ เป็น ราก ) ทุกจุดยอดจะมีเพื่อนบ้านที่อยู่ใกล้r มากที่สุดไม่เกินสองจุด และที่ทุกจุดยอดvลิงก์ของv (กราฟที่มีจุดยอดสำหรับแต่ละขอบที่เชื่อมต่อกับvและขอบสำหรับแต่ละวัฏจักร 4 มิติที่ประกอบด้วยv ) จะเป็นวัฏจักรที่มีความยาวมากกว่าสามหรือเป็นการรวมกันแบบไม่ทับซ้อนกันของเส้นทาง
• กราฟ เหล่านี้เป็นกราฟคู่ของการจัดเรียงเส้นตรงในระนาบไฮเปอร์โบลิกที่ไม่มีเส้นตรงสามเส้นตัดกัน

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

ปัญหาเชิงอัลกอริทึมหลายอย่างบนกราฟสี่เหลี่ยมอาจคำนวณได้อย่างมีประสิทธิภาพมากกว่าในกราฟระนาบหรือกราฟมัธยฐานทั่วไป ตัวอย่างเช่นChepoi, Dragan & Vaxès (2002)และChepoi, Fanciullini & Vaxès (2004)นำเสนออัลกอริทึมเวลาเชิงเส้นสำหรับการคำนวณเส้นผ่านศูนย์กลางของกราฟสี่เหลี่ยม และสำหรับการค้นหาจุดยอดที่ลดระยะทางสูงสุดไปยังจุดยอดอื่นๆ ทั้งหมดให้เหลือน้อยที่สุด