The Library
Improved upper bounds on the area required to embed arbitrary graphs
Tools
Tools
Tools
Dunne, Paul E. (1983) Improved upper bounds on the area required to embed arbitrary graphs. Coventry, UK: University of Warwick. Department of Computer Science. (Department of Computer Science Research Report). (Unpublished)
|
PDF
WRAP_cs-rr-055.pdf - Other - Requires a PDF viewer. Download (1154Kb) | Preview |
Abstract
We prove that any n-vertex graph of maximum degree r(r=3 or 4) can be embedded in a square grid of area Ar(n), where:
A3(n) ≤ n2/4 + O (n3/2)
A3(n) ≤ n2 + O (n3/2)
| Item Type: | Report | ||||
|---|---|---|---|---|---|
| Subjects: | Q Science > QA Mathematics > QA76 Electronic computers. Computer science. Computer software | ||||
| Divisions: | Faculty of Science > Computer Science | ||||
| Library of Congress Subject Headings (LCSH): | Graph theory | ||||
| Series Name: | Department of Computer Science Research Report | ||||
| Publisher: | University of Warwick. Department of Computer Science | ||||
| Place of Publication: | Coventry, UK | ||||
| Official Date: | December 1983 | ||||
| Dates: |
|
||||
| Number: | Number 55 | ||||
| Number of Pages: | 9 | ||||
| DOI: | CS-RR-055 | ||||
| Institution: | University of Warwick | ||||
| Theses Department: | Department of Computer Science | ||||
| Status: | Not Peer Reviewed | ||||
| Publication Status: | Unpublished | ||||
| Publisher Statement: | P.E. Dunne, “A Result on k-valent Graphs and its Application to a Graph Embedding Problem”, <i>Acta Informatica</i> <b>24</b>, pp. 447-458 (1987) | ||||
| Related URLs: |
Request changes or add full text files to a record
Repository staff actions (login required)
 |
View Item |
Downloads
Downloads per month over past year
