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