| Presentation | 2003/10/20 Octagonal Drawings of Plane Graphs with Prescribed Face Areas Md. Saidur Rahman, Kazuyuki Miura, Takao Nishizeki, |
|---|---|
| PDF Download Page | PDF download Page Link |
| Abstract(in Japanese) | (See Japanese page) |
| Abstract(in English) | An orthogonal drawing of a plane graph is called an "octagonal drawing" if each inner face is drawn as a rectilinear polygon of at most eight corners and the contour of the outer face is drawn as a rectangle. A "slicing graph" is obtained from a rectangle by repeatedly slicing it vertically and horizontally. A slicing graph is called a "good slicing graph" if either the upper subrectangle or the lower one obtained by any horizontal slice will never be vertically sliced. In this paper we show that any good slicing graph has an octagonal drawing with prescribed face areas, in which the area of each inner face is equal to a prescribed value. Such a drawing has practical applications in VLSI floorplanning. We also give a linear-time algorithm to find such a drawing. We furthermore present a sufficient condition for a plane graph to be a good slicing graph, and give a linear-time algorithm to find a tree-structure of slicing paths for any graph satisfying the condition. |
| Keyword(in Japanese) | (See Japanese page) |
| Keyword(in English) | Graph Drawing / Octagonal Drawing / Prescribed Face Area / Algorithm / VLSI Floorplanning |
| Paper # | COMP2003-45 |
| Date of Issue |
| Conference Information | |
| Committee | COMP |
|---|---|
| Conference Date | 2003/10/20(1days) |
| Place (in Japanese) | (See Japanese page) |
| Place (in English) | |
| Topics (in Japanese) | (See Japanese page) |
| Topics (in English) | |
| Chair | |
| Vice Chair | |
| Secretary | |
| Assistant | |
| Paper Information | |
| Registration To | Theoretical Foundations of Computing (COMP) |
|---|---|
| Language | ENG |
| Title (in Japanese) | (See Japanese page) |
| Sub Title (in Japanese) | (See Japanese page) |
| Title (in English) | Octagonal Drawings of Plane Graphs with Prescribed Face Areas |
| Sub Title (in English) | |
| Keyword(1) | Graph Drawing |
| Keyword(2) | Octagonal Drawing |
| Keyword(3) | Prescribed Face Area |
| Keyword(4) | Algorithm |
| Keyword(5) | VLSI Floorplanning |
| 1st Author's Name | Md. Saidur Rahman |
| 1st Author's Affiliation | Guraduate School of Information Sciences, Tohoku University() |
| 2nd Author's Name | Kazuyuki Miura |
| 2nd Author's Affiliation | Guraduate School of Information Sciences, Tohoku University |
| 3rd Author's Name | Takao Nishizeki |
| 3rd Author's Affiliation | Guraduate School of Information Sciences, Tohoku University |
| Date | 2003/10/20 |
| Paper # | COMP2003-45 |
| Volume (vol) | vol.103 |
| Number (no) | 394 |
| Page | pp.pp.- |
| #Pages | 8 |
| Date of Issue | |