International Journal of Foundations of Computer Science

Let G be a graph of n vertices with maximum degree d that can be drawn without crossing in a closed surface of Euler characteristic χ. It is proved that then G can be drawn in the plane with at most c_χdn crossings, where c_χ is a constant depending only on χ. This result, which is tight up to a constant factor, is strengthened and generalized to the case when there is no restriction on the degrees of the vertices.

We present a simplified version of the DFS-based Left-Right planarity testing and embedding algorithm implemented in Pigale [1, 2], which has been considered as the fastest implemented one [3]. We give here a full justification of the algorithm, based on a topological properties of Trémaux trees.

A convex grid drawing of a plane graph G is a drawing of G on the plane such that all vertices of G are put on grid points, all edges are drawn as straight-line segments without any edge-intersection, and every face boundary is a convex polygon. In this paper we give a linear-time algorithm for finding a convex grid drawing of every 4-connected plane graph G with four or more vertices on the outer face. The size of the drawing satisfies W + H ≤ n - 1, where n is the number of vertices of G, W is the width and H is the height of the grid drawing. Thus the area W · H is at most ⌈(n - 1)/2⌉ · ⌊(n - 1)/2⌋. Our bounds on the sizes are optimal in a sense that there exist an infinite number of 4-connected plane graphs whose convex drawings need grids such that W + H = n - 1 and W · H = ⌈(n - 1)/2⌉ · ⌊(n - 1)/2⌋.

We investigate the computational complexity of the following problem. Given a planar graph in which some vertices have already been placed in the plane, place the remaining vertices to form a planar straight-line drawing of the whole graph. We show that this extensibility problem, proposed in the 2003 "Selected Open Problems in Graph Drawing" [1], is NP-hard.

Let R and B be two sets of points such that the points of R are colored red and the points of B are colored blue. Let G be a planar graph such that |R| vertices of G are red and |B| vertices of G are blue. A bichromatic point-set embedding of G on R ∪ B is a crossing-free drawing of G such that each blue vertex is mapped to a point of B, each red vertex is mapped to a point of R, and each edge is a polygonal curve. We study the curve complexity of bichromatic point-set embeddings; i.e., the number of bends per edge that are necessary and sufficient to compute such drawings. We show that O(n) bends are sometimes necessary. We also prove that two bends per edge suffice if G is a 2-colored caterpillar and that for properly 2-colored caterpillars, properly 2-colored wreaths, 2-colored paths, and 2-colored cycles the number of bends per edge can be reduced to one, which is worst-case optimal.

In this paper we consider the problem of testing an arbitrary digraph G = (V,E) for upward planarity. In particular we describe two fixed-parameter tractable algorithms for testing the upward planarity of G. The first algorithm that we present can test the upward planarity of G in O(2^t · t! · |V|²)-time where t is the number of triconnected components of G. The second algorithm that we present uses a standard technique known as kernelisation and can test the upward planarity of G in O(|V|² + k⁴ · (2k)!)-time, where k = |E| - |V|.

In a convex drawing of a plane graph G, every facial cycle of G is drawn as a convex polygon. A polygon for the outer facial cycle is called an outer convex polygon. A necessary and sufficient condition for a plane graph G to have a convex drawing is known. However, it has not been known how many apices of an outer convex polygon are necessary for G to have a convex drawing. In this paper, we show that the minimum number of apices of an outer convex polygon necessary for G to have a convex drawing is, in effect, equal to the number of leaves in a triconnected component decomposition tree of a new graph constructed from G, and that a convex drawing of G having the minimum number of apices can be found in linear time.

Well-orderly tree is a powerful technique capable of deriving new results in graph encoding, graph enumeration and graph generation [3, 5]. In this paper, by using well-orderly trees, we prove that any plane graph G with n vertices has a visibility representation with height , which can be constructed in linear time. This improves the best previous bound of .

Traditionally, graph drawing algorithms represent vertices as circles and edges as curves connecting the vertices. We introduce the problem of drawing with "fat" edges, i.e., with edges of variable thickness. The thickness of an edge is often used as a visualization cue, to indicate importance, or to convey some additional information. We present a model for drawing with fat edges and a corresponding efficient polynomial time algorithm that uses the model.

We first focus on a restricted class of graphs that occur in VLSI wire routing and then show how to extend the algorithm to general planar graphs. We show how to convert an arbitrary wire routing into a homotopically equivalent routing that maximizes the distance between any two wires, which is a desired property in VLSI design. Among such, we obtain the routing with minimum total wire length. A homotopically equivalent routing that maximizes the distance between any two wires yields a graph drawing which maximizes edge thickness. Our algorithm does not require unit edge thickness but can be applied as well in the presence of different edge weights.

Let R be a rectangle with given area a(R), height h(R) and width w(R), and r₁, r₂, …, r_n be n soft rectangles, where we mean by a soft rectangle a rectangle r whose area a(r) is prescribed but whose aspect ratio ρ(r) is allowed to be changed. In this paper, we consider the problem of packing n soft rectangles r₁, r₂, …, r_n into R. We prove that, if a(R) ≥ Σ_1≤i≤n a(r_i) + 0.10103a_max and a_max ≤ 3(min{h(R), w(R)})² hold for a a_max = max_1≤i≤n a(r_i), then these n soft rectangles can be packed inside R so that the apect ratio of each rectangle r_i is at most 3.

We study counting various types of configurations in certain classes of graph automata viewed as discrete dynamical systems. The graph automata models of our interest are Sequential and Synchronous Dynamical Systems (SDSs and SyDSs, respectively). These models have been proposed as the mathematical foundation for a theory of large-scale simulations of complex multi-agent systems. Our emphasis in this paper is on the computational complexity of counting the fixed point and the garden of Eden configurations in Boolean SDSs and SyDSs. We show that counting these configurations is, in general, computationally intractable. We also show that this intractability still holds when both the underlying graphs and the node update rules of these SDSs and SyDSs are severely restricted. In particular, we prove that the problems of exactly counting fixed points, gardens of Eden and two other types of S(y)DS configurations are all #P-complete, even if the SDSs and SyDSs are defined over planar bipartite graphs, and each of their nodes updates its state according to a monotone update rule given as a Boolean formula. We thus add these discrete dynamical systems to the list of those problem domains where counting combinatorial structures of interest is intractable even when the related decision problems are known to be efficiently solvable.

Multicasting has become the main mode communication for providing a wide range of Internet services such as video broadcasting and multi-party teleconferencing, where data must be delivered to multiple recipients. The main focus of the work on securing multicast applications has been to control access and to ensure that only authorised users can access the broadcast. The authorised group is not fixed and may change over time and hence efficient methods of re-keying are of very important. Logical Key Hierarchy (LKH) schemes are schemes that use a logical tree to assign keys to users: each user will be attached to a leaf of the tree and will own all the keys allocated to the nodes from that leaf to the root of the tree. In this paper we propose a new LKH scheme in which only a subset of leaves are attached to users. This allows separation of the key sets of the users and providing protection against collusion attack. This property combined with the logarithmic size of the group controller storage makes the approach very attractive. We give a number of constructions, the best of which also has logarithmic cost for users' key storage and communication.

This paper introduces and discusses #-rewriting systems, which represent language-generating devices that resemble automata by using finitely many states without any nonterminals. It demonstrates that these systems characterize the well-known infinite hierarchy of language families resulting from programmed grammars of finite index in a very natural way. In its conclusion, this paper suggests some variants of #-rewriting systems.

In the paper [1], Theorem 23 and Example 24 are incorrect. The corrected version is presented in this note.