The page number problem is to determine the minimum number of pages in a book in which a graph G can
be embedded with the vertices placed in a sequence along the spine and the edges on the pages of the book
such that no two edges cross each other in any drawing. In this paper we have (a) statistically evaluated
five heuristics for ordering vertices on the spine for minimum number of edge crossings with all the edges
placed in a single page, (b) statistically evaluated four heuristics for distributing edges on a minimum
number of pages with no crossings for a fixed ordering of vertices on the spine and (c) implemented and
experimentally evaluated a hybrid evolutionary algorithm (HEA) for solving the pagenumber problem. In
accordance with the results of (a) and (b) above, in HEA, placement of vertices on the spine is decided
using a random depth first search of the graph and an edge embedding heuristic adapted from Chung et al.
is used to distribute the edges on a minimal number of pages. The results of experiments with HEA on
selected standard and random graphs show that the algorithm achieves the optimal pagenumber for the
standard graphs. HEA performance is also compared with the Genetic Algorithm described by Kapoor et
al. It is observed that HEA gives a better solution for most of the graph instances.
%0 Journal Article
%1 noauthororeditor
%A Satsangi, Dharna
%A Srivastava, Kamal
%A Gursaran,
%D 2012
%J International Journal of Computer Science, Engineering and Information Technology (IJCSEIT)
%K Algorithm Book Evolutionary Graph Hybrid Page a embedding graph layout number of problem
%N 2
%P 129-149
%R 10.5121/ijcseit.2012.2212
%T PAGE NUMBER PROBLEM: AN EVALUATION OF
HEURISTICS AND ITS SOLUTION USING A HYBRID
EVOLUTIONARY ALGORITHM
%U http://airccse.org/journal/ijcseit/papers/2212ijcseit12.pdf
%V 2
%X The page number problem is to determine the minimum number of pages in a book in which a graph G can
be embedded with the vertices placed in a sequence along the spine and the edges on the pages of the book
such that no two edges cross each other in any drawing. In this paper we have (a) statistically evaluated
five heuristics for ordering vertices on the spine for minimum number of edge crossings with all the edges
placed in a single page, (b) statistically evaluated four heuristics for distributing edges on a minimum
number of pages with no crossings for a fixed ordering of vertices on the spine and (c) implemented and
experimentally evaluated a hybrid evolutionary algorithm (HEA) for solving the pagenumber problem. In
accordance with the results of (a) and (b) above, in HEA, placement of vertices on the spine is decided
using a random depth first search of the graph and an edge embedding heuristic adapted from Chung et al.
is used to distribute the edges on a minimal number of pages. The results of experiments with HEA on
selected standard and random graphs show that the algorithm achieves the optimal pagenumber for the
standard graphs. HEA performance is also compared with the Genetic Algorithm described by Kapoor et
al. It is observed that HEA gives a better solution for most of the graph instances.
@article{noauthororeditor,
abstract = {The page number problem is to determine the minimum number of pages in a book in which a graph G can
be embedded with the vertices placed in a sequence along the spine and the edges on the pages of the book
such that no two edges cross each other in any drawing. In this paper we have (a) statistically evaluated
five heuristics for ordering vertices on the spine for minimum number of edge crossings with all the edges
placed in a single page, (b) statistically evaluated four heuristics for distributing edges on a minimum
number of pages with no crossings for a fixed ordering of vertices on the spine and (c) implemented and
experimentally evaluated a hybrid evolutionary algorithm (HEA) for solving the pagenumber problem. In
accordance with the results of (a) and (b) above, in HEA, placement of vertices on the spine is decided
using a random depth first search of the graph and an edge embedding heuristic adapted from Chung et al.
is used to distribute the edges on a minimal number of pages. The results of experiments with HEA on
selected standard and random graphs show that the algorithm achieves the optimal pagenumber for the
standard graphs. HEA performance is also compared with the Genetic Algorithm described by Kapoor et
al. It is observed that HEA gives a better solution for most of the graph instances.
},
added-at = {2018-07-16T09:23:27.000+0200},
author = {Satsangi, Dharna and Srivastava, Kamal and Gursaran},
biburl = {https://www.bibsonomy.org/bibtex/229057c47fbfb036b4ff2dbca0a7afa89/ijcseit},
doi = {10.5121/ijcseit.2012.2212},
interhash = {847271acfcce8b59760c80aa6eb08d72},
intrahash = {29057c47fbfb036b4ff2dbca0a7afa89},
issn = {2231-3117 [Online] ; 2231-3605 [Print]},
journal = {International Journal of Computer Science, Engineering and Information Technology (IJCSEIT)},
keywords = {Algorithm Book Evolutionary Graph Hybrid Page a embedding graph layout number of problem},
language = {English},
month = apr,
number = 2,
pages = {129-149},
timestamp = {2018-07-16T09:23:27.000+0200},
title = {PAGE NUMBER PROBLEM: AN EVALUATION OF
HEURISTICS AND ITS SOLUTION USING A HYBRID
EVOLUTIONARY ALGORITHM
},
url = {http://airccse.org/journal/ijcseit/papers/2212ijcseit12.pdf},
volume = 2,
year = 2012
}