## Abstract

We give improved approximations for two classical embedding problems: (i) minimizing the number of crossings in a drawing of a bounded degree graph on the plane; and (ii) minimizing the VLSI layout area of a degree four graph. These improved algorithms can be applied to improve a variety of VLSI layout problems. Our results are as follows. (i) We compute a drawing on the plane of a bounded degree graph in which the sum of the numbers of vertices and crossings is O(log^{3} n) times the optimal minimum sum. This is a logarithmic factor improvement relative to the best known result. (ii) We compute s VLSI layout of a degree four graph in a grid with constant aspect ratio the area of which is O(log^{4} n) times the optimal minimum layout area. This is an O(log^{2} n) improvement over the best known long standing result.

Original language | English (US) |
---|---|

Pages (from-to) | 296-305 |

Number of pages | 10 |

Journal | Conference Proceedings of the Annual ACM Symposium on Theory of Computing |

State | Published - Dec 3 2000 |

Externally published | Yes |

Event | 32nd Annual ACM Symposium on Theory of Computing - Portland, OR, USA Duration: May 21 2000 → May 23 2000 |

## All Science Journal Classification (ASJC) codes

- Software