Name
Abstract | ||
|---|---|---|
Given a planar graph G, we consider drawings of G in the plane where edges are represented by straight line segments (which possibly inter- sect). Such a drawing is specified by an injective embedding of the ver- tex set of G into the plane. Let fix(G, ) be the maximum integer k such that there exists a crossing-free redrawing 0 of G which keeps k vertices fixed, i.e., there exist k vertices v1,...,vk of G such that (vi) = 0(vi) for i = 1,...,k. We give examples of planar graphs G along with a drawing for which fix(G, ) = O( p n). In fact, such a drawing exists even if it is presup- posed that the vertices occupy any prescribed set of points on the boundary of a convex body. We also consider the parameter obf (G) of a graph G which is equal to the maximum number of edge crossings over all straight line drawings of G. We give examples of planar graphs with obf (G) ( 9 4 o(1))n 2 and prove that obf (T) ( 13 8 o(1))n 2 for every triangulation T. We also show that a given triangulation T can be eciently drawn with at least 0 .69obf (T) crossings. |
Year | Venue | Keywords |
|---|---|---|
2008 | Clinical Orthopaedics and Related Research | convex body,planar graph |
Field | DocType | Volume |
Outerplanar graph,Combinatorics,Planar straight-line graph,Polyhedral graph,Steinitz's theorem,Book embedding,Obfuscation,Planar graph,Mathematics | Journal | abs/0803.0 |
Citations | PageRank | References |
4 | 0.57 | 9 |
Authors | ||
5 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Mihyun Kang | 1 | 163 | 29.18 |
| Oleg Pikhurko | 2 | 318 | 47.03 |
| Alexander Ravsky | 3 | 11 | 1.42 |
| Mathias Schacht | 4 | 361 | 37.90 |
| Oleg Verbitsky | 5 | 191 | 27.50 |