✦ LIBER ✦

Circle orders,N-gon orders and the crossing number

✍ Scribed by J. B. Sidney; S. J. Sidney; Jorge Urrutia

Publisher: Springer Netherlands
Year: 1988
Tongue: English
Weight: 583 KB
Volume: 5
Category: Article
ISSN: 0167-8094
DOI: 10.1007/bf00143891

No coin nor oath required. For personal study only.

✦ Synopsis

Let d!= {P, , . . . . P,} be a family of sets. A partial order P(@, <) on CD is naturally defined by the condition P, < 5 iff P, is contained in 4. When the elements of Cg are disks (i.e. circles together with their interiors), P(@, <) is called a circle order; if the elements of Cg are n-polygons, P(cD, <) is called an n-gon order. In this paper we study circle orders and n-gon orders.

The crossing number of a partial order introduced in [5] is studied here. We show that for every n, there are partial orders with crossing number n. We prove next that the crossing number of circle orders is at most 2 and that the crossing number of n-gon orders is at most 2n. We then produce for every n B 4 partial orders of dimension n which are not circle orders. Also for every n> 3, we prove that there are partial orders of dimension 2n +2 which are not n-gon orders.

Finally, we prove that every partial order of dimension 62n is an n-gon order.

📜 SIMILAR VOLUMES

Angle orders, regularn-gon orders and th

Angle orders, regularn-gon orders and the crossing number

✍ Nicola Santoro; Jorge Urrutia 📂 Article 📅 1987 🏛 Springer Netherlands 🌐 English ⚖ 674 KB

A note on vertex orders for stability nu

A note on vertex orders for stability number

✍ Mahadev, N. V. R.; Reed, B. A. 📂 Article 📅 1999 🏛 John Wiley and Sons 🌐 English ⚖ 115 KB 👁 2 views

We investigate vertex orders that can be used to obtain maximum stable sets by a simple greedy algorithm in polynomial time in some classes of graphs. We characterize a class of graphs for which the stability number can be obtained by a simple greedy algorithm. This class properly contains previousl

Cyclic-order graphs and Zarankiewicz's c

Cyclic-order graphs and Zarankiewicz's crossing-number conjecture

✍ D. R. Woodall 📂 Article 📅 1993 🏛 John Wiley and Sons 🌐 English ⚖ 750 KB

## Abstract Zarankiewicz's conjecture, that the crossing number of the complete‐bipartite graph __K__~__m, n__~ is [1/2 __m__] [1/2 (__m__] −1) [1/2 __n__] [1/2 (__n__ −1)], was proved by Kleitman when min(__m, n__) ≤ 6, but was unsettled in all other cases. The cyclic‐order graph CO__n__ arises na

The crossing number of K1,3,n and K2,3,n

✍ Kouhei Asano 📂 Article 📅 1986 🏛 John Wiley and Sons 🌐 English ⚖ 234 KB

In this article, we will determine the crossing number of the complete tripartite graphs K,.3.n and K2,3.n. Our proof depends on Kleitman's results for the complete bipartite graphs [D. J. Kleitman, The crossing number of K5,n. J. Combhatorial Theory 9 (1970) 375-3231. a graph G is the minimum numbe

On the crossing numbers of products of c

On the crossing numbers of products of cycles and graphs of order four

✍ Lowell W. Beineke; Richard D. Ringeisen 📂 Article 📅 1980 🏛 John Wiley and Sons 🌐 English ⚖ 446 KB

The crossing number ofC5 �Cn

✍ Kle??, Mari�n; Richter, R. Bruce; Stobert, Ian 📂 Article 📅 1996 🏛 John Wiley and Sons 🌐 English ⚖ 276 KB

We prove that the crossing number of C5 x C, is 372, which is consistent with the general conjecture that the crossing number of C,, x C, is ( m -2)n, for 3 5 m 5 n.