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.
[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 firstname.lastname@example.org and email@example.com