| dc.contributor.advisor |
Rival, I., |
en |
| dc.contributor.author |
Alzohairi, Mohammad. |
en |
| dc.date.accessioned |
2009-03-25T19:45:00Z |
|
| dc.date.available |
2009-03-25T19:45:00Z |
|
| dc.date.created |
1997 |
en |
| dc.date.issued |
2009-03-25T19:45:00Z |
|
| dc.identifier.citation |
Source: Dissertation Abstracts International, Volume: 58-06, Section: B, page: 3068. |
en |
| dc.identifier.isbn |
9780612199262 |
en |
| dc.identifier.uri |
http://hdl.handle.net/10393/9505 |
|
| dc.description.abstract |
The main result is this The pagenumber of a series-parallel planar ordered set is at most two. We present an $O(n\sp3)$ algorithm to construct a two-page embedding in the case that it is a lattice, where n is the number of the elements of the lattice. Once consequence of independent interest, is a characterization of series-parallel planar ordered sets. A k-edge set $\{(a\sb{i}, b\sb{i}):1\le i\le k\},$ in an ordered set P, forms a k-twist in a linear extension L of P, if we have in ?? We give necessary and sufficient conditions for the existence of a linear extension L of an ordered set P such that k edges form a k-twist in L. We also, give lower and upper bounds in some classes of ordered sets. We proved that the problem to determine minimum number of pages required for a fixed linear extension of an ordered set is NP-complete. We conjecture that the pagenumber of planar ordered sets is unbounded. In contrast, we conjecture that the pagenumber of planar lattices is at most four. |
en |
| dc.format.extent |
181 p. |
en |
| dc.publisher |
University of Ottawa (Canada). |
en |
| dc.subject.classification |
Mathematics. |
en |
| dc.title |
The pagenumber of ordered sets. |
en |
| dc.type |
Ph.D.Thesis (Ph.D.)--University of Ottawa (Canada), 1997. |
en |
