ترغب بنشر مسار تعليمي؟ اضغط هنا

Homotopy height, grid-major height and graph-drawing height

57   0   0.0 ( 0 )
 نشر من قبل David Eppstein
 تاريخ النشر 2019
  مجال البحث الهندسة المعلوماتية
والبحث باللغة English




اسأل ChatGPT حول البحث

It is well-known that both the pathwidth and the outer-planarity of a graph can be used to obtain lower bounds on the height of a planar straight-line drawing of a graph. But both bounds fall short for some graphs. In this paper, we consider two other parameters, the (simple) homotopy height and the (simple) grid-major height. We discuss the relationship between them and to the other parameters, and argue that they give lower bounds on the straight-line drawing height that are never worse than the ones obtained from pathwidth and outer-planarity.



قيم البحث

اقرأ أيضاً

We present the first in-depth statistical survey of flare source heights observed by RHESSI. Flares were found using a flare-finding algorithm designed to search the 6-10 keV count-rate when RHESSIs full sensitivity was available in order to find the smallest events (Christe et al., 2008). Between March 2002 and March 2007, a total of 25,006 events were found. Source locations were determined in the 4-10 keV, 10-15 keV, and 15-30 keV energy ranges for each event. In order to extract the height distribution from the observed projected source positions, a forward-fit model was developed with an assumed source height distribution where height is measured from the photosphere. We find that the best flare height distribution is given by g(h) propto exp(-h/{lambda}) where {lambda} = 6.1pm0.3 Mm is the scale height. A power-law height distribution with a negative power-law index, {gamma} = 3.1 pm 0.1 is also consistent with the data. Interpreted as thermal loop top sources, these heights are compared to loops generated by a potential field model (PFSS). The measured flare heights distribution are found to be much steeper than the potential field loop height distribution which may be a signature of the flare energization process.
In algebraic geometry there is the notion of a height pairing of algebraic cycles, which lies at the confluence of arithmetic, Hodge theory and topology. After explaining a motivating example situation, we introduce new directions in this subject.
217 - Kaori Nagashima 2014
We study Doppler velocity measurements at multiple heights in the solar atmosphere using a set of six filtergrams obtained by the Helioseismic magnetic Imager on board the Solar Dynamics Observatory. There are clear and significant phase differences between core and wing Dopplergrams in the frequency range above the photospheric acoustic cutoff frequency, which indicates that these are really multi-height datasets.
Glivenkos theorem states that a formula is derivable in classical propositional logic $mathrm{CL}$ iff under the double negation it is derivable in intuitionistic propositional logic $mathrm{IL}$: $mathrm{CL}vdashvarphi$ iff $mathrm{IL}vdash eg egvar phi$. Its analog for the modal logics $mathrm{S5}$ and $mathrm{S4}$ states that $mathrm{S5}vdash varphi$ iff $mathrm{S4} vdash eg Box eg Box varphi$. In Kripke semantics, $mathrm{IL}$ is the logic of partial orders, and $mathrm{CL}$ is the logic of partial orders of height 1. Likewise, $mathrm{S4}$ is the logic of preorders, and $mathrm{S5}$ is the logic of equivalence relations, which are preorders of height 1. In this paper we generalize Glivenkos translation for logics of arbitrary finite height.
We prove non-asymptotic stretched exponential tail bounds on the height of a randomly sampled node in a random combinatorial tree, which we use to prove bounds on the heights and widths of random trees from a variety of models. Our results allow us t o prove a conjecture and settle an open problem of Janson (https://doi.org/10.1214/11-PS188), and nearly prove another conjecture and settle another open problem from the same work (up to a polylogarithmic factor). The key tool for our work is an equivalence in law between the degrees along the path to a random node in a random tree with given degree statistics, and a random truncation of a size-biased ordering of the degrees of such a tree. We also exploit a Poissonization trick introduced by Camarri and Pitman (https://doi.org/10.1214/EJP.v5-58) in the context of inhomogeneous continuum random trees, which we adapt to the setting of random trees with fixed degrees. Finally, we propose and justify a change to the conventions of branching process nomenclature: the name Galton-Watson trees should be permanently retired by the community, and replaced with the name Bienayme trees.
التعليقات
جاري جلب التعليقات جاري جلب التعليقات
سجل دخول لتتمكن من متابعة معايير البحث التي قمت باختيارها
mircosoft-partner

هل ترغب بارسال اشعارات عن اخر التحديثات في شمرا-اكاديميا