Back to Search
Start Over
INNER RECTANGULAR DRAWINGS OF PLANE GRAPHS.
- Source :
-
International Journal of Computational Geometry & Applications . Jun2006, Vol. 16 Issue 2/3, p249-270. 22p. 7 Diagrams, 9 Graphs. - Publication Year :
- 2006
-
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. [ABSTRACT FROM AUTHOR]
Details
- Language :
- English
- ISSN :
- 02181959
- Volume :
- 16
- Issue :
- 2/3
- Database :
- Academic Search Index
- Journal :
- International Journal of Computational Geometry & Applications
- Publication Type :
- Academic Journal
- Accession number :
- 20594298
- Full Text :
- https://doi.org/10.1142/S0218195906002026