Neravninski graf G je skoraj ravninski (ang. near-planar), če obstaja taka povezava, katere odstranitev naredi graf ravninski. V članku študiramo prekrižna števila skoraj ravninskih grafov. Po eni strani razvijemo min-max formule, ki določijo izračunljive spodnje in zgornje meje. Ti min-max rezultati so prvi svoje vrste v študiji prekrižnega števila in izboljšajo aproksimacijski faktor algoritma, ki sta ga opisala Hliněný in Salazar (Graph Drawing GD'06). Po drugi strani pokažemo, da je problem računanja prekrižnega števila skoraj ravninskih grafov NP-težak, kadar so povezave utežene.
COBISS.SI-ID: 15261785
Dokazano je, da je število označenih grafov z n vozlišči, ki se jih da vložiti v orientabilno ploskev roda g asimptotično približno enako vrednosti $c^{(g)}n^{5(g-1)/2-1}\gamma^n n!$, kjer je $c^{(g)})0$ konstanta, $\gamma \approx 27.23$ pa je eksponentna mera rasti za ravninske grafe. Rezultat je posplošitev znanega rezultata zaravninske grafe (g=0). Podoben rezultat je dokazan za norientabline ploskve. Dokazano je tudi, da so limitne lastnosti takih grafov asimptotično enake tistim, ki veljajo za ravninske grafe.
COBISS.SI-ID: 15875673
Presečno število roda n za dani graf G označimo kot $cr_n(G)$ in je definirano kot najmanjše možno število križanj povezav pri reprezentaciji grafa G na ploskvi roda n. Dokazano je, da za pjubne $a)b)0$ obstaja graf G, za katerega je $cr_0(G) = a$, $cr_1(G) = b$ in $cr_2(G) = 0$. Ta dokaj nenavadni rezultat podpira zanivo hipotezo Archdeacona o presečnih zaporedjih in reši odprti problem, ki ga je postavil Salazar.
COBISS.SI-ID: 16051801