Pagenumber problem.

Pagenumber problem.

Show full item record

Title: Pagenumber problem.
Author: Kapoor, Nidhi.
Abstract: A "book-embedding" of a graph G comprises of embedding the graph's nodes along the spine of a book, and embedding the edges on the pages so that the edges embedded on the same page do not intersect. This is also referred to as the page model. The "pagenumber" of a graph is the thickness of the smallest (in number of pages) book into which G can be embedded. A literature review of the one dimensional pagenumber problem is presented, and several two dimensional pagenumber models are proposed. Evolutionary computing methods on problems whose solution space comprises of permutations are reviewed. Since the pagenumber problem is known to be NP-complete, we describe two solutions using Hill Climbing methods and one solution using Genetic Algorithms for one and two-dimensional models. Two two-dimensional models are considered namely the square and rook models. We have given a unified framework for all three pagenumber models, in which a solution is a pair of two permutations (of nodes and edges), and which differ only by criteria for edge intersections. Experimental results on several kinds of graphs are then given.
Date: 1999
URI: http://hdl.handle.net/10393/8918

Files in this item

Files Size Format View
MQ48156.PDF 3.602Mb application/pdf View/Open

This item appears in the following Collection(s)

Show full item record


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