Obfuscated Drawings of Planar Graphs
Obfuscated Drawings of Planar Graphs
复制标题
平面图的模糊绘图
DOI：
--
复制
发表时间：
2008
期刊：
影响因子：
--
通讯作者：
O. Verbitsky
中科院分区：
文献类型：
--
作者：
Mihyun Kang;O. Pikhurko;A. Ravsky;M. Schacht;O. Verbitsky
给定一个平面图G，我们考虑G在平面上的绘图，其中边由直线段表示（可能相交）。这样的绘图是由G的顶点集到平面的内射嵌入π指定的。设fix（G，π）是最大整数k，使得存在G的无交叉重绘π′，它保持k个顶点不变，即存在k个顶点v1，. . .，vk，使得π（vi）= π ′（vi），其中i = 1，. . .，k.我们给出了平面图G沿着有图π的例子，其中fix（G，π）= O（n）.事实上，即使假设顶点占据凸体边界上的任何指定点集，这样的绘图π也存在。我们还考虑了图G的参数obf（G），它等于图G的所有直线图上的最大边交叉数。本文给出了obf（G）≥（9 4 − o（1））n2的平面图的例子，并证明了对每个三角剖分T，obf（T）≥（13 8 − o（1））n2.我们还表明，一个给定的三角形T可以有效地绘制至少0.69 obf（T）交叉。
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.