# The pagenumber of ordered sets.

 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

## Files in this item

Files Size Format View
NN19926.PDF 3.087Mb application/pdf View/Open

## Contact information

Morisset Hall (map)
65 University Private
Ottawa ON Canada
K1N 6N5

Tel. 613-562-5800 (4563)
Fax 613-562-5195

ruor@uottawa.ca