6 papers · 1 filter
A slightly better bound on the crossing number in terms of the pair-crossing number
János Karl, Géza Tóth
The crossing number of a graph , ${\mbox{cr}}(G)$, is the minimum number of crossings, the pair-crossing number, ${\mbox{pcr}}(G)$, is the minimum number of pairs of crossing ed…
On the hollow enclosed by convex sets
Jenő Lehel, Géza Tóth
For , a family of compact convex sets in is called an -critical family provided any members of have a non-empty…
Crossings between non-homotopic edges
János Pach, Gábor Tardos, Géza Tóth
We call a multigraph {\em non-homotopic} if it can be drawn in the plane in such a way that no two edges connecting the same pair of vertices can be continuously transformed into e…
Improvement on the crossing number of crossing-critical graphs
János Barát, Géza Tóth
The crossing number of a graph is the minimum number of edge crossings over all drawings of in the plane. A graph is -crossing-critical if its crossing number is at…
Petruska's question on planar convex sets
Adam S. Jobson, André E. Kézdy, Jenő Lehel +2
Given convex sets in such that no point of the plane is covered by more than of the sets, is it true that there are two among the convex sets whose union contains…
Towards The Albertson Conjecture
János Barát, Géza Tóth
Albertson conjectured that if a graph has chromatic number then its crossing number is at least as much as the crossing number of . Albertson, Cranston, and Fox verifi…