Angle orders, regular n-gon orders and the crossing number
type: Item
instance of: scholarly article
title: Angle orders, regular n-gon orders and the crossing number
zbMATH Open document ID: 0643.06001
DOI: 10.1007/BF00337885
author: N. Santoro
author: J. Urrutia
published in: Order
publication date: 1987-01-01T00:00:00Z
review text: Let \(X:=\{x_ 1,...,x_ m\}\) be a finite set, \(<\) be a partial order relation on X. A family \(\Phi =\{S_ 1,...,S_ m\}\) of sets is called a representation of \((X,<)\) iff \((x_ i<x_ j\) iff \(S_ i\subset S_ j\) for all \(i\neq j)\). \((X,<)\) is called angle order (regular n-gon order, circle order) iff there exists a representation \(\Phi\) consisting of angular regions (of regular polygons having n sides, circles) in the real affine plane. Let \(P:=(X,<)\) be a partial order, and let dim P denote the smallest number of linear orders whose intersection yields P. Using the concept of crossing number of a partial order defined by \textit{M. C. Golumbic}, \textit{D. Rotem}, and \textit{J. Urrutia} [Discrete Math. 43, 37-46 (1983; Zbl 0502.05050)], the authors prove: There exists P such that dim P\(=4\), \(| X| =14\), and for no value of n this partial order P is a regular n-gon order. On the contrary, dim P\(=3\) implies that P is a regular n-gon order for any \(n\geq 3\), where in particular, the triangle representation can be chosen equilateral. Conversely, if P is a regular n-gon oder, then dim \(P\leq n\), the bound being reached by some suitable P for any \(n\geq 3\). Finally, the authors consider the following question from \textit{P. C. Fishburn} and \textit{W. T. Trotter} [Order 1, 333-343 (1985; Zbl 0558.06003)]: What is the least dimension of a partial order which is not an angle order ? They give an example of a non-angle order P such that dim P\(=6\), \(| X| =64\).
reviewed by: Horst Szambien
Mathematics Subject Classification ID: 06A06
Mathematics Subject Classification ID: 06B05
Mathematics Subject Classification ID: 05A05
zbMATH DE Number: 4047783
zbMATH Keywords: polygon order
zbMATH Keywords: angle order
zbMATH Keywords: regular n-gon order
zbMATH Keywords: circle order
zbMATH Keywords: regular polygons
zbMATH Keywords: crossing number
MaRDI profile type: Publication
cites work: Partially Ordered Sets
cites work: Q3344239
cites work: Angle orders
cites work: Comparability graphs and intersection graphs
cites work: Q5598258
cites work: Circular permutation graphs
cites work: Circle orders, n-gon orders and the crossing number
Recommended article: Angle orders
Recommended article: Circle orders and angle orders
Recommended article: Q4326649
Recommended article: Spherical containment and the Minkowski dimension of partial orders
Recommended article: Q4982895
Recommended article: Extendability of cyclic orders
Recommended article: On the Boolean dimension of spherical orders
Recommended article: The Order Dimension of Convex Polytopes
Recommended article: Drawing and encoding two-dimensional posets
description: scientific article; zbMATH DE number 4047783