Embedding Planar Graphs at Fixed Vertex Locations |
| |
Authors: | János Pach Rephael Wenger |
| |
Institution: | (1) City College, New York and the Hungarian Academy of Sciences, Budapest e-mail: pach@cims.nyu.edu, XX;(2) The Ohio State University, Columbus, OH 43210, USA e-mail: wenger@cis.ohio-state.edu, US |
| |
Abstract: | Let G be a planar graph of n vertices, v
1,…,v
n
, and let {p
1,…,p
n
} be a set of n points in the plane. We present an algorithm for constructing in O(n
2) 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/403 bends.
Received: May 24, 1999 Final version received: April 10, 2000 |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|