Constrained Point-Set Embeddability of Planar Graphs

Di Giacomo, Emilio and Didimo, Walter and Liotta, Giuseppe and Meijer, Henk and Wismath, Stephen (2009) Constrained Point-Set Embeddability of Planar Graphs. In: Graph Drawing 16th International Symposium, GD 2008, September 21- 24, 2008 , pp. 360-371(Official URL: http://dx.doi.org/10.1007/978-3-642-00219-9_35).

Full text not available from this repository.

Abstract

This paper starts the investigation of a constrained version of the pointset embeddability 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: (i) 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. (ii) 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. (iii) 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 ).

Item Type: Conference Paper
Additional Information: 10.1007/978-3-642-00219-9_35
Classifications: P Styles > P.720 Straight-line
P Styles > P.540 Planar
URI: http://gdea.informatik.uni-koeln.de/id/eprint/922

Actions (login required)

View Item View Item