Polyline drawings with topological constraints

摘要

We study the problem of representing topological graphs as polyline drawings with few bends per edge and such that the topology of the graph is either fully or partially preserved. More formally, let G be a simple topological graph and let Gamma be a polyline drawing of G. Drawing Gamma partially preserves the topology of G if it has the same external boundary, the same circular order of the edges around each vertex, and the same set of crossings as G. while it fully preserves the topology of G if the planarization of G and the planarization of Gamma have the same planar embedding. We prove that if the set of crossing-free edges of G forms a biconnected (connected) spanning subgraph, then G admits a polyline drawing that partially preserves its topology and that has curve complexity at most one (three), i.e., with at most one (three) bend(s) per edge. If, however, the set of crossing-free edges of G is not a connected spanning subgraph, the curve complexity may be Omega(root n), while it is O(1) if the number of connected components is O(1). Concerning drawings that fully preserve the topology, we show that if G is k-skew (i.e., it becomes planar after removing k suitably chosen edges), it admits one such drawing with curve complexity at most 2k; for 1-skew graphs, the curve complexity can be reduced to one, which is a tight bound. We also consider optimal 2-plane graphs (i.e., with at most two crossings per edge and maximum edge density), for which we discuss trade-offs between curve complexity and crossing angle resolution of drawings that fully preserve the topology. (C) 2019 Elsevier B.V. All rights reserved.