## Abstract

Minimum spanning tree problem is a very important problem in VLSI CAD. Given n points in a plane, a minimum spanning tree is a set of edges which connects all the points and has a minimum total length. A naive approach enumerates edges on all pairs of points and takes at least Ω(n^{2}) time. More efficient approaches find a minimum spanning tree only among edges in the Delaunay triangulation of the points. However, Delaunay triangulation is not well defined in rectilinear distance. In this paper, we first establish a framework for minimum spanning tree construction which is based on a general concept of spanning graphs. A spanning graph is a natural definition and not necessarily a Delaunay triangulation. Based on this framework, we then design an O(nlogn) sweep-line algorithm to construct a rectilinear minimum spanning tree without using Delaunay triangulation.

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

Title of host publication | Proceedings of the ASP-DAC 2001 |

Subtitle of host publication | Asia and South Pacific Design Automation Conference 2001 |

Publisher | Institute of Electrical and Electronics Engineers Inc. |

Pages | 192-197 |

Number of pages | 6 |

Volume | 2001-January |

ISBN (Electronic) | 0780366336 |

DOIs | |

State | Published - Jan 1 2001 |

Event | Asia and South Pacific Design Automation Conference 2001, ASP-DAC 2001 - Yokohama, Japan Duration: Jan 30 2001 → Feb 2 2001 |

### Other

Other | Asia and South Pacific Design Automation Conference 2001, ASP-DAC 2001 |
---|---|

Country/Territory | Japan |

City | Yokohama |

Period | 1/30/01 → 2/2/01 |

## Keywords

- Algorithm design and analysis
- Computational geometry
- Design automation
- Euclidean distance
- Testing
- Tree graphs
- Very large scale integration
- Wire

## ASJC Scopus subject areas

- Electrical and Electronic Engineering
- Computer Science Applications
- Computer Graphics and Computer-Aided Design