اشترك بالحزمة الذهبية واحصل على وصول غير محدود شمرا أكاديميا
تسجيل مستخدم جديدDrawings of complete graphs in the projective plane
206
0
0.0
(
0
)
اسأل ChatGPT حول البحث
ﻻ يوجد ملخص باللغة العربية
Hills Conjecture states that the crossing number $text{cr}(K_n)$ of the complete graph $K_n$ in the plane (equivalently, the sphere) is $frac{1}{4}lfloorfrac{n}{2}rfloorlfloorfrac{n-1}{2}rfloorlfloorfrac{n-2}{2}rfloorlfloorfrac{n-3}{2}rfloor=n^4/64 + O(n^3)$. Moon proved that the expected number of crossings in a spherical drawing in which the points are randomly distributed and joined by geodesics is precisely $n^4/64+O(n^3)$, thus matching asymptotically the conjectured value of $text{cr}(K_n)$. Let $text{cr}_P(G)$ denote the crossing number of a graph $G$ in the projective plane. Recently, Elkies proved that the expected number of crossings in a naturally defined random projective plane drawing of $K_n$ is $(n^4/8pi^2)+O(n^3)$. In analogy with the relation of Moons result to Hills conjecture, Elkies asked if $lim_{ntoinfty} text{cr}_P(K_n)/n^4=1/8pi^2$. We construct drawings of $K_n$ in the projective plane that disprove this.
قيم البحث
اقرأ أيضاً
Motivated by the successful application of geometry to proving the Harary-Hill Conjecture for pseudolinear drawings of $K_n$, we introduce pseudospherical drawings of graphs. A spherical drawing of a graph $G$ is a drawing in the unit sphere $mathbb{
S}^2$ in which the vertices of $G$ are represented as points -- no three on a great circle -- and the edges of $G$ are shortest-arcs in $mathbb{S}^2$ connecting pairs of vertices. Such a drawing has three properties: (1) every edge $e$ is contained in a simple closed curve $gamma_e$ such that the only vertices in $gamma_e$ are the ends of $e$; (2) if $e e f$, then $gamma_ecapgamma_f$ has precisely two crossings; and (3) if $e e f$, then $e$ intersects $gamma_f$ at most once, either in a crossing or an end of $e$. We use Properties (1)--(3) to define a pseudospherical drawing of $G$. Our main result is that, for the complete graph, Properties (1)--(3) are equivalent to the same three properties but with precisely two crossings in (2) replaced by at most two crossings. The proof requires a result in the geometric transversal theory of arrangements of pseudocircles. This is proved using the surprising result that the absence of special arcs ( coherent spirals) in an arrangement of simple closed curves characterizes the fact that any two curves in the arrangement have at most two crossings. Our studies provide the necessary ideas for exhibiting a drawing of $K_{10}$ that has no extension to an arrangement of pseudocircles and a drawing of $K_9$ that does extend to an arrangement of pseudocircles, but no such extension has all pairs of pseudocircles crossing twice.
A P-graph is a simple graph G which is embeddable in the real projective plane P. A (3,6)-tight P-graph is shown to be constructible from one of 8 uncontractible P-graphs by a sequence of vertex splitting moves. Also it is shown that a P-graph is min
imally generically 3-rigid if and only if it is (3,6)-tight. In particular this characterisation holds for graphs that are embeddable in the M{o}bius strip.
Partial edge drawing (PED) is a drawing style for non-planar graphs, in which edges are drawn only partially as pairs of opposing stubs on the respective end-vertices. In a PED, by erasing the central parts of edges, all edge crossings and the result
ing visual clutter are hidden in the undrawn parts of the edges. In symmetric partial edge drawings (SPEDs), the two stubs of each edge are required to have the same length. It is known that maximizing the ink (or the total stub length) when transforming a straight-line graph drawing with crossings into a SPED is tractable for 2-plane input drawings, but NP-hard for unrestricted inputs. We show that the problem remains NP-hard even for 3-plane input drawings and establish NP-hardness of ink maximization for PEDs of 4-plane graphs. Yet, for k-plane input drawings whose edge intersection graph forms a collection of trees or, more generally, whose intersection graph has bounded treewidth, we present efficient algorithms for computing maximum-ink PEDs and SPEDs. We implemented the treewidth-based algorithms and show a brief experimental evaluation.
In this paper, we study the achromatic and the pseudoachromatic numbers of planar and outerplanar graphs as well as planar graphs of girth 4 and graphs embedded on a surface. We give asymptotically tight results and lower bounds for maximal embedded graphs.
Total dominator total coloring of a graph is a total coloring of the graph such that each object of the graph is adjacent or incident to every object of some color class. The minimum namber of the color classes of a total dominator total coloring of
a graph is called the total dominator total chromatic number of the graph. Here, we will find the total dominator chromatic numbers of wheels, complete bipartite graphs and complete graphs.
سجل دخول لتتمكن من نشر تعليقات
التعليقات
جاري جلب التعليقات
سجل دخول لتتمكن من متابعة معايير البحث التي قمت باختيارها
