มิติของทางหลวงเป็นพารามิเตอร์กราฟที่ใช้สร้างแบบจำลองเครือข่ายการขนส่งเช่นเครือข่ายถนนหรือ เครือข่าย ขนส่งสาธารณะ Abraham et al. ^{[ 1 ]}เป็นผู้กำหนดนิยามอย่างเป็นทางการเป็นครั้งแรก โดยอิงจากการสังเกตของ Bast et al. ^{[ 2 ] [ 3 ]}ที่ว่าเครือข่ายถนนใดๆ ก็ตามจะมี "จุดเชื่อมต่อ" ที่กระจัดกระจายอยู่ ดังนั้นการขับรถจากจุด A ไปยังจุด B ที่อยู่ไกลออกไปตามเส้นทางที่สั้นที่สุดจะต้องผ่านจุดเชื่อมต่อเหล่านี้อย่างน้อยหนึ่งจุดเสมอ นอกจากนี้ยังมีการเสนอว่ามิติของทางหลวงสามารถจับคุณสมบัติของ เครือข่าย ขนส่งสาธารณะได้ดี เนื่องจากเส้นทางที่ยาวกว่าโดยใช้รถบัสรถไฟหรือเครื่องบินมัก จะได้รับการบริการจาก ศูนย์กลางการขนส่งขนาดใหญ่(สถานีและสนามบิน) ซึ่งเกี่ยวข้องกับแบบแผนการกระจายแบบก้าน-ศูนย์กลางในการเพิ่มประสิทธิภาพโครงสร้างการขนส่ง

มีคำจำกัดความของมิติทางหลวงอยู่หลายแบบ^{[ 4 ]}แม้ว่าคำจำกัดความที่อิงตามเส้นทางที่สั้นที่สุดโดยประมาณที่ระบุไว้ด้านล่างจะเป็นคำจำกัดความที่ครอบคลุมที่สุดก็ตาม คำจำกัดความของมิติทางหลวงแต่ละแบบใช้เซตของเส้นทางที่สั้นที่สุด (โดยประมาณ) ที่กำหนดไว้ : กำหนดกราฟ ที่มีความยาวขอบให้ประกอบด้วยเซตของจุดยอดทุกจุดที่เหนี่ยวนำให้เกิดเส้นทางที่สั้นที่สุดระหว่างจุดยอดคู่ใดคู่หนึ่งของตามความยาวขอบในการวัดมิติทางหลวง เราจะกำหนด "ความเบาบาง" ของเซตของเส้นทางที่สั้นที่สุดในพื้นที่เฉพาะของกราฟ ซึ่งเรากำหนดลูกบอลรัศมีรอบจุดยอดให้เป็นเซต ของจุดยอดที่อยู่ห่าง จากในระยะทางไม่เกินตามความยาวขอบในบริบทของกราฟที่มีมิติทางหลวงต่ำ จุดยอดของเซตของเส้นทางที่สั้นที่สุดเรียกว่าฮับ ${\displaystyle G=(V,E)}$${\displaystyle \ell :E\to \mathbb {R} ^{+}}$${\displaystyle {\mathcal {P}}}$${\displaystyle P\subseteq V}$${\displaystyle P}$${\displaystyle G}$${\displaystyle \ell }$${\displaystyle {\mathcal {P}}}$${\displaystyle r>0}$${\displaystyle u\in V}$${\displaystyle B_{r}(u)\subseteq V}$${\displaystyle r}$${\displaystyle u}$${\displaystyle G}$${\displaystyle \ell }$

นิยามดั้งเดิม^{[ 1 ]}ของมิติทางหลวงวัดความหนาแน่นของชุดศูนย์กลางของเส้นทางที่สั้นที่สุดที่บรรจุอยู่ภายในทรงกลมรัศมี:${\displaystyle H}$${\displaystyle 4r}$

มิติของทางหลวงคือจำนวนเต็มที่เล็กที่สุดซึ่งสำหรับรัศมีใดๆและโหนดใดๆจะมีเซตที่กระทบที่มีขนาดไม่เกินสำหรับเส้นทางที่สั้นที่สุดทั้งหมดที่มีความยาวมากกว่าซึ่ง${\displaystyle G}$${\displaystyle h_{1}}$${\displaystyle r>0}$${\displaystyle u\in V}$${\displaystyle H\subseteq B_{4r}(u)}$${\displaystyle h_{1}}$${\displaystyle P\in {\mathcal {P}}}$${\displaystyle r}$${\displaystyle P\subseteq B_{4r}(u)}$

รูปแบบหนึ่งของคำจำกัดความนี้ใช้ลูกบอลที่มีรัศมีสำหรับค่าคงที่บางค่าการเลือกค่าคงที่ที่มากกว่า 4 บ่งบอกถึงคุณสมบัติเชิงโครงสร้างเพิ่มเติมของกราฟที่มีมิติทางหลวงที่จำกัด ซึ่งสามารถใช้ประโยชน์ในเชิงอัลกอริทึมได้^{[ 5 ]}${\displaystyle cr}$${\displaystyle c>4}$

คำจำกัดความต่อมา^{[ 6 ]}ของมิติทางหลวงจะวัดความหนาแน่นของชุดศูนย์กลางของเส้นทางที่สั้นที่สุดที่ตัดกับลูกบอลที่มีรัศมี:${\displaystyle H}$${\displaystyle 2r}$

มิติของทางหลวงคือจำนวนเต็มที่เล็กที่สุดซึ่งสำหรับรัศมีใดๆและโหนดใดๆจะมีเซตที่กระทบที่มีขนาดไม่เกินสำหรับเส้นทางที่สั้นที่สุดทั้งหมด ที่มี ความยาวมากกว่าและไม่เกินซึ่ง${\displaystyle G}$${\displaystyle h_{2}}$${\displaystyle r>0}$${\displaystyle u\in V}$${\displaystyle H\subseteq V}$${\displaystyle h_{2}}$${\displaystyle P\in {\mathcal {P}}}$${\displaystyle r}$${\displaystyle 2r}$${\displaystyle P\cap B_{2r}(u)\neq \emptyset }$

คำจำกัดความนี้อ่อนกว่าคำจำกัดความแรก กล่าวคือ กราฟทุกกราฟที่มีมิติทางหลวงจะมีมิติทางหลวงด้วยแต่ไม่ใช่ในทางกลับกัน^{[ 5 ]}${\displaystyle h_{1}}$${\displaystyle h_{2}}$

สำหรับคำจำกัดความที่สาม^{[ 7 ]}ของมิติทางหลวง เราได้แนะนำแนวคิดของ "เส้นทางพยาน": สำหรับรัศมีที่กำหนดเส้นทางที่สั้นที่สุดจะมีเส้นทางพยาน -ถ้ามีความยาวมากกว่าและสามารถหาได้จากโดยการเพิ่มจุดยอดไม่เกินหนึ่งจุดที่ปลายทั้งสองข้างของ(กล่าวคือมีจุดยอดมากกว่าไม่เกิน 2 จุดและจุดยอดเพิ่มเติมเหล่านี้อยู่ติดกับ) โปรดทราบว่าอาจสั้นกว่าแต่ อยู่ใน ซึ่งมีความ ยาวมากกว่า${\displaystyle r}$${\displaystyle P\in {\mathcal {P}}}$${\displaystyle r}$${\displaystyle Q\in {\mathcal {P}}}$${\displaystyle Q}$${\displaystyle r}$${\displaystyle Q}$${\displaystyle P}$${\displaystyle P}$${\displaystyle Q}$${\displaystyle P}$${\displaystyle P}$${\displaystyle P}$${\displaystyle r}$${\displaystyle Q}$${\displaystyle r}$

มิติของทางหลวงคือจำนวนเต็มที่เล็กที่สุดซึ่งสำหรับรัศมีใดๆและโหนดใดๆจะมีเซตที่กระทบที่มีขนาดไม่เกินสำหรับเส้นทางที่สั้นที่สุดทั้งหมดที่มีเส้นทางพยาน -witness ที่มี${\displaystyle G}$${\displaystyle h_{3}}$${\displaystyle r>0}$${\displaystyle u\in V}$${\displaystyle H\subseteq V}$${\displaystyle h_{3}}$${\displaystyle P\in {\mathcal {P}}}$${\displaystyle r}$${\displaystyle Q}$${\displaystyle Q\cap B_{2r}(u)\neq \emptyset }$

คำจำกัดความนี้แข็งแกร่งกว่าข้างต้น กล่าวคือ กราฟทุกกราฟที่มีมิติทางหลวงจะมีมิติทางหลวงด้วยแต่ไม่สามารถจำกัดในแง่ของ^{[ 5 ]}${\displaystyle h_{1}}$${\displaystyle h_{3}=O(h_{1}^{2})}$${\displaystyle h_{1}}$${\displaystyle h_{3}}$

การพัฒนาล่าสุด^{[ 8 ]}ได้นำเสนอคำจำกัดความที่ผ่อนคลายของมิติทางหลวงที่พิจารณาเส้นทางที่สั้นที่สุดโดยประมาณ ในกรณีนี้ มิติทางหลวงไม่ใช่ค่า แต่เป็นฟังก์ชัน ซึ่งสำหรับค่าใดๆจะให้ความเบาบางของชุดฮับ โดยที่จะกำหนดว่าเราต้องการอยู่ใกล้กับเส้นทางที่สั้นที่สุดจริงมากแค่ไหน${\displaystyle \varepsilon }$${\displaystyle \varepsilon }$

กราฟถ่วงน้ำหนักมีมิติทางหลวงถ้าสำหรับทุกและจะมีเซตย่อยที่มีจุดยอด อยู่ ซึ่งคุณสมบัติของทรงกลมต่อไปนี้เป็นจริงสำหรับทุกคู่ของจุดยอด ที่มีระยะห่างมากกว่าจะมีเส้นทางที่มีความยาวไม่เกินระยะห่างจากไปยังซึ่งตัดกับ${\displaystyle G}$${\displaystyle h:\mathbb {R} _{\geq 0}\to \mathbb {N} \cup \{\infty \}}$${\displaystyle \varepsilon \geq 0}$${\displaystyle v\in V}$${\displaystyle H_{\varepsilon }\subseteq V}$${\displaystyle |H_{\varepsilon }|\leq h(\varepsilon )}$${\displaystyle B=B_{(4+8\varepsilon )r}(v)}$${\displaystyle u,z\in B}$${\displaystyle r}$${\displaystyle uz}$${\displaystyle P}$${\displaystyle (1+\varepsilon )}$${\displaystyle u}$${\displaystyle z}$${\displaystyle P}$${\displaystyle H_{\varepsilon }}$

การผ่อนปรนนี้เป็นการขยายคำจำกัดความเดิม และยังรวมถึงช่องว่างที่เพิ่มเป็นสองเท่าทั้งหมดด้วย^{[ 8 ]}

แนวคิดที่เกี่ยวข้องอย่างใกล้ชิดกับมิติของทางหลวงคือการครอบคลุมเส้นทางที่สั้นที่สุด^{[ 1 ]}โดยที่ลำดับของตัวบ่งปริมาณในคำจำกัดความจะกลับกัน กล่าวคือ แทนที่จะมีชุดฮับสำหรับแต่ละลูกบอล จะมีชุดฮับหนึ่งชุดซึ่งกระจัดกระจายในทุกลูกบอล${\displaystyle H}$

เมื่อกำหนดรัศมี n แล้วชุดเส้นทางที่สั้นที่สุดของคือชุดเส้นทางที่สั้นที่สุดทั้งหมดในที่มีความยาวมากกว่าและไม่เกิน n ชุด เส้นทางที่สั้นที่สุดจะเรียกว่าชุด เส้นทางที่เบาบาง เฉพาะที่ (locally -sparse)หากโหนดใดๆในลูกบอลมีจุดยอดไม่เกิน n จุดของn นั่นคือ n = n${\displaystyle r>0}$${\displaystyle r}$${\displaystyle G}$${\displaystyle H\subseteq V}$${\displaystyle {\mathcal {P}}}$${\displaystyle r}$${\displaystyle 2r}$${\displaystyle r}$${\displaystyle H}$${\displaystyle h}$${\displaystyle u\in V}$${\displaystyle B_{2r}(u)}$${\displaystyle h}$${\displaystyle H}$${\displaystyle |B_{2r}(u)\cap H|\leq h}$

กราฟทุกกราฟที่มีมิติทางหลวงจำกัด(ตามคำจำกัดความข้างต้น) ยังมีการครอบคลุมเส้นทางที่สั้นที่สุดแบบเบาบาง เฉพาะที่สำหรับทุกค่า แต่ไม่ใช่ในทางกลับกัน^{[ 4 ]}เพื่อวัตถุประสงค์ทางอัลกอริทึม มักจะสะดวกกว่าที่จะทำงานกับเซตการกระทบหนึ่งชุดสำหรับแต่ละรัศมีซึ่งทำให้การครอบคลุมเส้นทางที่สั้นที่สุดเป็นเครื่องมือสำคัญสำหรับอัลกอริทึมบนกราฟที่มีมิติทางหลวงจำกัด แม้แต่คำจำกัดความที่ผ่อนคลายของมิติทางหลวงโดยใช้เส้นทางที่สั้นที่สุดโดยประมาณก็สามารถแสดงให้เห็นว่ายอมรับการครอบคลุมเส้นทางที่สั้นที่สุดแบบเบาบางได้^{[ 8 ]}${\displaystyle h}$${\displaystyle h}$${\displaystyle r}$${\displaystyle r>0}$${\displaystyle r}$

มิติของทางหลวงรวมคุณสมบัติเชิงโครงสร้างและเมตริกของกราฟเข้าด้วยกัน จึงไม่สามารถเปรียบเทียบกับพารามิเตอร์เชิงโครงสร้างและเมตริกทั่วไปได้ โดยเฉพาะอย่างยิ่ง สำหรับกราฟใดๆ ก็ตาม สามารถเลือกความยาวขอบเพื่อให้มิติของทางหลวงเป็น[ ^{5 ] ใน}ขณะเดียวกัน กราฟบางประเภทที่มีโครงสร้างที่เรียบง่ายมาก เช่น ต้นไม้ สามารถมีมิติของทางหลวงที่ใหญ่มากได้ตามอำเภอใจ ซึ่งหมายความว่าพารามิเตอร์มิติของทางหลวงไม่สามารถเปรียบเทียบกับพารามิเตอร์เชิงโครงสร้างของกราฟ เช่นtreewidth , cliquewidthหรือminor-freeness ได้ ในทางกลับกัน กราฟรูปดาวที่มีความยาวขอบเป็นหน่วยจะมีมิติของทางหลวง(ตามคำจำกัดความ 1 และ 2 ข้างต้น) แต่ มี มิติการคูณสอง เท่าที่ไม่จำกัด ในขณะที่กราฟแบบกริดที่มีความยาวขอบเป็นหน่วยจะมีมิติการคูณสอง เท่าคงที่ แต่มีมิติของทางหลวง[ ^{1 ] ซึ่ง}หมายความว่ามิติของทางหลวงตามคำจำกัดความ 1 และ 2 ก็ไม่สามารถเปรียบเทียบกับมิติการคูณสองเท่าได้เช่น กัน กราฟใดๆ ที่มีมิติทางหลวงที่จำกัดตามคำจำกัดความที่ 3 ข้างต้น จะมีมิติการคูณสองเท่าที่จำกัดด้วย^{[ 7 ]}ในทางตรงกันข้าม มิติทางหลวงที่กำหนดโดยใช้เส้นทางที่สั้นที่สุดโดยประมาณจะทำให้มิติการคูณสองเท่าเป็นแบบทั่วไป^{[ 8 ]}กล่าวคือ เมตริกใดๆ ที่มีมิติการคูณสองเท่าที่จำกัด จะมีมิติทางหลวงที่จำกัดตามคำจำกัดความนี้ด้วย ${\displaystyle 1}$${\displaystyle 1}$${\displaystyle k\times k}$${\displaystyle \Omega (k)}$

การคำนวณมิติทางหลวงของกราฟที่กำหนดนั้นเป็นปัญหาNP-hard [ ^{5 ] สมมติ}ว่าเส้นทางที่สั้นที่สุดทั้งหมดมีเอกลักษณ์ (ซึ่งสามารถทำได้โดยการรบกวนความยาวของขอบเล็กน้อย) สามารถคำนวณค่าประมาณได้ ในเวลาพหุนาม ^{[ 6 ]}โดยที่มิติทางหลวงของกราฟคือยังไม่เป็นที่ทราบแน่ชัดว่าการคำนวณมิติทางหลวงนั้นสามารถแก้ไขได้ด้วยพารามิเตอร์คงที่ (FPT) หรือไม่ อย่างไรก็ตาม มีผลลัพธ์ด้านความยากลำบากที่บ่งชี้ว่าไม่น่าจะเป็นเช่นนั้น^{[ 9 ]}โดยเฉพาะอย่างยิ่ง ผลลัพธ์เหล่านี้บ่งชี้ว่า ภายใต้สมมติฐานความซับซ้อนมาตรฐานอัลกอริทึม FPTไม่สามารถคำนวณมิติทางหลวงได้ทั้งจากล่างขึ้นบน (จากค่าที่เล็กที่สุดไปยังค่าที่ใหญ่ที่สุด) หรือจากบนลงล่าง (จากค่าที่ใหญ่ที่สุดไปยังค่าที่เล็กที่สุด) ${\displaystyle O(\log h)}$${\displaystyle h}$${\displaystyle r}$${\displaystyle r}$

ฮิวริสติกบางอย่างในการคำนวณเส้นทางที่สั้นที่สุด เช่น อัลกอริทึม Reach, Contraction Hierarchies , Transit NodesและHub Labellingสามารถพิสูจน์ได้อย่างเป็นทางการว่าทำงานได้เร็วกว่าอัลกอริทึมเส้นทางที่สั้นที่สุดอื่นๆ (เช่นอัลกอริทึมของ Dijkstra ) บนกราฟที่มีมิติทางหลวงที่จำกัดตามคำจำกัดความที่ 3 ข้างต้น^{[ 7 ]}

คุณสมบัติสำคัญที่สามารถใช้ประโยชน์ทางอัลกอริทึมสำหรับกราฟของมิติทางหลวงที่จำกัดคือจุดยอดที่อยู่ห่างจากศูนย์กลางของเส้นทางที่สั้นที่สุดจะรวมกลุ่มกันเป็นที่เรียกว่าเมือง: ^{[ 5 ]}

กำหนดรัศมี, เส้นทางที่สั้นที่สุด ที่ครอบคลุม พื้นที่ , และจุดยอดที่ อยู่ห่าง จาก จุดยอดนั้น เป็นระยะทางมากกว่า, เซต ของจุดยอดที่อยู่ห่าง จาก จุดยอดนั้น เป็นระยะทางไม่เกินตามความยาวของขอบเรียกว่าเมืองเซตของจุดยอดทั้งหมดที่ไม่ได้อยู่ในเมืองใด ๆ เรียกว่าพื้นที่ขยาย${\displaystyle r>0}$${\displaystyle r}$${\displaystyle H}$${\displaystyle G}$${\displaystyle u\in V}$${\displaystyle 2r}$${\displaystyle H}$${\displaystyle T\subseteq V}$${\displaystyle r}$${\displaystyle u}$${\displaystyle \ell }$

สามารถแสดงได้ว่าเส้นผ่านศูนย์กลางของทุกเมืองมีค่าไม่เกินในขณะที่ระยะห่างระหว่างเมืองกับจุดยอดใดๆ ที่อยู่นอกเมืองนั้นมีค่ามากกว่ายิ่งไปกว่านั้น ระยะห่างจากจุดยอดใดๆ ในพื้นที่แผ่ขยายไปยังจุดศูนย์กลางของ มีค่า ไม่เกิน${\displaystyle r}$${\displaystyle r}$${\displaystyle H}$${\displaystyle 2r}$

จากโครงสร้างนี้ Feldmann et al. ^{[ 5 ]}ได้กำหนดการแบ่งส่วนเมืองซึ่งแบ่งส่วนการขยายตัวออกเป็นเมืองที่มีค่าเพิ่มขึ้นแบบเลขชี้กำลังแบบวนซ้ำสำหรับกราฟที่มีมิติทางหลวงที่จำกัด (ตามคำนิยาม 1 ข้างต้น) การแบ่งส่วนนี้สามารถใช้เพื่อค้นหาการฝังเมตริกในกราฟที่มีความกว้างของต้นไม้ ที่จำกัด ซึ่งรักษาระยะห่างระหว่างจุดยอดได้ดีตามต้องการ เนื่องจากการฝังนี้ ทำให้สามารถได้รับแผนการประมาณค่าแบบกึ่งพหุนาม (QPTAS) สำหรับปัญหาต่างๆ เช่นTravelling Salesman (TSP), Steiner Tree , k-Median และ Facility Location ^{[ 5 ]}${\displaystyle r}$

สำหรับปัญหาการจัดกลุ่ม เช่น k-Median, k-Means และ Facility Location แผนการประมาณค่าแบบพหุนาม ที่รวดเร็วกว่า (PTAS) เป็นที่รู้จักสำหรับกราฟที่มีมิติทางหลวงที่จำกัดตามคำจำกัดความที่ 1 ข้างต้น^{[ 10 ]}สำหรับปัญหาการออกแบบเครือข่าย เช่น TSP และ Steiner Tree ยังไม่ทราบวิธีการได้มาซึ่ง PTAS

สำหรับ ปัญหา k-Centerยังไม่เป็นที่ทราบแน่ชัดว่ามี PTAS สำหรับกราฟที่มีมิติทางหลวงที่จำกัดหรือไม่ อย่างไรก็ตาม การคำนวณการประมาณค่า ( ) บนกราฟที่มีมิติทางหลวงนั้นเป็นปัญหา^{NP-hard [} 11 ] ซึ่งหมายความว่าอั^{ลกอริ}ทึมการประมาณค่า ( ) ใดๆ ก็ตามต้องการ เวลาอย่างน้อย สองเท่าของเลขชี้กำลัง ในมิติทางหลวง เว้นแต่ว่า P=NP ^{[ 11 ]}ในทางกลับกัน ได้มีการแสดงให้เห็นว่า มี อัลกอริทึมการ ประมาณค่าแบบ พารามิเตอร์ที่มีเวลาทำงานสำหรับk-Centerโดยที่คือมิติทางหลวงตามคำจำกัดความใดๆ ข้างต้น ^{[ 11 ]}เมื่อใช้คำจำกัดความที่ 1 ข้างต้นเป็นที่ทราบกันว่ามีแบบแผนการประมาณค่าแบบพารามิเตอร์ (PAS) เมื่อใช้ และเป็นพารามิเตอร์^{[ 12 ]}${\displaystyle 2-\varepsilon }$${\displaystyle O(\log ^{2}{n})}$${\displaystyle 2-\varepsilon }$${\displaystyle 3/2}$${\displaystyle 2^{O(kh\log {h})}n^{O(1)}}$${\displaystyle h}$${\displaystyle k}$${\displaystyle h}$

สำหรับปัญหา Capacitated k-Center นั้นไม่มีPASที่กำหนดพารามิเตอร์โดยและมิติของทางหลวงเว้นแต่FPT=W[1] [ ^{13 ] นี่}เป็นสิ่งที่น่าสังเกต เนื่องจากโดยทั่วไป (เช่น สำหรับปัญหาทั้งหมดที่กล่าวถึงข้างต้น) หากมีแผนการประมาณค่าสำหรับเมตริกที่มีมิติการคูณสองเท่า ต่ำ ก็จะมีแผนการประมาณค่าสำหรับกราฟที่มีมิติทางหลวงที่จำกัดด้วย แต่สำหรับ Capacitated k-Center นั้นมีPASที่กำหนดพารามิเตอร์โดยและมิติการคูณสองเท่า^{[ 13 ]}${\displaystyle k}$${\displaystyle h}$${\displaystyle k}$

ในเอกสารล่าสุด แสดงให้เห็นว่าเมืองและการขยายตัวยังสามารถพบได้ในกราฟที่มีมิติทางหลวงที่จำกัด เมื่อกำหนดโดยใช้เส้นทางที่สั้นที่สุดโดยประมาณ^{[ 8 ]}เอกสารนี้ยังแสดงให้เห็นว่าปัญหาพนักงานขายเดินทาง (TSP) ยอมรับPASที่กำหนดพารามิเตอร์โดยมิติทางหลวง ยิ่งไปกว่านั้น ยังสามารถสร้างการแบ่งส่วนที่มีการเติม การครอบคลุม/การแบ่งส่วนแบบเบาบาง และการครอบคลุมแบบต้นไม้ได้อีกด้วย มีแอปพลิเคชันมากมายตามมาโดยอิงจากผลลัพธ์ที่ทราบแล้ว

• วิดีโอเกี่ยวกับ " ศูนย์ k ที่มีความจุในมิติการคูณสองต่ำและทางหลวง " ^{[ 13 ]}จัดทำโดย Tung Ahn Vu, 2022
• วิดีโอเรื่อง " อัลกอริทึมสำหรับปัญหาที่ยากบนกราฟมิติทางหลวงต่ำ " บรรยายโดย Andreas Emil Feldmann ที่ ICERM มหาวิทยาลัยบราวน์ พรอวิเดนซ์ สหรัฐอเมริกา พฤษภาคม 2019
• วิดีโอเกี่ยวกับ " การฝัง (1 + ε) ของกราฟมิติทางหลวงต่ำลงในกราฟความกว้างต้นไม้ที่จำกัด " ^{[ 5 ]}นำเสนอโดย Andreas Emil Feldmann ที่ Hausdorff Institut, Bonn, DE, 2015
• วิดีโอเรื่อง " มิติทางหลวง: จากการปฏิบัติสู่ทฤษฎีและย้อนกลับ " ^{[ 6 ]}นำเสนอโดย Andrew Goldberg