Knjiga je nastala na osnovi knjige Product Graphs, ki je leta 2000 izšla pri Wiley-Interscience. Slednja je postala klasično delo o produktih grafov in predstavlja enega njbolj citiranih del slovenske matematike. V bazi MathSciNet ima že preko 250 citatov. Nova knjiga je bistveno obsežnejša (518 str. proti 358 str.) in je napisana povsem na novo ter ima povsem novo strukturo. Knjiga Priročnik o produktih grafov obravnava dihotomijo med strukturo produktov grafov in njihovimi podgrafi. Poudarja tudi načrtovanje učinkovitih algoritmov, ki prepoznavajo produkte in njihove podgrafe ter raziskuje povezave med grafovskimi parametri produktov in njihovih faktorjev. Občudno razširjena in popravljena knjiga prinaša popolne dokaze mnogih pomembnih rezultatov in tudi najnovejše rezultate in domneve. Rezultati in algoritmi, ki so novi v tej knjigi obsegajo (1) Izreke o krajšanju, (2) kvadratični prepoznavni algoritem za delne kocke, (3) rezultate o krepki izometrični dimenziji, (4) izračun Wienerjevega indeksa preko kanonične izometrične vložitve, (5) rezultate o povezanosti, (6) deljeno inačico Hedetniemijeve domneve, (7) rezultate o neodvisnostnem številu kartezičnih potenc po vozliščih tranzitivnih grafov, (8) dokaz Vizingove domneve za tetivne grafe, (9) rezultate o minimalnih bazah ciklov in (10) številen izbrane rezultate, kot na primer rezultate o polnih minorjih in nikjer ničelnih pretokih.
COBISS.SI-ID: 15916121
Neravninski graf G je skoraj ravninski (ang. nearplanar), če obstaja taka povezava, katere odstranitev naredi graf ravninski. V članku študiramo prekrižna števila skoraj ravninskih grafov. Po eni strani razvijemo minmax formule, ki določijo izračunljive spodnje in zgornje meje. Ti minmax 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 NPtežak, kadar so povezave utežene.
COBISS.SI-ID: 15261785
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