Name
Abstract | ||
|---|---|---|
A multigraph drawn in the plane is called non-homotopic if no pair of its edges connecting the same pair of vertices can be continuously transformed into each other without passing through a vertex, and no loop can be shrunk to its end-vertex in the same way. Edges are allowed to intersect each other and themselves. It is easy to see that a non-homotopic multigraph on n>1 vertices can have arbitrarily many edges. We prove that the number of crossings between the edges of a non-homotopic multigraph with n vertices and m>4n edges is larger than cm2n for some constant c>0, and that this bound is tight up to a polylogarithmic factor. We also show that the lower bound is not asymptotically sharp as n is fixed and m tends to infinity. |
Year | DOI | Venue |
|---|---|---|
2022 | 10.1016/j.jctb.2022.05.007 | Journal of Combinatorial Theory, Series B |
Keywords | DocType | Volume |
Graph drawing,Crossing number,Homotopic edges | Journal | 156 |
ISSN | Citations | PageRank |
0095-8956 | 0 | 0.34 |
References | Authors | |
4 | 3 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| János Pach | 1 | 2366 | 292.28 |
| Gábor Tardos | 2 | 1261 | 140.58 |
| Geza Toth | 3 | 0 | 0.34 |