12322077
Bounded Degree Book Embeddings and Three-Dimensional Orthogonal Graph Drawing
A book embedding of a graph consists of a linear ordering of the vertices along a line in 3-space (the spine), and an assignment of edges to half-planes with the spine as boundary (the pages), so that edges assigned to the same page can be drawn on that page without crossings. Given a graph G = (V,E), let f : V → ℕ be a function such that 1 ≤ f(υ) ≤ deg(υ). We present a Las Vegas algorithm which produces a book embedding of G with \( O(\sqrt {|E| \cdot \max _\upsilon \left\lceil {\deg (\upsilon )/f(\upsilon )} \right\rceil } ) \) pages, such that at most f(v) edges incident to a vertex v are on a single page. This algorithm generalises existing results for book embeddings. We apply this algorithm to produce 3-D orthogonal drawings with one bend per edge and O(∣V ∣3/2∣E∣) volume, and single-row drawings with two bends per edge and the same volume. In the produced drawings each edge is entirely contained in some Z-plane; such drawings are without so-called cross-cuts, and are particularly appropriate for applications in multilayer VLSI. Using a different approach, we achieve two bends per edge with O(∣V ∣∣E∣) volume but with cross-cuts. These results establish improved bounds for the volume of 3-D orthogonal graph drawings.
341729
Lower Bounds for the Number of Bends in Three-Dimensional Orthogonal Graph Drawings
In this paper we present the first non-trivial lower bounds for the total number of bends in 3-D orthogonal drawings of maximum degree six graphs. In particular, we prove lower bounds for the number of bends in 3-D orthogonal drawings of complete simple graphs and multigraphs, which are tight in most cases. These result are used as the basis for the construction of infinite classes of c-connected simple graphs and multigraphs (2 ≤ c ≤ 6) of maximum degree Δ (3 ≤ Δ ≤ 6) with lower bounds on the total number of bends for all members of the class. We also present lower bounds for the number of bends in general position 3-D orthogonal graph drawings. These results have significant ramifications for the '2-bends' problem, which is one of the most important open problems in the field.
122961893
Lower Bounds for the Number of Bends in Three-Dimensional Orthogonal Graph Drawings
123081730
Simultaneous diagonal flips in plane triangulations
Simultaneous diagonal flips in plane triangulations are investigated. It is proved that every triangulation with at least six vertices has a simultaneous flip into a 4-connected triangulation, and that it can be computed in linear time. It follows that every triangulation has a simultaneous flip into a Hamiltonian triangulation. This result is used to prove that for any two n-vertex triangulations, there exists a sequence of O(log n) simultaneous flips to transform one into the other. The total number of edges flipped in this sequence is O(n). The maximum size of a simultaneous flip is then studied. It is proved that every triangulation has a simultaneous flip of at least 1/3(n − 2) edges. On the other hand, every simultaneous flip has at most n − 2 edges, and there exist triangulations with a maximum simultaneous flip of 6/7 (n − 2) edges.
45354174
On the Parameterized Complexity of Layered Graph Drawing
We consider graph drawings in which vertices are assigned to layers and edges are drawn as straight line-segments between vertices on adjacent layers. We prove that graphs admitting crossing-free h-layer drawings (for fixed h) have bounded pathwidth. We then use a path decomposition as the basis for a linear-time algorithm to decide if a graph has a crossing-free h-layer drawing (for fixed h). This algorithm is extended to solve a large number of related problems, including allowing at most k crossings, or removing at most r edges to leave a crossing-free drawing (for fixed k or r). If the number of crossings or deleted edges is a non-fixed parameter then these problems are NP-complete. For each setting, we can also permit downward drawings of directed graphs and drawings in which edges may span multiple layers, in which case the total span or the maximum span of edges can be minimized. In contrast to the so-called Sugiyama method for layered graph drawing, our algorithms do not assume a preassignment of the vertices to layers.
32158792
An Algorithm for Three-Dimensional Orthogonal Graph Drawing
In this paper we present an algorithm for 3-dimensional orthogonal graph drawing based on the movement of vertices from an initial layout along the main diagonal of a cube. For an n-vertex m-edge graph with maximum degree six, the algorithm produces drawings with bounding box volume at most 2:37n3 and with a total of 7m/3 bends, using no more than 4 bends per edge route. For maximum degree five graphs the bounding box has volume n3 and each edge route has two bends. These results establish new bounds for 3-dimensional orthogonal graph drawing algorithms and improve on some existing bounds.
205885836
On Predecessors of Finite Languages
We continue the study of finite grammatical families by characterizing when a family has a predecessor. This characterization implies that (i) the existence of predecessors for finite families is decidable and (ii) the collection of context-free grammatical families, each family of which contains all regular languages, is not maximal dense.
12937575
Application-specific protocols for user-level shared memory
Recent distributed shared memory (DSM) systems and proposed shared-memory machines have implemented some or all of their cache coherence protocols in software. One way to exploit the flexibility of this software is to tailor a coherence protocol to match an application's communication patterns and memory semantics. This paper presents evidence that this approach can lead to large performance improvements. It shows that application-specific protocols substantially improved the performance of three application programs-appbt, em3d, and barnes-over carefully tuned transparent shared memory implementations. The speed-ups were obtained on Blizzard, a fine-grained DSM system running on a 32-node Thinking Machines CM-5.<<ETX>>
12582971
Stabbing line segments
An algorithm for the geometric problem of determining a line (called a stabbing line) which intersects each ofn given line segments in the plane is presented. As a matter of fact, the algorithm computes a description of all stabbing lines. A purely geometric fact is proved which infers that this description requiresO(n) space to be specified. Our algorithm computes it inO(n logn) time which is optimal in the worst case.Using the description of the stabbing lines, we are able to decide inO(logn) time whether or not a specified line is a stabbing line. Finally, the problem of maintaining the description of all stabbing lines while inserting and deleting line segments is addressed.
23304788
On non context-free grammar forms
A grammar formF defines via a so-calledinterpretation mechanism, a family of languages(F). In this paper we establish that for many grammar formsF, (the family of context-free languages) implies(F)=RE (the family of recursively enumerable sets). We conjecture that this is also true in general. Because of this, it seems necessary to use restricted interpretations for non context-free grammar forms, a form giving then rise to a family We compare the obvious alternatives for restricting interpretations and focus attention on two promising alternatives,Q(F) andst(F) and their combinationQ, st(F). Using st-interpretations, surprising families can be generated and strong normal form results can be obtained. Closure results and decidability results are also given. UnderQ, st-interpretation, it is possible to characterize a number of well-known families of languages betweenCF andRE, including the families of EOL, ETOL, matrix and scattered context languages.
3174555
A characterization of Thompson digraphs
A finite-state machine is called a Thompson machine if it can be constructed from an empty-free regular expression using the construction of Thompson as modified by Hopcroft and Ullman. We call the underlying digraph of a Thompson machine a Thompson digraph. We characterize Thompson digraphs and we give an algorithm that generates an equivalent regular expression from a Thompson machine that has size linear in the total number of states and transitions. Although the algorithm is simple, it is novel in that the usual constructions of equivalent regular expressions from finite-state machines produce regular expressions that have size exponential in the size of the given machine, in the worst case. The algorithm provides a tentative first step in the construction of small expressions from finite-state machines.