Eulerian straight ahead cycles in drawings of complete bipartite graphs (Q5931408)

In a drawing \(D(G)\) of a graph \(G=(V,E)\) the vertices of \(G\) are mapped injectively into points of the (Euclidean) plane (called the vertices of \(D(G)\)), and edges are mapped injectively into simple curves (called the edges of \(D(G)\)) such that incidences are preserved, and two edges of \(D(G)\) have at most one point of the plane in common (i.e., either they are adjacent to the same point of \(D(G)\) or they cross each other). Note that the graphs considered need not be planar graphs. A cycle/trail \(K\) in a drawing \(D(G)\) is called `straight ahead' if two edges \(e,f\) of \(K\) which are adjacent to a vertex of even degree, have on both sides of the curve defined by \(e\) and \(f\), the same number of edges. Eulerian graphs can be characterized in two ways: namely, by Eulerian trails, and by cycle decompositions. In general, the number of Eulerian trails/cycle decompositions is exponentially large, so one might pose the following questions: Given an Eulerian graph \(G\) , does there exist a drawing \(D(G)\) such that some Eulerian trail of \(G\) appears as an Eulerian straight ahead trail of \(D(G)\)? Given an Eulerian graph \(G\), does there exist a drawing \(D(G)\) such that some cycle decomposition of \(G\) appears as a decomposition of \(D(G)\) into straight ahead cycles of smallest length? NEWLINENEWLINENEWLINENote that these problems can be answered trivially if one allows edges of \(D(G)\) to have more than one point of the plane in common. Also, every drawing \(D(G)\) of an Eulerian graph \(G\) admits a decomposition into closed straight ahead trails. In an earlier paper, the author has shown that complete graphs of odd order have a drawing with an Eulerian straight ahead trail. In contrast, for Steiner triple systems, interpreted as cycle decompositions of complete graphs into triangles, only for the complete graph of order 7 a drawing is known in which the triangles appear as straight ahead cycles. In the paper under review, the author gives an affirmative answer to the above questions for complete bipartite graphs \(G(X,Y)\) for even \(|X|> 1\), \(|Y|> 1\). Theorem 1: If the two vertex sets of the complete bipartite graph \(G(X,Y)\) are drawn on parallel lines in the plane, and if the edges are drawn as straight line segments, then such drawing admits a decomposition into straight ahead 4-cycles. Theorem 2: For the complete bipartite graphs \(G(X,Y)\) a drawing exists such that it has an Eulerian straight ahead trail.