| EPSRC Reference: |
GR/S76694/01 |
| Title: |
Outerplanar Crossing Numbers |
| Principal Investigator: |
Salagean, Dr Am |
| Other Investigators: |
|
| Researcher Co-Investigators: |
|
| Project Partners: |
|
| Department: |
Computer Science |
| Organisation: |
Loughborough University |
| Scheme: |
Standard Research (Pre-FEC) |
| Starts: |
01 January 2004 |
Ends: |
31 December 2006 |
Value (£): |
163,905
|
| EPSRC Research Topic Classifications: |
| Algebra & Geometry |
Fundamentals of Computing |
| Logic & Combinatorics |
|
|
| EPSRC Industrial Sector Classifications: |
| No relevance to Underpinning Sectors |
|
|
| Related Grants: |
|
| Panel History: |
|
|
Summary on Grant Application Form |
|
Our project is focusing on low crossing outerplanar, 2-page and planar drawings of graphs. We will design new efficient sequential and parallel heuristics as well as fixed parameter tractable algorithms for producing outerplanar drawings with small number of crossings. To achieve this aim, we need to study fundamental questions on the crossing numbers in the one- and two-page as well as rectilinear drawings, and produce new strong theoretical results. We hope to prove that the planar and outerplanar crossing numbers do not differ too much and that a good approximation of the outerplanar crossing number should be a good approximation of the planar crossing number. We also intend to prove tight bounds for the outerplanar crossing number of standard graphs including 2-dimensional meshes, hypercubes, circulants and generalized Petersen graphs. We will also produce sequential and parallel heuristics for the outerplanar crossing number based on standard approaches as sifting and swapping combined with simulated annealing and stochastic hill climbing.The similarity with the optimal lineararrangement problem can lead to an approximation algorithm for the problem. We want to produce fixed parameter tractable algorithms for the buterplanar crossing number.We will also construct, implement, test and compare new heuristics and algorithms for 2-page drawings.
|
|
Key Findings |
|
This information can now be found on Gateway to Research (GtR) http://gtr.rcuk.ac.uk
|
|
Potential use in non-academic contexts |
|
This information can now be found on Gateway to Research (GtR) http://gtr.rcuk.ac.uk
|
|
Impacts |
|
| Description |
This information can now be found on Gateway to Research (GtR) http://gtr.rcuk.ac.uk |
| Summary |
|
| Date Materialised |
|
|
|
|
Sectors submitted by the Researcher |
|
This information can now be found on Gateway to Research (GtR) http://gtr.rcuk.ac.uk
|
| Project URL: |
http://www-staff.lboro.ac.uk/~coams/CrossingNumberProjectWeb/Home.htm |
| Further Information: |
|
| Organisation Website: |
http://www.lboro.ac.uk |