การวาดกราฟเป็นสาขาหนึ่งของคณิตศาสตร์และวิทยาศาสตร์คอมพิวเตอร์ที่ผสมผสานวิธีการจากทฤษฎีกราฟเชิงเรขาคณิตและการแสดงภาพข้อมูล เพื่อสร้างภาพ กราฟสองมิติ (หรือบางครั้งสามมิติ) ที่เกิดขึ้นจากการใช้งานต่างๆ เช่นการวิเคราะห์เครือข่ายสังคมการทำแผนที่ภาษาศาสตร์และชีวสารสนเทศ^{[ 1 ]}

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

กราฟมักถูกวาดเป็นแผนภาพโหนด-ลิงก์ โดยที่จุดยอดจะถูกแทนด้วยวงกลม กล่อง หรือป้ายกำกับข้อความ และขอบจะถูกแทนด้วยส่วนของเส้นตรงเส้นหลายเหลี่ยมหรือเส้นโค้งในระนาบยุคลิด [ ^{3 ] แผนภาพ}โหนด-ลิงก์สามารถสืบย้อนไปถึงผลงานของ Pseudo-Lull ในศตวรรษที่ 14-16 ซึ่งตีพิมพ์ภายใต้ชื่อของRamon Llullนักปราชญ์ในศตวรรษที่ 13 Pseudo-Lull วาดแผนภาพประเภทนี้สำหรับกราฟสมบูรณ์เพื่อวิเคราะห์การรวมกันแบบคู่ทั้งหมดระหว่างชุดของแนวคิดเชิงอภิปรัชญา^{[ 5 ]}

ในกรณีของกราฟแบบมีทิศทางหัวลูกศรเป็นรูปแบบกราฟิกที่ใช้กันทั่วไปเพื่อแสดงทิศทาง[ ^{2 ] อย่างไรก็ตาม}การศึกษาของผู้ใช้แสดงให้เห็นว่ารูปแบบอื่นๆ เช่น การเรียว ให้ข้อมูลนี้ได้อย่างมีประสิทธิภาพมากกว่า^{[ 6 ]}การวาดระนาบขึ้นด้านบนใช้รูปแบบที่ขอบทุกเส้นมีทิศทางจากจุดยอดที่ต่ำกว่าไปยังจุดยอดที่สูงกว่า ทำให้ไม่จำเป็นต้องใช้หัวลูกศร^{[ 7 ]}

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

มีการกำหนดมาตรวัดคุณภาพที่แตกต่างกันมากมายสำหรับการวาดกราฟ โดยพยายามหาวิธีที่เป็นกลางในการประเมินความสวยงามและความสามารถในการใช้งาน^{[ 9 ]}นอกเหนือจากการเป็นแนวทางในการเลือกวิธีการจัดวางที่แตกต่างกันสำหรับกราฟเดียวกันแล้ว วิธีการจัดวางบางวิธีพยายามที่จะปรับมาตรวัดเหล่านี้ให้เหมาะสมที่สุดโดยตรง

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

มีกลยุทธ์การจัดวางกราฟที่หลากหลาย:

• ใน ระบบ การจัดวางแบบใช้แรงซอฟต์แวร์วาดกราฟจะปรับเปลี่ยนตำแหน่งจุดยอดเริ่มต้นโดยการเคลื่อนย้ายจุดยอดอย่างต่อเนื่องตามระบบแรงที่อิงตามอุปมาอุปไมยทางกายภาพที่เกี่ยวข้องกับระบบสปริงหรือกลศาสตร์โมเลกุลโดยทั่วไป ระบบเหล่านี้จะรวมแรงดึงดูดระหว่างจุดยอดที่อยู่ติดกันเข้ากับแรงผลักระหว่างจุดยอดทุกคู่ เพื่อค้นหารูปแบบการจัดวางที่ความยาวของขอบมีขนาดเล็กในขณะที่จุดยอดอยู่ห่างกันพอสมควร ระบบเหล่านี้อาจทำการ ลดค่า ฟังก์ชันพลังงานโดยใช้การไล่ระดับความชันหรืออาจแปลงแรงโดยตรงเป็นความเร็วหรือความเร่งสำหรับจุดยอดที่เคลื่อนที่^{[ 14 ]}
• วิธี การจัดวางสเปกตรัมใช้เวกเตอร์ลักษณะเฉพาะของเมทริกซ์เช่นลาปลาเซียนที่ได้จากเมทริกซ์ประชิดของกราฟ เป็นพิกัด ^{[ 15 ]}
• วิธีการจัดวางแบบตั้งฉาก ซึ่งอนุญาตให้ขอบของกราฟวิ่งในแนวนอนหรือแนวตั้ง ขนานกับแกนพิกัดของการจัดวาง วิธีการเหล่านี้ได้รับการออกแบบมาสำหรับ ปัญหาการจัดวาง VLSIและPCB เป็นหลัก แต่ก็ได้รับการดัดแปลงสำหรับการวาดกราฟด้วย โดยทั่วไปแล้ว วิธีการเหล่านี้เกี่ยวข้องกับวิธีการหลายขั้นตอน ซึ่งกราฟอินพุตจะถูกทำให้เป็นระนาบโดยการแทนที่จุดตัดด้วยจุดยอด จะมีการค้นหาการฝังเชิงโทโพโลยีของกราฟที่เป็นระนาบ เลือกทิศทางของขอบเพื่อลดการโค้งงอ วางจุดยอดให้สอดคล้องกับทิศทางเหล่านี้ และสุดท้าย ขั้นตอนการบีบอัดการจัดวางจะลดพื้นที่ของภาพวาด^{[ 16 ]}
• อัลกอริทึมการจัดวางแบบต้นไม้เหล่านี้แสดง รูปแบบคล้าย ต้นไม้ ที่มีราก เหมาะสำหรับต้นไม้บ่อยครั้งในเทคนิคที่เรียกว่า "การจัดวางแบบบอลลูน" ลูกของแต่ละโหนดในต้นไม้จะถูกวาดบนวงกลมที่ล้อมรอบโหนด โดยรัศมีของวงกลมเหล่านี้จะลดลงที่ระดับล่างในต้นไม้ เพื่อไม่ให้วงกลมเหล่านี้ทับซ้อนกัน^{[ 17 ]}
• วิธี การวาดกราฟแบบหลายชั้น (มักเรียกว่าการวาดแบบซูกิยามะ) เหมาะที่สุดสำหรับกราฟแบบมีทิศทางที่ไม่มีวงจรหรือกราฟที่เกือบไม่มีวงจร เช่น กราฟความสัมพันธ์ระหว่างโมดูลหรือฟังก์ชันในระบบซอฟต์แวร์ ในวิธีการเหล่านี้ โหนดของกราฟจะถูกจัดเรียงเป็นชั้นแนวนอนโดยใช้วิธีการต่างๆ เช่นอัลกอริทึม Coffman–Grahamในลักษณะที่ขอบส่วนใหญ่จะลงมาจากชั้นหนึ่งไปยังอีกชั้นหนึ่ง หลังจากขั้นตอนนี้ โหนดภายในแต่ละชั้นจะถูกจัดเรียงเพื่อลดจุดตัดให้น้อยที่สุด^{[ 18 ]}

• แผนภาพส่วนโค้งซึ่งเป็นรูปแบบการจัดวางที่มีมาตั้งแต่ทศวรรษ 1960 ^{[ 19 ]}จะวางจุดยอดไว้บนเส้นตรง ขอบอาจวาดเป็นครึ่งวงกลมเหนือหรือใต้เส้นตรง หรือเป็นเส้นโค้งเรียบที่เชื่อมต่อกันจากครึ่งวงกลมหลายอัน
• วิธีการ จัดวางแบบวงกลมจะวางจุดยอดของกราฟไว้บนวงกลม โดยเลือกจัดลำดับจุดยอดรอบวงกลมอย่างระมัดระวังเพื่อลดจุดตัดและวางจุดยอดที่อยู่ติดกันให้ใกล้กัน ขอบอาจวาดเป็นคอร์ดของวงกลมหรือเป็นส่วนโค้งภายในหรือภายนอกวงกลม ในบางกรณี อาจใช้วงกลมหลายวง^{[ 20 ]}
• การวาดแบบ Dominanceจะวางจุดยอดในลักษณะที่จุดยอดหนึ่งอยู่ด้านบน ด้านขวา หรือทั้งสองอย่างของจุดยอดอื่นก็ต่อเมื่อสามารถเข้าถึงได้จากจุดยอดอื่นเท่านั้น ด้วยวิธีนี้ รูปแบบการจัดวางจะทำให้ความสัมพันธ์ในการเข้าถึงของกราฟปรากฏให้เห็นได้ชัดเจน^{[ 21 ]}

กราฟและภาพวาดกราฟที่เกิดขึ้นในสาขาการประยุกต์ใช้ด้านอื่นๆ ได้แก่

• โซซิโอแกรมภาพวาดเครือข่ายสังคมดังที่มักนำเสนอโดยซอฟต์แวร์วิเคราะห์เครือข่ายสังคม^{[ 22 ]}
• แผนภาพ Hasseซึ่งเป็นรูปแบบการวาดกราฟเฉพาะสำหรับลำดับบางส่วน^{[ 23 ]}
• Dessin d'enfantsซึ่งเป็นรูปแบบการวาดกราฟที่ใช้ในเรขาคณิตเชิงพีชคณิต^{[ 24 ]}
• แผนภาพสถานะการแสดงภาพกราฟิกของเครื่องจักรสถานะจำกัด^{[ 25 ]}
• แผนภาพเครือข่ายคอมพิวเตอร์ภาพแสดงโหนดและการเชื่อมต่อในเครือข่ายคอมพิวเตอร์^{[ 26 ]}
• ผังงานและแผนผังดรากอนคือภาพวาดที่จุดแทนขั้นตอนของอัลกอริทึมและเส้นเชื่อมแทนการควบคุมการไหลระหว่างขั้นตอนต่างๆ
• แผนผังเครือข่ายโครงการคือภาพแสดงลำดับเวลาของการดำเนินงานในโครงการ
• แผนภาพการไหลของข้อมูลคือภาพวาดที่จุด (nodes) แทนส่วนประกอบต่างๆ ของระบบสารสนเทศและเส้นเชื่อม (edges) แทนการเคลื่อนย้ายข้อมูลจากส่วนประกอบหนึ่งไปยังอีกส่วนประกอบหนึ่ง
• ชีวสารสนเทศศาสตร์รวมถึงแผนภูมิวิวัฒนาการ เครือข่าย ปฏิสัมพันธ์ระหว่างโปรตีนและวิถีการเผาผลาญ^{[ 27 ]}

นอกจากนี้ ขั้นตอน การจัดวางและการกำหนดเส้นทางของระบบอัตโนมัติในการออกแบบอิเล็กทรอนิกส์ (EDA) มีความคล้ายคลึงกับการวาดกราฟในหลายๆ ด้าน เช่นเดียวกับปัญหา การฝังแบบ โลภ (greedy embedding)ในการประมวลผลแบบกระจายและเอกสารเกี่ยวกับการวาดกราฟก็มีผลลัพธ์หลายอย่างที่ยืมมาจากเอกสาร EDA อย่างไรก็ตาม ปัญหาเหล่านี้ก็แตกต่างกันในหลายๆ ด้านที่สำคัญ เช่น ใน EDA การลดพื้นที่และความยาวของสัญญาณมีความสำคัญมากกว่าความสวยงาม และปัญหาการกำหนดเส้นทางใน EDA อาจมีเทอร์มินัลมากกว่าสองจุดต่อเน็ต ในขณะที่ปัญหาที่คล้ายคลึงกันในการวาดกราฟโดยทั่วไปจะเกี่ยวข้องกับคู่ของจุดยอดสำหรับแต่ละขอบเท่านั้น

มีอัลกอริธึมมากมายสำหรับการวาดกราฟ ซึ่งได้แก่:

• อัลกอริทึม Reingold-Tilford สำหรับการวาดต้นไม้^{[ 28 ]}
• อัลกอริทึมของ Kant ^{[ 29 ]}ซึ่งสร้างภาพวาดเส้นหลายเหลี่ยมของกราฟระนาบที่เชื่อมต่อ 3 จุด โดยที่ขนาดของมุมขั้นต่ำระหว่างส่วนโค้งมีค่าอย่างน้อย${\displaystyle {\frac {1}{d}}\pi }$โดยที่dคือดีกรีโหนดสูงสุด และการวางนัยทั่วไปซึ่งใช้ได้ดีกับกราฟระนาบอื่นๆ โดย Gutwenger และ Mutzel ^{[ 30 ]}
• อัลกอริทึมของ Tamassia สำหรับการลดจำนวนโค้งในการแสดงแบบตั้งฉากของกราฟระนาบ^{[ 31 ]}
• แบบจำลองสปริงแม่เหล็กโดย Sugiyama และ Misue ^{[ 32 ]}

ซอฟต์แวร์ ระบบ และผู้ให้บริการระบบสำหรับการวาดกราฟ ได้แก่:

• BioFabricเป็นซอฟต์แวร์โอเพนซอร์สสำหรับแสดงภาพเครือข่ายขนาดใหญ่โดยการวาดจุดเชื่อมต่อเป็นเส้นแนวนอน
• Cytoscapeซอฟต์แวร์โอเพนซอร์สสำหรับแสดงภาพเครือข่ายปฏิสัมพันธ์ระดับโมเลกุล
• Gephiซอฟต์แวร์โอเพนซอร์สสำหรับการวิเคราะห์และแสดงภาพเครือข่าย
• graph-toolเป็น ไลบรารี Python ฟรี สำหรับวิเคราะห์กราฟ
• Graphvizซึ่งเป็นระบบวาดกราฟแบบโอเพนซอร์สจากบริษัท AT&T ^{[ 33 ]}
• Linkuriousเป็นซอฟต์แวร์เชิงพาณิชย์สำหรับการวิเคราะห์และแสดงภาพเครือข่ายสำหรับฐานข้อมูลกราฟ
• Mathematicaเป็นเครื่องมือคำนวณอเนกประสงค์ที่รวมเครื่องมือแสดงภาพกราฟ 2 มิติและ 3 มิติ และเครื่องมือวิเคราะห์กราฟ^{[ 34 ]}
• Microsoft Automatic Graph Layoutไลบรารี .NET แบบโอเพนซอร์ส (เดิมชื่อ GLEE) สำหรับการจัดวางกราฟ^{[ 35 ]}
• NetworkXเป็นไลบรารี Python สำหรับศึกษาเกี่ยวกับกราฟและเครือข่าย
• Tulip [ ^{36 ]}เครื่องมือแสดงภาพข้อมูลแบบโอเพน^{ซอร์ส}
• yEdซึ่งเป็นโปรแกรมแก้ไขกราฟที่มีฟังก์ชันการจัดวางกราฟ^{[ 37 ]}
• PGF/TikZ 3.0 พร้อมgraphdrawingแพ็คเกจ (ต้องใช้LuaTeX ) ^{[ 38 ]}
• LaNet-viเป็นซอฟต์แวร์โอเพนซอร์สสำหรับแสดงภาพเครือข่ายขนาดใหญ่
• OGDF เป็นไลบรารีโอเพนซอร์สของโครงสร้างข้อมูลและอัลกอริธึม C++ ส่วนใหญ่ใช้สำหรับการวาดกราฟ^{[ 39 ]}

• การประชุมวิชาการนานาชาติว่าด้วยการวาดกราฟ
• รายชื่อเครื่องมือ Unified Modeling Language

• ไลบรารี GraphX ​​สำหรับ .NET (เก็บถาวรเมื่อ2018-01-26 ที่Wayback Machine) : ไลบรารีโอเพนซอร์สสำหรับ WPF เพื่อการคำนวณและแสดงภาพกราฟ รองรับอัลกอริธึมการจัดวางและการกำหนดเส้นทางขอบหลายแบบ
• คลังเอกสารอิเล็กทรอนิกส์เกี่ยวกับการวาดกราฟ : รวมถึงข้อมูลเกี่ยวกับบทความจาก งาน สัมมนาการวาดกราฟ ทั้งหมด