HSV05.pdf (173.1 kB)

Crossing minimisation Heuristics for 2-page drawings

Download (173.1 kB)
journal contribution
posted on 25.09.2006 by Hongmei He, Ondrej Sykora, Imrich Vrt'o
The minimisation of edge crossings in a book drawing of a graph G is one of important goals for a linear VLSI design, and the two-page crossing number of a graph G provides an upper bound for the standard planar crossing number. We propose several new heuristics for the 2-page drawing problem and test them on benchmark test sets like Rome graphs, Random Connected Graphs and some typical graphs. We get exact results of some structural graphs, and compare some of the experimental results with the one in paper.

History

School

  • Science

Department

  • Computer Science

Pages

154455 bytes

Citation

HE, SÝKORA and VRT'O, 2005. Crossing minimisation heuristics for 2-page drawings. Electronic notes in discrete mathematics, 22, pp. 527-534

Publisher

© Elsevier

Publication date

2005

Notes

This article was published in the journal, Electronic notes in discrete mathematics [© Elsevier] and is also available at: http://www.sciencedirect.com/science/journal/15710653

ISSN

1571-0653

Language

en

Exports