Two Problems About Drawing Graphs in the Plane

We offer the following two unrelated problems about drawing graphs in the plane. In a drawing two nonadjacent edges are allowed to cross once transversally. Every graph can be so drawn.

A point in a drawing is an *m-fold* crossing if *m* edges cross pairwise transversally there. There exist drawings of graphs with *2m* vertices which have two *m*-fold crossings.

**Question**: *Is this the maximum number of* m*-fold crossings?*

This is true for *m = *3 and 4. See [H] for more details.

The second problem concerns a special drawing of the *n* cycle C_n.

**Question:** *Does there exist a drawing of* C_n *so that every edge has exactly* r *crossings*? *Note the necessary conditions that *r *cannot exceed* n-3, *and that* n *and* r *cannot both be odd.*

The first two undecided cases are 1) *n *= 10, *r *= 6, and 2) *n *= 14, *r* = 6. Except for these small values the cases *r* at most 9 are known for all *n*.

References:

[H] H. Harborth, Drawings of graphs and multiple crossings, *Graph Theory and its Applications to Algorithms and Computer Science*}, Y. Alavi et al Eds., J. Wiley (1995) 413-421.

Submitted by: Heiko Harborth, Diskrete Mathematik, Technische Universitat Braunschweig, Pockelsstrasse 14, D-38106 Braunschweig, Germany

Send comments to *dan.archdeacon@uvm.edu *and *h.harborth@tu-bs.de*

August, 1995