Obfuscated Drawings of Planar Graphs
Mihyun Kang, Oleg Pikhurko, Alexander Ravsky, Mathias Schacht, Oleg Verbitsky · arXiv (Cornell University) · 2008
Abstract. Given a planar graph G, we consider drawings of G in the plane where edges are represented by straight line segments (which possibly intersect). Such a drawing is specified by an injective embedding π of the vertex set of G into the plane. Let fix(G, π) be the maximum integer k such that there exists a crossing-free redrawing π ′ of G which keeps k vertices fixed, i.e., there exist k vertices v1,..., vk of G such that π(vi) = π ′(vi) for i = 1,..., k. We give examples of planar graphs G along with a drawing π for which fix(G, π) = O ( √ n). In fact, such a drawing π exists even if it is presupposed 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))n2 and prove that obf (T) ≥ ( 13 8 − o(1))n2 for every triangulation T. We also show that a given triangulation T can be efficiently drawn with at least 0.69 obf (T) crossings. 1.