Back to Search
Start Over
CONSTRAINED POINT-SET EMBEDDABILITY OF PLANAR GRAPHS.
- Source :
-
International Journal of Computational Geometry & Applications . Oct2010, Vol. 20 Issue 5, p577-600. 24p. 10 Diagrams. - Publication Year :
- 2010
-
Abstract
- This paper starts the investigation of a constrained version of the point-set embed-dability problem. Let G = (V,E) be a planar graph with n vertices, G′ = (V′,E′) a subgraph of G, and S a set of n distinct points in the plane. We study the problem of computing a point-set embedding of G on S subject to the constraint that G′ is drawn with straight-line edges. Different drawing algorithms are presented that guarantee small curve complexity of the resulting drawing, i.e. a small number of bends per edge. It is proved that: • If G′ is an outerplanar graph and S is any set of points in convex position, a point-set embedding of G on S can be computed such that the edges of E\E′ have at most 4 bends each. • If S is any set of points in general position and G′ is a face of G or if it is a simple path, the curve complexity of the edges of E\E′ is at most 8. • If S is in general position and G′ is a set of k disjoint paths, the curve complexity of the edges of E \ E′ is O(2k). [ABSTRACT FROM AUTHOR]
- Subjects :
- *SET theory
*GRAPHIC methods
*MATHEMATICS
*ALGORITHMS
*NUMERICAL analysis
Subjects
Details
- Language :
- English
- ISSN :
- 02181959
- Volume :
- 20
- Issue :
- 5
- Database :
- Academic Search Index
- Journal :
- International Journal of Computational Geometry & Applications
- Publication Type :
- Academic Journal
- Accession number :
- 54874602
- Full Text :
- https://doi.org/10.1142/S021819591000344X