Embedding Planar Graphs at Fixed Vertex Locations

Pach, János and Wenger, Rephael (1998) Embedding Planar Graphs at Fixed Vertex Locations. In: Graph Drawing 6th International Symposium, GD’ 98, August 13-15, 1998 , pp. 263-274(Official URL: http://dx.doi.org/10.1007/3-540-37623-2_20).

Full text not available from this repository.


Let G be a planar graph of n vertices, v_1, \ldots, v_n, and let {p_1, \ldots, p_n} be a set of n points in the plane. We present an algorithm for constructing in O(n²) time a planar embedding of G, where vertex v_i is represented by point p_i and each edge is represented by a polygonal curve with O(n) bends (internal vertices.) This bound is asymptotically optimal in the worst case. In fact, if G is a planar graph containing at least m pairwise independent edges and the vertices of G are randomly assigned to points in convex position, then, almost surely, every planar embedding of G mapping vertices to their assigned points and edges to polygonal curves has at least m/20 edges represented by curves with at least m/40^3 bends.

Item Type: Conference Paper
Additional Information: 10.1007/3-540-37623-2_20
Classifications: M Methods > M.999 Others
P Styles > P.300 Curved
G Algorithms and Complexity > G.490 Embeddings
G Algorithms and Complexity > G.999 Others
G Algorithms and Complexity > G.210 Bends
URI: http://gdea.informatik.uni-koeln.de/id/eprint/312

Actions (login required)

View Item View Item