Pach, János and Wenger, Rephael (1998) Embedding Planar Graphs at Fixed Vertex Locations. [Conference Paper]
Full text not available from this repository.
Abstract
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 |
|---|---|
| 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 |
| Deposited By: | Arnopolina, Galina |
| Deposited On: | 23 Nov 2004 |
| Last Modified: | 18 Sep 2008 13:08 |
| Alternative Locations: | http://www.springerlink.com/openurl.asp?genre=article&issn=0302-9743&volume=1547&spage=263 |
Repository Staff Only: item control page
