Name
Abstract | ||
|---|---|---|
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 a graph satisfying the condition. |
Year | DOI | Venue |
|---|---|---|
2009 | 10.1016/j.comgeo.2008.09.002 | Computational Geometry: Theory and Applications |
Keywords | Field | DocType |
prescribed face area,prescribed value,horizontal slice,linear-time algorithm,octagonal drawing,algorithm,vlsi floorplanning,outer face,plane graph,inner face,graph drawing,orthogonal drawing,satisfiability,tree structure | Strength of a graph,Geometric graph theory,Discrete mathematics,Outerplanar graph,Combinatorics,Circle graph,Slope number,Computer science,String graph,Lattice graph,Planar graph | Journal |
Volume | Issue | ISSN |
42 | 3 | Computational Geometry: Theory and Applications |
Citations | PageRank | References |
10 | 0.87 | 17 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Md. Saidur Rahman | 1 | 342 | 41.83 |
| Kazuyuki Miura | 2 | 84 | 8.66 |
| Takao Nishizeki | 3 | 1771 | 267.08 |