Search

We present a new model for hybrid planarity that relaxes existing hybrid representation models. A graph G = (V , E) is (k , p) -planar if V can be partitioned into clusters of size at most k such that G admits a drawing where: (i) each cluster is associated with a closed, bounded planar region, called a cluster region ; (ii) cluster regions are pairwise disjoint, (iii) each vertex v ∈ V is identified with at most p distinct points, called ports , on the boundary of its cluster region; (iv) each inter-cluster edge (u , v) ∈ E is identified with a Jordan arc connecting a port of u to a port of v ; (v) inter-cluster edges do not cross or intersect cluster regions except at their end-points. We first tightly bound the number of edges in a (k , p) -planar graph with p < k. We then prove that (4 , 1) -planarity testing and (2 , 2) -planarity testing are NP-complete problems. Finally, we prove that neither the class of (2 , 2) -planar graphs nor the class of 1-planar graphs contains the other, indicating that the (k , p) -planar graphs are a large and novel class. [ABSTRACT FROM AUTHOR]

Let Γ be a straight-line drawing of a graph and let u and v be two vertices of Γ. The Gabriel disk of u , v is the disk having u and v as antipodal points. A pair 〈 Γ 0 , Γ 1 〉 of vertex-disjoint straight-line drawings forms a mutual witness Gabriel drawing when, for i = 0 , 1 , any two vertices u and v of Γ i are adjacent if and only if their Gabriel disk does not contain any vertex of Γ 1 − i. We characterize the pairs 〈 G 0 , G 1 〉 of complete bipartite graphs that admit a mutual witness Gabriel drawing. The characterization leads to a linear time testing algorithm. We also show that when the pair 〈 G 0 , G 1 〉 consists of two complete multi-partite graphs whose partition sets all have size greater than one, then the pair does not admit a mutual witness Gabriel drawing unless the pair is 〈 K 2 , 2 , K 2 , 2 〉. [ABSTRACT FROM AUTHOR]

Abstract We show that any outerplanar graph admits a planar straight-line drawing such that the length ratio of the longest to the shortest edges is strictly less than 2. This result is tight in the sense that for any ϵ > 0 there are outerplanar graphs that cannot be drawn with an edge-length ratio smaller than 2 − ϵ. We also show that this ratio cannot be bounded if the embeddings of the outerplanar graphs are given. [ABSTRACT FROM AUTHOR]

A 1-plane graph is a graph embedded in the plane such that each edge is crossed at most once. A 1-plane graph is optimal if it has maximum edge density. A red–blue edge coloring of an optimal 1-plane graph G partitions the edge set of G into blue edges and red edges such that no two blue edges cross each other and no two red edges cross each other. We prove the following: ( i ) Every optimal 1-plane graph has a red–blue edge coloring such that the blue subgraph is maximal planar while the red subgraph has vertex degree at most four; this bound on the vertex degree is worst-case optimal. ( ii ) A red–blue edge coloring may not always induce a red forest of bounded vertex degree. Applications of these results to graph augmentation and graph drawing are also discussed. [ABSTRACT FROM AUTHOR]

We study the problem of representing a graph as a storyplan, a recently introduced model for dynamic graph visualization. It is based on a sequence of frames, each showing a subset of vertices and a planar drawing of their induced subgraphs, where vertices appear and disappear over time. Namely, in the StoryPlan problem, we are given a graph and we want to decide whether there exists a total vertex appearance order for which a storyplan exists. We prove that the problem is NP -complete, and complement this hardness with two parameterized algorithms, one in the vertex cover number and one in the feedback edge set number of the input graph. We prove that partial 3-trees always admit a storyplan, which can be computed in linear time. Finally, we show that the problem remains NP -complete if the vertex appearance order is given and we have to choose how to draw the frames. [ABSTRACT FROM AUTHOR]

Let P be a set of n polygons in R 3 , each of constant complexity and with pairwise disjoint interiors. We propose a rounding algorithm that maps P to a simplicial complex Q whose vertices have integer coordinates. Every face of P is mapped to a set of faces (or edges or vertices) of Q and the mapping from P to Q can be done through a continuous motion of the faces such that: (i) the L ∞ Hausdorff distance between a face and its image during the motion is at most 3/2, and (ii) if two points become equal during the motion, they remain equal through the rest of the motion. In the worst case the size of Q is O (n 13) and the time complexity of the algorithm is O (n 15) but, under reasonable assumptions, these complexities decrease to O (n 4 n) and O (n 5) . Furthermore, these complexities are likely not tight and we expect, in practice on non-pathological data, O (n n) space and time complexities. [ABSTRACT FROM AUTHOR]