Search

It is known that every planar graph has a planar embedding where edges are represented by non-crossing straight-line segments. We study the planar slope number, i.e., the minimum number of distinct edge-slopes in such a drawing of a planar graph with maximum degree ∆. We show that the planar slope number of every series-parallel graph of maximum degree three is three. We also show that the planar slope number of every planar partial 3-tree and also every plane partial 3-tree is at most ]> . In particular, we answer the question of Dujmović et al. [Computational Geometry 38 (3), pp. 194–212 (2007)] whether there is a function f such that plane maximal outerplanar graphs can be drawn using at most f(∆) slopes. [ABSTRACT FROM AUTHOR]

We investigate embeddings of graphs into the infinite extended grid graph. The problem was motivated by computation on adiabatic quantum computers, but it is related to a number of other well studied grid embedding problems. Such problems typically deal with representing vertices by grid points, and edges by grid paths, while minimizing some objective function such as the area or the maximum length of the grid paths representing the edges. Our particular model, while expressible in this language, is more naturally viewed as one where the vertices are represented by subtrees of the grid (called islands), and the edges are represented by the usual grid edges joining the islands. Somewhat unexpectedly, these graphs turn out to unify such seemingly unrelated graph classes as the string graphs and the induced subgraphs of the extended grid. The connection is established by limiting the size (number of vertices) k of the representing islands. We study the problem of representability of an input graph G by islands of size at most k. We conjecture that this problem is NP-complete for any positive integer k, and prove the conjecture for k < 3 and k > 5; the cases k = 3, 4, 5 remain open. [ABSTRACT FROM AUTHOR]

We present a linear algorithm for c-planarity testing of clustered graphs, in which every cluster has at most four outgoing edges. [ABSTRACT FROM AUTHOR]