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, Montréal, Canada , 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
ID Code:312

Repository Staff Only: item control page


O. Bastert and S. Fekete. Geometrische Verdrhtungsprobleme. Technical Report 96.247, Angewandte Mathematik und Informatik, Universität zu Köln, Köln, Germany 1996.

P. Gritzmann, B. Mohar, J. Pach, and R. Pollack. Embedding a planar triangulation with vertices at specified points. American Mathematical Monthly 98 (1991), 165-166. (Solution to Problem E3341).

T. Leighton. Complexity Issues in VLSI. Foundation of Computing Series, MIT Press, Cambridge, MA, 1983.

J. Pach and P.K. Agarwal. Combinatorial geometry. John Wiley, New-York, 1995.

J. Pach, F. Shahrokhi, and M. Szegedy. Applications of the crossing number. Algorithmica 16 (1996), 111-117. (Special Issue on Graph Drawing, edited by G. Di Battista and R. Tamassia).

D. Souvaine and R. Wenger. Constructing piecewise linear homeomorphisms. Technical Report 94-52. DIMACS, New Brunswick, New Jersey, 1994.