𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Bounds for rectilinear crossing numbers

✍ Scribed by Daniel Bienstock; Nathaniel Dean

Publisher
John Wiley and Sons
Year
1993
Tongue
English
Weight
780 KB
Volume
17
Category
Article
ISSN
0364-9024

No coin nor oath required. For personal study only.

✦ Synopsis

Abstract

A rectilinear drawing of a graph is one where each edge is drawn as a straight‐line segment, and the rectilinear crossing number of a graph is the minimum number of crossings over all rectilinear drawings. We describe, for every integer k β‰₯ 4, a class of graphs of crossing number k, but unbounded rectilinear crossing number. This is best possible since the rectilinear crossing number is equal to the crossing number whenever the latter is at most 3. Further, if we consider drawings where each edge is drawn as a polygonal line segment with at most one break point, then the resulting crossing number is at most quadratic in the regular crossing number. Β© 1993 John Wiley & Sons, Inc.

πŸ“œ SIMILAR VOLUMES

New results on rectilinear crossing numb
New results on rectilinear crossing numbers and plane embeddings
✍ Daniel Bienstock; Nathaniel Dean πŸ“‚ Article πŸ“… 1992 πŸ› John Wiley and Sons 🌐 English βš– 561 KB

## Abstract We show that if a graph has maximum degree __d__ and crossing number __k__, its rectilinear crossing number is at most __O__(__dk__^2^). Hence for graphs of bounded degree, the crossing number and the rectilinear crossing number are bounded as functions of one another. We also obtain a

Bounds for Betti Numbers
Bounds for Betti Numbers
✍ Tim RΓΆmer πŸ“‚ Article πŸ“… 2002 πŸ› Elsevier Science 🌐 English βš– 144 KB

In this paper we prove parts of a conjecture of Herzog giving lower bounds on the rank of the free modules appearing in the linear strand of a graded kth syzygy module over the polynomial ring. If in addition the module is β€«ήšβ€¬ n -graded we show that the conjecture holds in full generality. Furthermo