Home > Timetable > Contribution details

Contribution

Orientable quadrilateral embeddings of cartesian products

Speakers

  • Dr. Mark ELLINGHAM

Primary authors

Content

White, Pisanski and others have proved a number of results on the existence of quadrilateral embeddings of cartesian products of graphs; in some cases these provide minimum genus embeddings. In a 1992 paper Pisanski posed three questions. First, if $G$ and $H$ are connected $1$-factorable $r$-regular graphs with $r \ge 2$, does the cartesian product $G \times H$ have an orientable quadrilateral embedding? Second, if $G$ is $r$-regular, does the cartesian product of $G$ with sufficiently many even cycles have an orientable quadrilateral embedding? Third, if $G$ is an arbitrary connected graph, does the cartesian product of $G$ with a sufficient large cube $Q_n = \times^n K_2$ have an orientable quadrilateral embedding? We answer all three questions. The answers to the second and third questions are positive, as we show using a general theorem that answers both. We have also shown that the answer to the first question is negative, via some families of $3$-regular examples. This is joint work with Wenzhong Liu, Dong Ye and Xiaoya Zha.