Embedding Graphs into Embedded Graphs

  • PDF / 1,841,139 Bytes
  • 24 Pages / 439.37 x 666.142 pts Page_size
  • 57 Downloads / 321 Views

DOWNLOAD

REPORT


Embedding Graphs into Embedded Graphs Radoslav Fulek1  Received: 10 October 2017 / Accepted: 7 May 2020 © Springer Science+Business Media, LLC, part of Springer Nature 2020

Abstract A (possibly degenerate) drawing of a graph G in the plane is approximable by an embedding if it can be turned into an embedding by an arbitrarily small perturbation. We show that testing whether a piece-wise linear drawing of a planar graph G in the plane is approximable by an embedding can be carried out in polynomial time, if a desired embedding of G belongs to a fixed isotopy class. In other words, we show that c-planarity with embedded pipes is tractable for graphs with prescribed combinatorial embedding. To the best of our knowledge, an analogous result was previously known essentially only when G is a cycle. Keywords  Graph embedding · Clustered planarity · Weakly simple polygons · Euler circuit

1 Introduction In the theory of graph visualization a drawing of a graph G = (V, E) in the plane is usually assumed to be free of degeneracies, that is, edge overlaps and edges passing through a vertex. However, in practice degenerate drawings often arise and need to be dealt with. The present work concerns the algorithmic problem of detecting denegerate drawings that can be perturbed into embeddings. (See Sect. 2 for the definitions of a generic and degenerate drawing, and an embedding.) Recent papers [1, 9] address this problem for simple polygons, which can be thought of as straight-line (rectilinear) embeddings of graph cycles. Chang et al. [9] gave an O(n2 log n)-time algorithm to detect if a given polygon with n vertices can be turned into a simple (non self-intersecting) one by small perturbations of its vertices, or in other words if the polygon is weakly simple. We mention that there exists an earlier closely related definition of weakly simple polygons by Toussaint [8, 31], An extended abstract of the contribution was accepted to ISAAC 2017. * Radoslav Fulek [email protected] 1



University of Arizona, Tucson, AZ, USA

13

Vol.:(0123456789)

Algorithmica

however, as pointed out in [9], this notion is not well-defined for general polygons with so-called spurs. A spur can be thought of as a U-turn, or more formally, a connected portion of the polygon consisting of two identical overlapping parts, each of which is free of self-intersections, that immediately follow one another during polygon’s traversal; see [9] for an overview of attempts at combinatorial definitions of a polygon not intersecting itself. Akitaya et al. [1] improved the running time of the algorithm by Chang et al. to O(n log n) . The combinatorial formulation of this problem corresponds to the setting of c-planarity with embedded pipes introduced by Cortese et al. [12] well before the two aforementioned papers. Therein only an O(n3 )-time algorithm for the problem was given. Nevertheless, the algorithms in [1, 9] were built upon the ideas from [12]. Moreover, to the best of our knowledge, the complexity status of the c-planarity with embedded pipes is

Data Loading...