Integral Embedding

An integral embedding of a graph, not to be confused with an integral graph, is a graph drawn such that vertices are distinct points and all graph edges have integer lengths. Every graph possesses an integral embedding (Müller 1953, Harborth and Möller 1994).

It is conjectured that every planar graph has a plane integral embedding.

A unit-distance graph is a graph that not only possesses an integral embedding, but an embedding in which all edges have the same length (which can be taken as 1 without loss of generality). Unit-distance embeddings are therefore minimal integral embeddings since they have the smallest possible (1) largest edge length.

The following table summarizes the minimum diameters for integral and plane integral embeddings of the Platonic graphs (Müller 1953, Harborth et al. 1987, Harborth and Möller 1994), where  refers to the "diameter" given by the largest integer in the set of lengths of an integral embedding (not the graph diameter).

graph		plane
cubical graph	1	2
dodecahedral graph	1	2
icosahedral graph	8	159
octahedral graph	7	13
tetrahedral graph	4	17

The minimal integral embeddings of the Platonic graphs are illustrated above (Harborth and Möller 1994).

The minimal planar integral embeddings of the Platonic graphs are illustrated above (Harborth et al. 1987).

---

REFERENCES

Harborth, H.; Kemnitz, A.; Möller, M.; and Süssenbach, A. "Ganzzahlige planare Darstellungen der platonischen Körper." Elem. Math. 42, 118-122, 1987.

Harborth, H. and Möller, M. "Minimum Integral Drawings of the Platonic Graphs." Math. Mag. 67, 355-358, 1994.

Hartsfield, N. and Ringel, G. Pearls in Graph Theory: A Comprehensive Introduction. San Diego, CA: Academic Press, p. 173, 1990.

Müller, A. "Auf einem Kreis liegende Punktmengen ganzzahliger Entfernungen." Elem. Math. 8, 37-38, 1953.

اخر الاخبار

اخبار العتبة العباسية المقدسة

متحف الكفيل يباشر صيانة منسوجات تراثية تابعة للعتبة العسكرية المقدسة

العتبة العباسية المقدسة تستذكر مظلومية الإمام الكاظم (عليه السلام) عبر مجلس عزاء

قسم العلاقات العامة يناقش مع منتدى شباب الإسكان إقامة مهرجان تكريم طالبات المدارس المرتديات العباءة في القادسية

سماحة السيد الصافي يدعو إلى توحيد الجهود في تحقيق التراث لضمان الرصانة والدقة وخدمة الساحة العلمية

المزيد

الآخبار الصحية

6 فواكة تساعدك على الشعور بتحسّن عند المرض

حفاظا على صحة العين.. هذا أفضل وقت لتناول فيتامين أ

الاستخدام اليومي لسماعات الأذن.. أخطر مما تتصور !

هل توقيت نشاطك اليومي يؤثر على صحة دماغك؟.. العلماء يجيبون

المزيد

الآخبار التكنلوجية

ابتكار ألماني قد يغيّر مستقبل صناعة البلاستيك

تحديثات وأرباح عبر المشاهدات.. ما الذي تخطط له "لينكد إن"؟

"الكوكايين الوردي".. مخدر جديد يثير قلق السلطات الأميركية

دراسة: تغيّرات في أسلوب القيادة قد تكشف مبكرا عن الخرف !

المزيد

مواضيع ذات صلة

Minimum Spanning Tree

Maximum Leaf Number

Lobster Graph

Labeled Tree

Internal Path Length

Red-Black Tree

Pseudotree

Pseudoforest

Prüfer Code

Planted Tree

Planted Planar Tree

Graph Strength