تاريخ الرياضيات
الاعداد و نظريتها
تاريخ التحليل
تار يخ الجبر
الهندسة و التبلوجي
الرياضيات في الحضارات المختلفة
العربية
اليونانية
البابلية
الصينية
المايا
المصرية
الهندية
الرياضيات المتقطعة
المنطق
اسس الرياضيات
فلسفة الرياضيات
مواضيع عامة في المنطق
الجبر
الجبر الخطي
الجبر المجرد
الجبر البولياني
مواضيع عامة في الجبر
الضبابية
نظرية المجموعات
نظرية الزمر
نظرية الحلقات والحقول
نظرية الاعداد
نظرية الفئات
حساب المتجهات
المتتاليات-المتسلسلات
المصفوفات و نظريتها
المثلثات
الهندسة
الهندسة المستوية
الهندسة غير المستوية
مواضيع عامة في الهندسة
التفاضل و التكامل
المعادلات التفاضلية و التكاملية
معادلات تفاضلية
معادلات تكاملية
مواضيع عامة في المعادلات
التحليل
التحليل العددي
التحليل العقدي
التحليل الدالي
مواضيع عامة في التحليل
التحليل الحقيقي
التبلوجيا
نظرية الالعاب
الاحتمالات و الاحصاء
نظرية التحكم
بحوث العمليات
نظرية الكم
الشفرات
الرياضيات التطبيقية
نظريات ومبرهنات
علماء الرياضيات
500AD
500-1499
1000to1499
1500to1599
1600to1649
1650to1699
1700to1749
1750to1779
1780to1799
1800to1819
1820to1829
1830to1839
1840to1849
1850to1859
1860to1864
1865to1869
1870to1874
1875to1879
1880to1884
1885to1889
1890to1894
1895to1899
1900to1904
1905to1909
1910to1914
1915to1919
1920to1924
1925to1929
1930to1939
1940to the present
علماء الرياضيات
الرياضيات في العلوم الاخرى
بحوث و اطاريح جامعية
هل تعلم
طرائق التدريس
الرياضيات العامة
نظرية البيان
Planar Graph
المؤلف:
Auslander, L. and Parter, S.
المصدر:
"On Imbedding Graphs in the Sphere." J. Math. Mechanics 10
الجزء والصفحة:
...
6-4-2022
3218
Planar Graph
A graph is planar if it can be drawn in a plane without graph edges crossing (i.e., it has graph crossing number 0). The number of planar graphs with , 2, ... nodes are 1, 2, 4, 11, 33, 142, 822, 6966, 79853, ... (OEIS A005470; Wilson 1975, p. 162), the first few of which are illustrated above.
The corresponding numbers of planar connected graphs are 1, 1, 1, 2, 6, 20, 99, 646, 5974, 71885, ... (OEIS A003094; Steinbach 1990, p. 131)
There appears to be no term in standard use for a graph with graph crossing number 1. In particular, the terms "almost planar" and "1-planar" are used in the literature for other concepts. Therfore, in this work, the term singlecross graph is introduced for such a graph. A graph with crossing (or rectilinear crossing) number 0 is planar by definition, a graph with crossing (or rectilinear crossing) number 1 is said to be singlecross, and a graph with crossing (or rectilinear crossing) number 2 is said to be doublecross.
Note that while graph planarity is an inherent property of a graph, it is still sometimes possible to draw nonplanar embeddings of planar graphs. For example, the two embeddings above both correspond to the planar tetrahedral graph, but while the left embedding is planar, the right embedding is not.
A planar embedding of a planar graph is sometimes called a planar embedding or plane graph (Harborth and Möller 1994). A planar straight line embedding of a graph can be made in the Wolfram Language using PlanarGraph[g].
There are a number of efficient algorithms for planarity testing, most of which are based on the algorithm of Auslander and Parter (1961; Skiena 1990, p. 247). A graph may be tested for planarity in the Wolfram Language using the command PlanarGraphQ[g].
A graph is planar iff it has a combinatorial dual graph (Harary 1994, p. 115). Any planar graph has a graph embedding as a planar straight line embedding where edges do not intersect (Fáry 1948; Bryant 1989; Skiena 1990, pp. 100 and 251; Scheinerman and Wilf 1994).
Only planar graphs have duals. If a finite simple graph is planar, then
has at least one vertex degree
. If both graph
and its graph complement
are planar, then
has eight or fewer vertices.
Complete graphs are planar only for . The complete bipartite graph
is nonplanar. More generally, Kuratowski proved in 1930 that a graph is planar iff it does not contain within it any graph that is a graph expansion of the complete graph
or
.
There are a number of measures characterizing the degree by which a graph fails to be planar, among these being the graph crossing number, rectilinear crossing number, graph skewness, graph coarseness, and graph thickness.
A graph with thickness 1 is planar, while a graph with graph thickness 1 or 2 is said to be biplanar. A nonplanar apex graph is a nonplanar graph possessing at least one vertex whose removal results in a planar graph.
All trees are planar, as is a cycle graph, grid graph, or wheel graph. Every planar graph on nine vertices has a nonplanar complement (Battle et al. 1962; Skiena 1990, p. 250).
The following table gives the numbers of planar graphs having minimal degrees of at least .
OEIS | ||
2 | A049370 | 0, 0, 1, 3, 10, 50, 335, ... |
3 | A049371 | 0, 0, 0, 1, 2, 9, 46, 386, ... |
4 | A049372 | 0, 0, 0, 0, 0, 1, 1, 4, 14, 69, ... |
5 | A049373 | 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 1, 5, ... |
REFERENCES
Auslander, L. and Parter, S. "On Imbedding Graphs in the Sphere." J. Math. Mechanics 10, 517-523, 1961.
Battle, J.; Harary, F.; and Kodama, Y. "Every Planar Graph with Nine Points has a Nonplanar Complement." Bull. Amer. Math. Soc. 68, 569-571, 1962.
Booth, K. S. and Lueker, G. S. "Testing for the Consecutive Ones Property, Interval Graphs, and Graph Planarity using PQ-Tree Algorithms." J. Comput. System Sci. 13, 335-379, 1976.
Bryant, V. W. "Straight Line Representation of Planar Graphs." Elem. Math. 44, 64-66, 1989.
Cai, J.; Han, X.; and Tarjan, R. "New Solutions to Four Planar Graph Problems." Technical Report. New York University, 1990.
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.
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.
Eppstein, D. "Layered Graph Drawing." http://www.ics.uci.edu/~eppstein/junkyard/thickness/.Even, S. Graph Algorithms. Rockville, MD: Computer Science Press, 1979.
Fáry, I. "On Straight Line Representations of Planar Graphs." Acta Sci. Math. (Szeged( 11, 229-233, 1948.
Gardner, M. The Sixth Book of Mathematical Games from Scientific American. Chicago, IL: University of Chicago Press, pp. 91-94, 1984.
Harary, F. "Planarity." Ch. 11 in Graph Theory. Reading, MA: Addison-Wesley, pp. 102-125, 1994.
Harborth, H. and Möller, M. "Minimum Integral Drawings of the Platonic Graphs." Math. Mag. 67, 355-358, 1994.
Hopcroft, J. and Tarjan, R. "Efficiency Planarity Testing." J. ACM 21, 549-568, 1974.
Kocay, W. and Pantel, C. "An Algorithm for Finding a Planar Layout of a Graph with a Regular Polygon as Outer Face." Util. Math. 48, 161-178, 1995.
Le Lionnais, F. Les nombres remarquables. Paris: Hermann, p. 56, 1983.
Nishizeki, T. and Rahman, M. S. Planar Graph Drawing. Singapore: World Scientific, 2004.
Read, R. C. "A New Method for Drawing a Planar Graph Given the Cyclic Order of the Edges at Each Vertex." Congr. Numer. 56, 31-44, 1987.
Scheinerman, E. and Wilf, H. S. "The Rectilinear Crossing Number of a Complete Graph and Sylvester's 'Four Point' Problem of Geometric Probability." Amer. Math. Monthly 101, 939-943, 1994.
Skiena, S. "Planar Graphs." §6.5 in Implementing Discrete Mathematics: Combinatorics and Graph Theory with Mathematica. Reading, MA: Addison-Wesley, pp. 247-253, 1990.
Sloane, N. J. A. Sequences A003094/M1652, A005470/M1252, A049370, A049371, A049372, and A049373 in "The On-Line Encyclopedia of Integer Sequences."Steinbach, P. Field Guide to Simple Graphs. Albuquerque, NM: Design Lab, 1990.
Stony Brook Algorithm Repository. §1.4.12. "Planarity Detection and Embedding." http://www.cs.sunysb.edu/~algorith/files/planar-drawing.shtml.Wagon, S. "Coloring Planar Maps and Graphs." Ch. 24 in Mathematica in Action, 2nd ed. New York: Springer-Verlag, pp. 507-537, 1999.
West, D. B. Introduction to Graph Theory, 2nd ed. Englewood Cliffs, NJ: Prentice-Hall, p. 243, 2000.
Whitney, H. "Non-Separable and Planar Graphs." Trans. Amer. Math. Soc. 34, 339-362, 1932.
Whitney, H. "Planar Graphs." Fund. Math. 21, 73-84, 1933.Wilson, R. J. Introduction to Graph Theory. London: Longman, 1975.
الاكثر قراءة في نظرية البيان
اخر الاخبار
اخبار العتبة العباسية المقدسة

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