The book was written based on the book Product Graphs published in 2000 by Wiley-Interscience. The latter book bacame a classic on product graphs and is one of the most cited works of Slovene mathematics. In MathSciNet it has more than 250 citations. The new book is much expanded (518 pp. versus 358 pp.) and was written newly written with a completely different structure. The book Handbook of product graphs examines the dichotomy between the structure of products and their subgraphs. It also features the design of efficient algorithms that recognize products and their subgraphs and explores the relationship between graph parameters of the product and factors. Extensively revised and expanded, the handbook presents full proofs of many important results as well as up-to-date research and conjectures. Results and algorithms new to the second edition: (1) Cancellation results, (2) A quadratic recognition algorithm for partial cubes, (3) Results on the strong isometric dimension, (4) Computing the Wiener index via canonical isometric embedding, (5) Connectivity results, (6) A fractional version of Hedetniemi's conjecture, (7) Results on the independence number of Cartesian powers of vertex-transitive graphs, (8) Verification of Vizing's conjecture for chordal graphs, (9) Results on minimum cycle bases and (10) Numerous selected recent results, such as complete minors and nowhere-zero flows.
COBISS.SI-ID: 15916121
A nonplanar graph ▫$G$▫ is near-planar if it contains an edge ▫$e$▫ such that ▫$G-e$▫ is planar. The problem of determining the crossing number of a near-planar graph is exhibited from different combinatorial viewpoints. On the one hand, we develop min-max formulas involving efficiently computable lower and upper bounds. These min-max results are the first of their kind in the study of crossing numbers and improve the approximation factor for the approximation algorithm given by Hliněný and Salazar (Graph Drawing GD'06). On the other hand, we show that it is NP-hard to compute a weighted version of the crossing number for near-planar graphs.
COBISS.SI-ID: 15261785
The ▫$n$▫-th crossing number of a graph ▫$G$▫, denoted ▫$cr_n(G$)▫, is the minimum number of crossings in a drawing of ▫$G$▫ on an orientable surface of genus ▫$n$▫. We prove that for every ▫$a)b)0$▫, there exists a graph ▫$G$▫ for which ▫$cr_0(G) = a$▫, ▫$cr_1(G) = b$▫, and ▫$cr_2(G) = 0$▫. This provides support for a conjecture of Archdeacon et al. and resolves a problem of Salazar.
COBISS.SI-ID: 16051801