Graph Embedding

 

A graph embedding, sometimes also called a graph drawing, is a particular drawing of a graph. Graph embeddings are most commonly drawn in the plane, but may also be constructed in three or more dimensions. The above figure shows several embeddings of the cubical graph. The most commonly encountered graph embeddings are generally straight line embeddings, in which all edges are drawn as straight line segments.

A good choice of embedding can lead to particularly illuminating diagrams. For example, the circular (left) embedding of the cubical graph illustrates this graph's inherent symmetries.

Skiena (1990) considers a number of different types of embeddings, including circular, ranked, radial, rooted, and spring. Graph embeddings can be visualized in the Wolfram Language in two dimensions using the option GraphLayout. Alternately, GraphPlot[g] can be used in two dimensions and GraphPlot3D[g] in three dimensions. Embeddings for trees can be visualized using TreePlot[g].

Precomputed embeddings of certain types for a number of graphs are available in the Wolfram Language as GraphData[g, "Graph", type].

---

REFERENCES

Chung, F.; Leighton, T.; and Rosenberg, A. "Embeddings Graphs in Books: A Layout Problem with Applications to VLSI Design." SIAM J. Algebraic Disc. Meth. 8, 33-58, 1987.

Di Battista, G.; Eades, P.; Tamassia, R.; and Tollis, I. G. Graph Drawing: Algorithms for the Visualization of Graphs. Englewood Cliffs, NJ: Prentice-Hall, 1998.Di Battista, G.; Garg, A.; Liotta, G.; Tamassia, R.; Tassinari, E.; and Vargiu, F. "An Experimental Comparison of Four Graph Drawing Algorithms." Computational Geom. 7, 303-325, 1997.

Eades, P. "A Heuristic for Graph Drawing." Congr. Numer. 42, 149-160, 1984.

Eades, P.; Fogg, I.; and Kelly, D. SPREMB: A System for Developing Graph Algorithms. Technical Report. Department of Computer Science. St. Lucia, Queensland, Australia: University of Queensland, 1988.

Eades, P. and Tamassia, R. "Algorithms for Drawing Graphs: An Annotated Bibliography." Technical Report CS-89-09. Department of Computer Science. Providence, RI: Brown University, Feb. 1989.

Kamada, T. and Kawai, S. "An Algorithm for Drawing General Undirected Graphs." Inform. Processing Lett. 31, 7-15, 1989.

Malitz, S. M. "Genus g Graphs Have Pagenumber ." In Proc. 29th Sympos. Found. Computer Sci. IEEE Press, pp. 458-468, 1988.

Pemmaraju, S. and Skiena, S. Computational Discrete Mathematics: Combinatorics and Graph Theory with Mathematica. Cambridge, England: Cambridge University Press, 2003.Reingold, E. and Tilford, J. "Tidier Drawings of Trees." IEEE Trans. Software Engin. 7, 223-228, 1981.

Skiena, S. "Graph Embeddings." §3.3 in Implementing Discrete Mathematics: Combinatorics and Graph Theory with Mathematica. Reading, MA: Addison-Wesley, pp. 81 and 98-118, 1990.

Supowit, K. and Reingold, E. "The Complexity of Drawing Trees Nicely." Acta. Inform. 18, 377-392, 1983.

Tamassia, R. "Graph Drawing." Ch. 21 in Handbook of Computational Geometry (Ed. J.-R. Sack and J. Urrutia). Amsterdam, Netherlands: North-Holland, pp. 937-971, 2000.

Vaucher, J. "Pretty Printing of Trees." Software Pract. Experience 10, 553-561, 1980.

Wetherell, C. and Shannon, A. "Tidy Drawings of Trees." IEEE Trans. Software Engin. 5, 514-520, 1979.

White, A. T. "Imbedding Problems in Graph Theory." Ch. 6 in Graphs of Groups on Surfaces: Interactions and Models (Ed. A. T. White). Amsterdam, Netherlands: Elsevier, pp. 49-72, 2001.

اخر الاخبار

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

الحلقة 26 من جائزة العميد القرآنية تشهد مشاركة 5 قراء من الفتية ضمن المرحلة النهائية

بهدف تعزيز مفاهيم الخدمة.. مركز الامتثال الوظيفي يواصل لقاءاته مع المنتسبين

العتبة العباسية المقدسة تستضيف عددًا من عوائل الشهداء للوقوف على احتياجاتهم

بحضور 270 مشاركة.. شعبة فاطمة بنت أسد تختتم محفلها الرمضاني المركزي

المزيد

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

دراسة: تناول القهوة يوميا يخفض خطر الإصابة بالاضطرابات النفسية

عرض شائع في الفم قد يكون مرتبطا بخطر الإصابة بأمراض خطيرة

نصائح عامة لاستخدام سماعات الرأس بأمان

تأثير اللياقة البدنية على الدماغ

المزيد

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

ديدان الأرض تكشف تلوث التربة بالمعادن الثقيلة

خبير أرصاد جوية: ظاهرة النينيو القادمة قد تكون الأقوى خلال 10 سنوات

"ناسا" تكشف موعد إعادة إطلاق رحلتها المأهولة إلى القمر

علماء الجيولوجيا يفكون لغز الصدع العملاق تحت الماء في المحيط الأطلسي

المزيد

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

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