Name
Abstract | ||
|---|---|---|
A drawing of a plane graph is called an inner rectangular drawing if every edge is drawn as a horizontal or vertical line segment so that every inner face is a rectangle In this paper we show that a plane graph G has an inner rectangular drawing D if and only if a new bipartite graph constructed from G has a perfect matching We also show that D can be found in time O(n1.5/log n) if G has n vertices and a sketch of the outer face is prescribed, that is, all the convex outer vertices and concave ones are prescribed. |
Year | DOI | Venue |
|---|---|---|
2004 | 10.1007/978-3-540-30551-4_60 | Int. J. Comput. Geometry Appl. |
Keywords | Field | DocType |
new bipartite graph,n vertex,outer face,plane graph g,plane graph,inner face,time o,inner rectangular drawing,convex outer vertex,log n | Discrete mathematics,Combinatorics,Outerplanar graph,Graph power,Graph factorization,Bipartite graph,Cycle graph,String graph,Dominance drawing,Planar graph,Mathematics | Conference |
Volume | Issue | ISSN |
16 | 2-3 | 0218-1959 |
ISBN | Citations | PageRank |
3-540-24131-0 | 0 | 0.34 |
References | Authors | |
15 | 3 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Kazuyuki Miura | 1 | 84 | 8.66 |
| Hiroki Haga | 2 | 0 | 0.34 |
| Takao Nishizeki | 3 | 1771 | 267.08 |