Monotone Crossing Number

Pach, János and Tóth, Géza (2012) Monotone Crossing Number. In: Graph Drawing 19th International Symposium, GD 2011, September 21-23, 2011 , pp. 278-289(Official URL: http://dx.doi.org/10.1007/978-3-642-25878-7_27).

Full text not available from this repository.

Abstract

The monotone crossing number of G is defined as the smallest number of crossing points in a drawing of G in the plane, where every edge is represented by an x-monotone curve, that is, by a connected continuous arc with the property that every vertical line intersects it in at most one point. It is shown that this parameter can be strictly larger than the classical crossing number cr(G), but it is bounded from above by 2cr2 (G). This is in sharp contrast with the behavior of the rectilinear crossing number, which cannot be bounded from above by any function of cr(G).

Item Type: Conference Paper
Additional Information: 10.1007/978-3-642-25878-7_27
Classifications: G Algorithms and Complexity > G.420 Crossings
P Styles > P.480 Layered
URI: http://gdea.informatik.uni-koeln.de/id/eprint/1262

Actions (login required)

View Item View Item