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

ชื่อกราฟเส้นมาจากบทความของHarary & Norman (1960)แม้ว่าทั้งWhitney (1932)และKrausz (1943)จะใช้โครงสร้างนี้มาก่อนหน้านั้น ก็ตาม ^{[ 1 ]}คำศัพท์อื่นๆ ที่ใช้เรียกกราฟเส้น ได้แก่กราฟครอบคลุม กราฟอนุพันธ์กราฟคู่ขอบต่อจุดยอดกราฟ สังยุค กราฟตัวแทนและกราฟθ -obrazom ^{[ 1 ]}รวมถึงกราฟขอบกราฟแลกเปลี่ยนกราฟผกผันและกราฟอนุพันธ์^{[ 2 ]}

Hassler Whitney  ( 1932 ) พิสูจน์ว่าด้วยกรณีพิเศษหนึ่งกรณี โครงสร้างของกราฟเชื่อมต่อGสามารถกู้คืนได้อย่างสมบูรณ์จากกราฟเส้น^{[ 3 ]}คุณสมบัติอื่นๆ อีกมากมายของกราฟเส้นนั้นได้มาจากการแปลคุณสมบัติของกราฟพื้นฐานจากจุดยอดไปยังขอบ และตามทฤษฎีบทของ Whitney การแปลแบบเดียวกันนี้สามารถทำได้ในทิศทางตรงกันข้ามด้วย กราฟเส้นไม่มีกรงเล็บและกราฟเส้นของกราฟสองส่วนเป็นกราฟสมบูรณ์กราฟเส้นมีลักษณะเฉพาะด้วยกราฟย่อยต้องห้าม เก้าแบบ และสามารถจดจำได้ในเวลาเชิงเส้น

มีการศึกษาขยายแนวคิดของกราฟเส้นในรูปแบบต่างๆ มากมาย รวมถึงกราฟเส้นของกราฟเส้น กราฟเส้นของมัลติกราฟกราฟเส้นของไฮเปอร์กราฟและกราฟเส้นของกราฟถ่วงน้ำหนัก

กำหนดให้กราฟGกราฟเส้นL ( G )คือกราฟที่มีคุณสมบัติว่า

• จุดยอดแต่ละ จุด ของL ( G )แทนขอบของGและ
• จุดยอดสองจุดของL ( G )จะอยู่ติดกันก็ต่อเมื่อขอบที่สอดคล้องกันของจุดยอดทั้งสองนั้นมีจุดปลายร่วมกัน ("เชื่อมต่อกัน") ในG

นั่นคือ เป็นกราฟจุดตัดของขอบของGซึ่งแสดงขอบแต่ละขอบด้วยเซตของจุดปลายทั้งสอง^{[ 2 ]}

ภาพต่อไปนี้แสดงกราฟ (ซ้าย มีจุดยอดสีน้ำเงิน) และกราฟเส้น (ขวา มีจุดยอดสีเขียว) จุดยอดแต่ละจุดในกราฟเส้นจะแสดงด้วยหมายเลขคู่ของจุดปลายของเส้นขอบที่สอดคล้องกันในกราฟต้นฉบับ ตัวอย่างเช่น จุดยอดสีเขียวทางด้านขวาที่มีหมายเลข 1,3 สอดคล้องกับเส้นขอบทางด้านซ้ายระหว่างจุดยอดสีน้ำเงิน 1 และ 3 จุดยอดสีเขียว 1,3 อยู่ติดกับจุดยอดสีเขียวอีกสามจุด ได้แก่ 1,4 และ 1,2 (ซึ่งสอดคล้องกับเส้นขอบที่มีจุดปลายร่วมกันคือ 1 ในกราฟสีน้ำเงิน) และ 4,3 (ซึ่งสอดคล้องกับเส้นขอบที่มีจุดปลายร่วมกันคือ 3 ในกราฟสีน้ำเงิน)

• 
  กราฟG
• 
  จุดยอดใน L( G ) ที่สร้างขึ้นจากขอบในG
• 
  เพิ่มขอบใน L( G )
• 
  กราฟเส้น L( G )

คุณสมบัติของกราฟGที่ขึ้นอยู่กับการประชิดกันระหว่างขอบเท่านั้น สามารถแปลเป็นคุณสมบัติที่เทียบเท่ากันในL ( G )ที่ขึ้นอยู่กับการประชิดกันระหว่างจุดยอดได้ ตัวอย่างเช่นการจับคู่ในGคือเซตของขอบที่ไม่มีขอบสองขอบใดอยู่ติดกัน และสอดคล้องกับเซตของจุดยอดในL ( G )ที่ไม่มีจุดยอดสองจุดใดอยู่ติดกัน นั่นคือเซตอิสระ^{[ 4 ]}

ดังนั้น,

• กราฟเส้นของกราฟที่เชื่อมต่อกันจะเชื่อมต่อกัน หากGเชื่อมต่อกัน จะมีเส้นทางที่เชื่อมต่อขอบสองขอบใดๆ ของกราฟ G ซึ่งแปลงเป็นเส้นทางในL ( G )ที่มีจุดยอดสองจุดใดๆ ของL ( G )อย่างไรก็ตาม กราฟGที่มีจุดยอดโดดเดี่ยวบางจุด และด้วยเหตุนี้จึงไม่เชื่อมต่อกัน อาจมีกราฟเส้นที่เชื่อมต่อกันได้^{[ 5 ]}
• กราฟเส้นจะมีจุดเชื่อมต่อก็ต่อเมื่อกราฟพื้นฐานมีสะพานซึ่งปลายทั้งสองข้างไม่มีดีกรีหนึ่ง^{[ 2 ]}
• สำหรับกราฟGที่มี จุดยอด nจุดและ ขอบ mเส้น จำนวนจุดยอดของกราฟเส้นL ( G )คือmและจำนวนขอบของL ( G )คือครึ่งหนึ่งของผลรวมของกำลังสองของ^{ดีกรี}ของจุดยอดในGลบด้วยm ^{[ 6} ]
• เซตอิสระ ในL ( G )สอดคล้องกับการจับคู่ในGโดยเฉพาะอย่างยิ่งเซตอิสระสูงสุดในL ( G )สอดคล้องกับการจับคู่สูงสุดในG เนื่องจากการจับคู่สูงสุดอาจพบได้ในเวลาพหุนาม ดังนั้นเซตอิสระสูงสุดของกราฟเส้นก็อาจพบ ได้เช่นกัน แม้ว่าปัญหาเซตอิสระสูงสุดจะยากสำหรับตระกูลกราฟทั่วไปก็ตาม^{[ 4 ]}ในทำนองเดียวกันเซตอิสระสีรุ้งในL ( G )สอดคล้องกับการจับคู่สีรุ้งในG
• จำนวนสีของขอบกราฟGเท่ากับจำนวนสีของจุดยอด^กราฟเส้นL ( G ) [ ^{7 ]}
• กราฟเส้นของกราฟที่ขอบเปลี่ยนทิศทางได้จะเป็นกราฟที่จุดยอดเปลี่ยนทิศทางได้ คุณสมบัตินี้สามารถใช้สร้างตระกูลของกราฟที่ (เช่นกราฟ Petersen ) เป็นกราฟที่จุดยอดเปลี่ยนทิศทางได้ แต่ไม่ใช่กราฟ Cayley : ถ้าGเป็นกราฟที่ขอบเปลี่ยนทิศทางได้ซึ่งมีจุดยอดอย่างน้อยห้าจุด ไม่ใช่กราฟสองส่วน และมีดีกรีของจุดยอดเป็นเลขคี่ แล้วL ( G )จะเป็นกราฟที่ไม่ใช่ Cayley ที่จุดยอดเปลี่ยนทิศทางได้^{[ 8 ]}
• ถ้ากราฟGมีวงจรออยเลอร์นั่นคือ ถ้าGเชื่อมต่อกันและมีจำนวนขอบคู่ที่แต่ละจุดยอด กราฟเส้นของGจะเป็นกราฟแฮมิลโทเนียนอย่างไรก็ตาม วงจรแฮมิลโทเนียนในกราฟเส้นไม่ได้มาจากวงจรออยเลอร์ในลักษณะนี้เสมอไป ตัวอย่างเช่น กราฟเส้นของกราฟแฮมิลโทเนียนGเองก็เป็นกราฟแฮมิลโทเนียน ไม่ว่าGจะเป็นกราฟออยเลอร์ด้วย หรือไม่ก็ตาม ^{[ 9 ]}
• ถ้ากราฟอย่างง่ายสองกราฟเป็นไอโซมอร์ฟิกกันแล้ว กราฟเส้นของกราฟทั้งสองนั้นก็จะเป็นไอโซมอร์ฟิกกันด้วยทฤษฎีบทไอโซมอร์ฟิซึมของกราฟของวิทนีย์ให้บทกลับของทฤษฎีบทนี้สำหรับกราฟเชื่อมต่อทุกคู่ ยกเว้นเพียงคู่เดียว
• ในบริบทของ ทฤษฎี เครือข่ายที่ซับซ้อนกราฟเส้นของเครือข่ายแบบสุ่มจะรักษาคุณสมบัติหลายอย่างของเครือข่ายไว้ เช่นคุณสมบัติของโลกขนาดเล็ก (การมีอยู่ของเส้นทางสั้น ๆ ระหว่างจุดยอดทุกคู่) และรูปร่างของการกระจายระดับดีกรี [ ^{10 ] Evans} & Lambiotte (2009)สังเกตว่าวิธีการใด ๆ ในการค้นหาคลัสเตอร์จุดยอดในเครือข่ายที่ซับซ้อนสามารถนำไปใช้กับกราฟเส้นและใช้ในการจัดกลุ่มขอบแทนได้

ถ้ากราฟเส้นของกราฟที่เชื่อมต่อกัน สองกราฟ เป็นไอโซมอร์ฟิก กราฟพื้นฐานก็จะเป็นไอโซมอร์ฟิกเช่นกัน ยกเว้นในกรณีของกราฟสามเหลี่ยมK ₃และกรงเล็บK _1,3ซึ่งมีกราฟเส้นที่เป็นไอโซมอร์ฟิก แต่ตัวกราฟเองไม่ใช่ไอโซมอร์ฟิก^{[ 3 ]}

นอกจากK ₃และK _1,3แล้ว ยังมีกราฟขนาดเล็กพิเศษอื่นๆ อีกบางชนิดที่มีคุณสมบัติว่ากราฟเส้นของกราฟเส้นนั้นมีระดับความสมมาตรสูงกว่าตัวกราฟเอง ตัวอย่างเช่นกราฟรูปเพชรK _1,1,2 (สามเหลี่ยมสองรูปที่ใช้ขอบร่วมกัน) มีกราฟออโตมอร์ฟิซึม สี่แบบ แต่กราฟเส้นK _1,2,2มีแปดแบบ ในภาพประกอบของกราฟรูปเพชรที่แสดง การหมุนกราฟ 90 องศาไม่ใช่ความสมมาตรของกราฟ แต่เป็นความสมมาตรของกราฟเส้น อย่างไรก็ตาม กรณีพิเศษทั้งหมดเหล่านี้มีจุดยอดอย่างมากที่สุดสี่จุด ทฤษฎีบทไอโซมอร์ฟิซึมของ Whitney เวอร์ชันที่เสริมความแข็งแกร่งขึ้นระบุว่า สำหรับกราฟที่เชื่อมต่อกันที่มีจุดยอดมากกว่าสี่จุด จะมีการจับคู่แบบหนึ่งต่อหนึ่งระหว่างไอโซมอร์ฟิซึมของกราฟและไอโซมอร์ฟิซึมของกราฟเส้น^{[ 11 ]}

ทฤษฎีบทไอโซมอร์ฟิซึมของวิทนีย์ได้รับการพิสูจน์แล้วสำหรับกราฟเส้นของมัลติกราฟแต่มีความซับซ้อนกว่าในกรณีนี้^{[ 12 ]}

กราฟเส้นของกราฟสมบูรณ์K _nเรียกอีกอย่างว่ากราฟสามเหลี่ยมกราฟจอห์นสันJ ( n , 2)หรือส่วนเติมเต็มของกราฟเนเซอร์KG _{n ,2}กราฟสามเหลี่ยมมีลักษณะเฉพาะด้วยสเปกตรัมยกเว้นn = 8 [ ^{13 ] นอกจาก}นี้ยังสามารถกำหนดลักษณะเฉพาะได้ (อีกครั้งโดยยกเว้นK ₈ ) เป็นกราฟปกติอย่างเข้มข้นที่มีพารามิเตอร์srg( n ( n − 1)/2, 2( n − 2), n − 2, 4) [ ^{14 ] กราฟ}ปกติอย่างเข้มข้นสามกราฟที่มีพารามิเตอร์และสเปกตรัมเดียวกันกับL ( K ₈ )คือกราฟชางซึ่ง อาจได้มาจากการสลับกราฟจากL ( K ₈ )

กราฟเส้นของกราฟสองส่วนเป็นกราฟสมบูรณ์ (ดูทฤษฎีบทของ Kőnig ) แต่ไม่จำเป็นต้องเป็นกราฟสองส่วน ดังตัวอย่างของกราฟกรงเล็บแสดงให้เห็น กราฟเส้นของกราฟสองส่วนเป็นส่วนประกอบสำคัญอย่างหนึ่งของกราฟสมบูรณ์ ซึ่งใช้ในการพิสูจน์ทฤษฎีบทกราฟสมบูรณ์ที่แข็งแกร่ง^{[ 15 ]}กรณีพิเศษของกราฟเหล่านี้คือกราฟของหมากรุกซึ่งเป็นกราฟเส้นของกราฟสองส่วนสมบูรณ์เช่นเดียวกับกราฟเส้นของกราฟสมบูรณ์ กราฟเหล่านี้สามารถระบุลักษณะได้โดยมีข้อยกเว้นหนึ่งประการ โดยจำนวนจุดยอด จำนวนขอบ และจำนวนเพื่อนบ้านร่วมกันสำหรับจุดที่อยู่ติดกันและไม่ติดกัน กรณีพิเศษหนึ่งประการคือL ( K _4,4 )ซึ่งมีพารามิเตอร์ร่วมกับกราฟ Shrikhandeเมื่อทั้งสองด้านของการแบ่งสองส่วนมีจำนวนจุดยอดเท่ากัน กราฟเหล่านี้จะเป็นกราฟปกติที่แข็งแกร่งอีกครั้ง^{[ 16 ]}ได้มีการแสดงให้เห็นแล้วว่า ยกเว้น C ₃ , C ₄และ C ₅กราฟปกติที่เชื่อมต่อกันทั้งหมดสามารถทำให้ไม่เป็นปกติอย่างแข็งแกร่งได้ภายในการแปลงกราฟเส้นสองเส้น^{[ 17 ]} การขยายไปสู่กราฟที่ไม่เชื่อมต่อกันจะต้อง ใช้ กราฟที่ไม่ใช่การรวมกันแบบไม่ทับซ้อนของ C ₃

โดยทั่วไปแล้ว กราฟGเรียกว่ากราฟเส้นสมบูรณ์ถ้าL ( G )เป็นกราฟสมบูรณ์กราฟเส้นสมบูรณ์คือกราฟที่ไม่มีวัฏจักรเดี่ยวที่มีความยาวคี่มากกว่าสาม^{[ 18 ]}หรือกล่าวอีกนัยหนึ่ง กราฟจะเป็นกราฟเส้นสมบูรณ์ก็ต่อเมื่อส่วนประกอบที่เชื่อมต่อกัน สองส่วนแต่ละส่วน เป็นกราฟสองส่วนหรืออยู่ในรูปแบบK ₄ (ทรงสี่หน้า) หรือK _{1,1, n} (หนังสือของสามเหลี่ยมหนึ่งรูปหรือมากกว่าที่ใช้ขอบร่วมกัน) ^{[ 19 ]}กราฟเส้นสมบูรณ์ทุกกราฟเป็นกราฟสมบูรณ์ในตัวเอง^{[ 20 ]}

กราฟเส้นทั้งหมดเป็นกราฟที่ไม่มีกรงเล็บกราฟที่ไม่มีซับกราฟเหนี่ยวนำในรูปแบบของต้นไม้สามใบ^{[ 21 ]}เช่นเดียวกับกราฟที่ไม่มีกรงเล็บโดยทั่วไป กราฟเส้นที่เชื่อมต่อกันทุกกราฟL ( G )ที่มีจำนวนขอบเป็นเลขคู่จะมี การจับคู่ ที่สมบูรณ์แบบ^{[ 22 ]}หรือกล่าวอีกนัยหนึ่งคือ ถ้ากราฟพื้นฐานGมีจำนวนขอบเป็นเลขคู่ ขอบของกราฟนั้นสามารถแบ่งออกเป็นเส้นทางสองขอบได้

กราฟเส้นของต้นไม้ คือ บล็อกกราฟที่ไม่มีกรงเล็บอย่างแท้จริง^{[ 23 ]}กราฟเหล่านี้ถูกนำมาใช้เพื่อแก้ปัญหาในทฤษฎีกราฟสุดขั้วในการสร้างกราฟที่มีจำนวนขอบและจุดยอดที่กำหนด ซึ่งต้นไม้ที่ใหญ่ที่สุดที่เหนี่ยวนำเป็นกราฟย่อยมีขนาดเล็กที่สุดเท่าที่จะเป็นไปได้^{[ 24 ]}

ค่าลักษณะเฉพาะทั้งหมดของเมทริกซ์ประชิดAของกราฟเส้นมีค่าอย่างน้อย −2 เหตุผลก็คือAสามารถเขียนได้เป็น โดยที่Jคือเมทริกซ์เหตุการณ์ ที่ไม่มีเครื่องหมาย ของกราฟเส้นก่อนหน้า และIคือเมทริกซ์เอกลักษณ์ โดยเฉพาะอย่างยิ่งA + 2 Iคือเมทริกซ์แกรมเมียนของระบบเวกเตอร์ กราฟทั้งหมดที่มีคุณสมบัตินี้เรียกว่ากราฟเส้นทั่วไป^{[ 25 ]}${\displaystyle A=J^{\mathsf {T}}J-2I}$

สำหรับกราฟG ใดๆ และจุดยอดv ใดๆ ในGเซตของขอบที่เชื่อมต่อกับvจะสอดคล้องกับคลิกในกราฟเส้นL ( G )คลิกที่เกิดขึ้นในลักษณะนี้จะแบ่งขอบของL ( G ) ออกเป็นส่วนๆ โดยแต่ละจุดยอดของL ( G )จะเป็นของคลิกเพียงสองคลิกเท่านั้น (คลิกสองคลิกที่สอดคล้องกับจุดปลายทั้งสองของขอบที่เกี่ยวข้องในG )

การมีอยู่ของการแบ่งกลุ่มดังกล่าวเป็นคลิกสามารถใช้เพื่อกำหนดลักษณะของกราฟเส้นได้: กราฟLเป็นกราฟเส้นของกราฟหรือมัลติกราฟอื่นก็ต่อเมื่อสามารถหากลุ่มคลิกในLได้ (โดยอนุญาตให้คลิกบางกลุ่มเป็นจุดยอดเดี่ยว) ที่แบ่งขอบของL ออกเป็นส่วนๆ โดยที่จุดยอดแต่ละจุดของLอยู่ในคลิกสองกลุ่มพอดี^{[ 21 ]}กราฟเส้นนั้นเป็นกราฟเส้นของกราฟ (แทนที่จะเป็นมัลติกราฟ) หากชุดคลิกนี้ตรงตามเงื่อนไขเพิ่มเติมที่ว่าไม่มีจุดยอดสองจุดใดของLอยู่ในคลิกสองกลุ่มเดียวกัน เมื่อมีกลุ่มคลิกดังกล่าวแล้ว กราฟพื้นฐานGที่Lเป็นกราฟเส้นสามารถกู้คืนได้โดยการสร้างจุดยอดหนึ่งจุดในGสำหรับแต่ละคลิก และขอบในGสำหรับแต่ละจุดยอดในLโดยมีจุดปลายของขอบเป็นคลิกสองกลุ่มที่ประกอบด้วยจุดยอดในLตามทฤษฎีบทไอโซมอร์ฟิซึมของวิทนีย์ฉบับที่เข้มงวด หากกราฟพื้นฐานGมีจุดยอดมากกว่าสี่จุด จะมีการแบ่งประเภทนี้ได้เพียงหนึ่งเดียวเท่านั้น

ตัวอย่างเช่น การกำหนดลักษณะเช่นนี้สามารถใช้เพื่อแสดงให้เห็นว่ากราฟต่อไปนี้ไม่ใช่กราฟเส้น:

ในตัวอย่างนี้ ขอบที่ขึ้นไปทางซ้ายและไปทางขวาจากจุดยอดกลางที่มีดีกรีสี่นั้นไม่มีกลุ่มคลิก (clique) ร่วมกัน ดังนั้น การแบ่งขอบของกราฟออกเป็นกลุ่มคลิกจะต้องมีกลุ่มคลิกอย่างน้อยหนึ่งกลุ่มสำหรับแต่ละขอบทั้งสามนี้ และกลุ่มคลิกทั้งสามนี้จะตัดกันที่จุดยอดกลาง ซึ่งขัดกับข้อกำหนดที่ว่าแต่ละจุดยอดจะต้องปรากฏอยู่ในกลุ่มคลิกอย่างน้อยสองกลุ่ม ดังนั้น กราฟที่แสดงจึงไม่ใช่กราฟเส้น

ลักษณะเฉพาะอีกประการหนึ่งของกราฟเส้นได้รับการพิสูจน์ในBeineke (1970) (และรายงานก่อนหน้านี้โดยไม่มีการพิสูจน์โดยBeineke (1968) ) เขาแสดงให้เห็นว่ามีกราฟขั้นต่ำเก้ากราฟที่ไม่ใช่กราฟเส้น โดยที่กราฟใดๆ ที่ไม่ใช่กราฟเส้นจะมีกราฟย่อยเหนี่ยวนำ หนึ่งในเก้ากราฟนี้ นั่นคือ กราฟจะเป็นกราฟเส้นก็ต่อเมื่อไม่มีเซตย่อยของจุดยอดใดๆ ที่เหนี่ยวนำกราฟย่อยเหนี่ยวนำหนึ่งในเก้ากราฟนี้ ในตัวอย่างข้างต้น จุดยอดสี่จุดบนสุดเหนี่ยวนำให้เกิดกรงเล็บ (นั่นคือกราฟสองส่วนสมบูรณ์K _1,3 ) ซึ่งแสดงอยู่ด้านบนซ้ายของภาพประกอบของกราฟย่อยต้องห้าม ดังนั้น ตามลักษณะเฉพาะของ Beineke ตัวอย่างนี้จึงไม่สามารถเป็นกราฟเส้นได้ สำหรับกราฟที่มีดีกรีขั้นต่ำอย่างน้อย 5 กราฟย่อยหกกราฟในคอลัมน์ซ้ายและขวาของรูปเท่านั้นที่จำเป็นในการกำหนดลักษณะเฉพาะ^{[ 26 ]}

Roussopoulos (1973)และLehot (1974)ได้อธิบายอัลกอริทึมแบบใช้เวลาเชิงเส้นสำหรับการจดจำกราฟเส้นและสร้างกราฟดั้งเดิมขึ้นใหม่Sysło (1982)ได้ขยายวิธีการเหล่านี้ไปยังกราฟแบบมีทิศทาง Degiorgi & Simon (1995)ได้อธิบายโครงสร้างข้อมูลที่มีประสิทธิภาพสำหรับการบำรุงรักษากราฟแบบไดนามิก ซึ่งอยู่ภายใต้การแทรกและการลบจุดยอด และการรักษาการแสดงผลของข้อมูลนำเข้าเป็นกราฟเส้น (เมื่อมีอยู่) ในเวลาที่แปรผันตามจำนวนขอบที่เปลี่ยนแปลงในแต่ละขั้นตอน

อัลกอริทึมของRoussopoulos (1973)และLehot (1974)อิงตามลักษณะเฉพาะของกราฟเส้นที่เกี่ยวข้องกับสามเหลี่ยมคี่ (สามเหลี่ยมในกราฟเส้นที่มีคุณสมบัติว่ามีจุดยอดอื่นอยู่ติดกับจำนวนจุดยอดของสามเหลี่ยมที่เป็นเลขคี่) อย่างไรก็ตาม อัลกอริทึมของDegiorgi & Simon (1995)ใช้เพียงทฤษฎีบทไอโซมอร์ฟิซึมของ Whitney เท่านั้น มีความซับซ้อนเนื่องจากจำเป็นต้องระบุการลบที่ทำให้กราฟที่เหลือกลายเป็นกราฟเส้น แต่เมื่อปรับให้เข้ากับปัญหาการระบุแบบคงที่แล้ว จะต้องทำการแทรกเท่านั้น และอัลกอริทึมจะดำเนินการตามขั้นตอนต่อไปนี้:

• สร้างกราฟอินพุตLโดยการเพิ่มจุดยอดทีละจุด โดยในแต่ละขั้นตอนให้เลือกจุดยอดที่จะเพิ่มซึ่งอยู่ติดกับจุดยอดที่เพิ่มไปแล้วอย่างน้อยหนึ่งจุด ในขณะที่เพิ่มจุดยอดลงในLให้รักษากราฟGไว้ซึ่งL = L ( G )หากอัลกอริทึมไม่สามารถหากราฟG ที่เหมาะสมได้ แสดงว่าอินพุตไม่ใช่กราฟเส้น และอัลกอริทึมจะหยุดทำงาน
• เมื่อเพิ่มจุดยอดvลงในกราฟL ( G )ซึ่งGมีจุดยอดสี่จุดหรือน้อยกว่านั้น อาจเกิดกรณีที่การแสดงผลในรูปแบบกราฟเส้นไม่ซ้ำกัน แต่ในกรณีนี้ กราฟที่เพิ่มเข้ามามีขนาดเล็กพอที่จะสามารถค้นหาการแสดงผลในรูปแบบกราฟเส้นได้โดยการค้นหาแบบครบถ้วนในเวลาคงที่
• เมื่อเพิ่มจุดยอดvลงในกราฟL ที่ใหญ่กว่า ซึ่งเท่ากับกราฟเส้นของกราฟG อีกกราฟหนึ่ง ให้Sเป็นกราฟย่อยของGที่เกิดจากขอบที่สอดคล้องกับจุดข้างเคียงของvในLตรวจสอบว่าSมีกลุ่มจุดยอดที่ประกอบด้วยจุดยอดหนึ่งจุดหรือสองจุดยอดที่ไม่ติดกันหรือไม่ ถ้ามีจุดยอดสองจุดในกลุ่มจุดยอด ให้ขยายGโดยการเพิ่มขอบ (ที่สอดคล้องกับv ) ที่เชื่อมต่อจุดยอดทั้งสองนี้ ถ้ามีจุดยอดเพียงจุดเดียวในกลุ่มจุดยอด ให้เพิ่มจุดยอดใหม่ลงในGโดยให้จุดยอดนั้นอยู่ติดกับจุดยอด v

แต่ละขั้นตอนใช้เวลาคงที่ หรือเกี่ยวข้องกับการค้นหาชุดจุดยอดที่ครอบคลุมจุดยอดที่มีขนาดคงที่ภายในกราฟSซึ่งมีขนาดเป็นสัดส่วนกับจำนวนจุดยอดข้างเคียงของvดังนั้น เวลาทั้งหมดสำหรับอัลกอริทึมทั้งหมดจึงเป็นสัดส่วนกับผลรวมของจำนวนจุดยอดข้างเคียงของจุดยอดทั้งหมด ซึ่ง (ตามทฤษฎีบทการจับมือ ) เป็นสัดส่วนกับจำนวนขอบที่ป้อนเข้ามา

van Rooij & Wilf (1965)พิจารณาลำดับของกราฟ

${\displaystyle G,L(G),L(L(G)),L(L(L(G))),\dots .\ }$

ผลการศึกษาแสดงให้เห็นว่า เมื่อGเป็นกราฟเชื่อมต่อ แบบจำกัด จะมีพฤติกรรมที่เป็นไปได้เพียงสี่แบบสำหรับลำดับนี้:

• ถ้าGเป็นกราฟวงจรแล้วL ( G )และกราฟถัดไปในลำดับนี้จะสมมาตรกับG เอง กราฟเหล่านี้เป็นกราฟเชื่อมต่อเพียง ^กราฟเดียวที่L ( G )สมมาตรกับG ^{[ 27} ]
• ถ้าGเป็นกรงเล็บK _1,3แล้วL ( G )และกราฟทั้งหมดที่ตามมาในลำดับนั้นจะเป็นรูปสามเหลี่ยม
• ถ้าGเป็นกราฟเส้นทางแล้ว กราฟแต่ละกราฟถัดไปในลำดับจะเป็นเส้นทางที่สั้นลงเรื่อยๆ จนกระทั่งในที่สุดลำดับจะสิ้นสุดลงด้วยกราฟว่างเปล่า
• ในกรณีที่เหลือทั้งหมด ขนาดของกราฟในลำดับนี้จะเพิ่มขึ้นอย่างไม่มีขีดจำกัดในที่สุด

หากGไม่มีการเชื่อมต่อ การจำแนกประเภทนี้จะใช้แยกกันสำหรับแต่ละองค์ประกอบของ G

สำหรับกราฟที่เชื่อมต่อกันซึ่งไม่ใช่เส้นทาง จำนวนการวนซ้ำที่สูงเพียงพอทั้งหมดของการดำเนินการกราฟเส้นจะสร้างกราฟที่เป็นแฮมิลโทเนียน^{[ 28 ]}

เมื่อกราฟระนาบGมีดีกรีสูงสุดของจุดยอดเท่ากับสาม กราฟเส้นของมันจะเป็นกราฟระนาบ และการฝังตัวแบบระนาบทุกแบบของGสามารถขยายไปสู่การฝังตัวของL ( G )ได้ อย่างไรก็ตาม มีกราฟระนาบที่มีดีกรีสูงกว่าซึ่งกราฟเส้นของมันไม่ใช่กราฟระนาบ ตัวอย่างเช่น กราฟ 5-star K1,5กราฟอัญมณี ที่เกิดจากการเพิ่มเส้นทแยงมุมสอง _เส้นที่ไม่ตัดกันภายในรูปห้าเหลี่ยมปกติ และรูปทรงหลายเหลี่ยมนูน ทั้งหมด ที่มีจุดยอดดีกรีสี่ขึ้นไป^{[ 29 ]}

โครงสร้างทางเลือกอีกแบบหนึ่งคือกราฟกลางซึ่งตรงกับกราฟเส้นสำหรับกราฟระนาบที่มีดีกรีสูงสุดสาม แต่จะเป็นกราฟระนาบเสมอ มีจุดยอดเหมือนกับกราฟเส้น แต่อาจมีขอบน้อยกว่า: จุดยอดสองจุดของกราฟกลางจะอยู่ติดกันก็ต่อเมื่อขอบสองขอบที่สอดคล้องกันอยู่ติดกันบนหน้าใดหน้าหนึ่งของการฝังระนาบ กราฟกลางของกราฟคู่ของกราฟระนาบจะเหมือนกับกราฟกลางของกราฟระนาบเดิม^{[ 30 ]}

สำหรับทรงหลายเหลี่ยมปกติหรือทรงหลายเหลี่ยมแบบง่าย การดำเนินการกราฟสื่อกลางสามารถแสดงได้ทางเรขาคณิตโดยการดำเนินการตัดจุดยอดแต่ละจุดของทรงหลายเหลี่ยมด้วยระนาบที่ผ่านจุดกึ่งกลางของขอบที่เชื่อมต่อทั้งหมด^{[ 31 ]}การดำเนินการนี้เรียกกันหลายชื่อ เช่น การตัดครั้งที่สอง^{[ 32 ]}การตัดแบบเสื่อมสภาพ^{[ 33 ]}หรือการแก้ไข^{[ 34 ]}

กราฟทั้งหมดT ( G )ของกราฟGมีองค์ประกอบ (จุดยอดหรือขอบ) ของG เป็นจุดยอด และมีขอบระหว่างสององค์ประกอบเมื่อใดก็ตามที่องค์ประกอบเหล่านั้นอยู่ติดกันหรืออยู่ใกล้กัน กราฟทั้งหมดอาจได้มาจากการแบ่งขอบแต่ละขอบของG ออกเป็นส่วนย่อย แล้วนำกราฟที่แบ่งย่อยแล้ว มายก กำลังสอง^{[ 35 ]}

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

อย่างไรก็ตาม สำหรับมัลติกราฟ จะมีจำนวนคู่ของกราฟที่ไม่สมมาตรกันที่มีกราฟเส้นเดียวกันมากขึ้น ตัวอย่างเช่น กราฟสองส่วนสมบูรณ์K _{1, n}มีกราฟเส้นเดียวกันกับกราฟไดโพลและมัลติกราฟแชนนอนที่มีจำนวนขอบเท่ากัน ถึงกระนั้นก็ยังสามารถอนุมานทฤษฎีบทสมมาตรของวิทนีย์ได้ในกรณีนี้^{[ 12 ]}

นอกจากนี้ยังสามารถขยายกราฟเส้นให้เป็นกราฟทิศทางได้อีกด้วย^{[ 37 ]}ถ้าGเป็นกราฟทิศทางกราฟเส้นทิศทางหรือไดกราฟเส้น ของ G จะมีจุดยอดหนึ่งจุดสำหรับแต่ละขอบของGจุดยอดสองจุดที่แสดงถึงขอบทิศทางจากuไปvและจากwไปxในGจะเชื่อมต่อกันด้วยขอบจากuvไปwxในไดกราฟเส้นเมื่อv = wนั่นคือ ขอบแต่ละเส้นในไดกราฟเส้นของGแสดงถึงเส้นทางทิศทางที่มีความยาวสองในG กราฟ เดอ บรูอินอาจถูกสร้างขึ้นโดยการทำซ้ำกระบวนการสร้างกราฟเส้นทิศทางนี้ โดยเริ่มจากกราฟทิศทางที่สมบูรณ์^{[ 38 ]}

ในกราฟเส้นL ( G )แต่ละจุดยอดที่มีดีกรีkในกราฟดั้งเดิมGจะสร้างขอบk ( k − 1)/2 ในกราฟเส้น สำหรับการวิเคราะห์หลายประเภท นี่หมายความว่าจุดยอดที่มีดีกรีสูงใน Gจะถูกแสดงเกินในกราฟเส้นL ( G )ตัวอย่างเช่น พิจารณาการเดินแบบสุ่มบนจุดยอดของกราฟดั้งเดิมG การ เดินนี้จะผ่านขอบe บางขอบ ด้วยความถี่fในทางกลับกัน ขอบe นี้ ถูกแมปไปยังจุดยอดที่ไม่ซ้ำกัน สมมติว่าเป็นvในกราฟเส้นL ( G )หากเราทำการเดินแบบสุ่มประเภทเดียวกันบนจุดยอดของกราฟเส้น ความถี่ที่vถูกเยี่ยมชมอาจแตกต่างจากf อย่าง สิ้นเชิง หากขอบe ของเรา ในGเชื่อมต่อกับจุดยอดที่มีดีกรีO ( k )มันจะถูกผ่าน บ่อยขึ้น O ( k² ⁾ในกราฟเส้นL ( G )กล่าวอีกนัยหนึ่ง ทฤษฎีบทไอโซมอร์ฟิซึมของกราฟ Whitney รับประกันว่ากราฟเส้นจะเข้ารหัสโทโพโลยีของกราฟG ดั้งเดิม ได้อย่างซื่อสัตย์เกือบตลอดเวลา แต่ไม่รับประกันว่าไดนามิกบนกราฟทั้งสองนี้จะมีความสัมพันธ์ที่เรียบง่าย วิธีแก้ปัญหาหนึ่งคือการสร้างกราฟเส้นที่มีน้ำหนัก นั่นคือกราฟเส้นที่มีขอบที่มีน้ำหนักมีหลายวิธีที่เป็นธรรมชาติในการทำเช่นนี้^{[ 39 ]}ตัวอย่างเช่น ถ้าขอบdและeในกราฟGอยู่ที่จุดยอดvที่มีดีกรีkแล้วในกราฟเส้นL ( G )ขอบที่เชื่อมต่อจุดยอดdและeสามารถกำหนดน้ำหนักเป็น1/( k − 1) ได้ ด้วยวิธีนี้ ขอบทุกเส้นในG (โดยที่ปลายทั้งสองข้างไม่ได้เชื่อมต่อกับจุดยอดที่มีดีกรี 1) จะมีความแข็งแรง 2 ในกราฟเส้นL ( G )ที่สอดคล้องกับปลายทั้งสองข้างที่ขอบนั้นมีในGการขยายคำจำกัดความของกราฟเส้นที่มีน้ำหนักนี้ไปยังกรณีที่กราฟG ดั้งเดิมนั้นทำได้ง่ายได้รับการกำหนดทิศทางหรือแม้แต่ถ่วงน้ำหนัก^{[ 40 ]} หลักการในทุกกรณีคือเพื่อให้แน่ใจว่ากราฟเส้นL ( G )สะท้อนถึงพลวัตและโทโพโลยีของกราฟGดั้งเดิม

ขอบของไฮเปอร์กราฟอาจประกอบกันเป็นกลุ่มของเซต ใดๆ ก็ได้ ดังนั้นกราฟเส้นของไฮเปอร์กราฟจึงเหมือนกับกราฟจุดตัดของเซตจากกลุ่มนั้น

กราฟที่ไม่ทับซ้อนกันของGซึ่งแสดงด้วยD ( G )ถูกสร้างขึ้นในลักษณะต่อไปนี้: สำหรับแต่ละขอบในGให้สร้างจุดยอดในD ( G ) ; สำหรับขอบสองขอบใดๆ ในGที่ไม่มีจุดยอดร่วมกัน ให้สร้างขอบระหว่างจุดยอดที่สอดคล้องกันในD ( G ) [ ^{41 ] กล่าว}อีกนัยหนึ่งD ( G )คือกราฟส่วนเติมเต็มของL ( G )กลุ่มในD ( G )สอดคล้องกับเซตอิสระในL ( G )และในทางกลับ กัน

• กราฟเส้น , ระบบสารสนเทศเกี่ยวกับกราฟ (เนื้อหาในชั้นเรียน)
• ไวส์สไตน์, เอริค ดับเบิลยู. "กราฟเส้น" . แมธเวิลด์ .