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.
14634802
Bounded degree acyclic decompositions of digraphs
An acyclic decomposition of a digraph is a partition of the edges into acyclic subgraphs. Trivially every digraph has an acyclic decomposition into two subgraphs. It is proved that for every integer s ≥ 2 every digraph has an acyclic decomposition into s subgraphs such that in each subgraph the outdegree of each vertex v is at most ⌊deg(v)/s - 1⌋. For all digraphs this degree bound is optimal.
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.
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.
1804621
The Maximum Number of Edges in a Three-Dimensional Grid-Drawing
An exact formula is given for the maximum number of edges in a graph that admits a three-dimensional grid-drawing contained in a given bounding box. The first universal lower bound on the volume of threedimensional grid-drawings is obtained as a corollary. Our results generalise to the setting of multi-dimensional polyline grid-drawings.
123658090
Simultaneous diagonal flips in plane triangulations
Simultaneous diagonal flips in plane triangulations are investigated. It is proved that every triangulation with n ≥ 6 vertices has a simultaneous flip into a 4-connected triangulation, and that the set of edges to be flipped can be computed in $\cal O$(n) 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 $\cal O$(logn) simultaneous flips to transform one into the other. Moreover, o(log n) simultaneous flips are needed for some pairs of triangulations. The total number of edges flipped in this sequence is $\cal 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}\over{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}\over{7}}({n}-{2})$ edges. © 2006 Wiley Periodicals, Inc. J Graph Theory 54: 307–330, 2007 
 
A preliminary version of this paper was published in the Proceedings of the 17th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA'06). 
 
Research partially completed at Carleton University and McGill University (Montreal).
2937296
The Wisconsin Wind Tunnel: virtual prototyping of parallel computers
We have developed a new technique for evaluating cache coherent, shared-memory computers. The Wisconsin Wind Tunnel (WWT) runs a parallel shared-memory program on a parallel computer (CM-5) and uses execution-driven, distributed, discrete-event simulation to accurately calculate program execution time. WWT is a virtual prototype that exploits similarities between the system under design (the target) and an existing evaluation platform (the host). The host directly executes all target program instructions and memory references that hit in the target cache. WWT's shared memory uses the CM-5 memory's error-correcting code (ECC) as valid bits for a fine-grained extension of shared virtual memory. Only memory references that miss in the target cache trap to WWT, which simulates a cache-coherence protocol. WWT correctly interleaves target machine events and calculates target program execution time. WWT runs on parallel computers with greater speed and memory capacity than uniprocessors. WWT's simulation time decreases as target system size increases for fixed-size problems and holds roughly constant as the target system and problem scale.
3174704
Mechanisms for cooperative shared memory
This paper explores the complexity of implementing directory protocols by examining their <i>mechanisms</i> primitive operations on directories, caches, and network interfaces. We compare the following protocols: <i>Dir</i><sub>1</sub><i>B</i>, <i>Dir</i><sub>4</sub><i>B</i>, <i>Dir</i><sub>4</sub><i>NB</i>, <i>Dir</i><sub>n</sub><i>NB</i>[2], <i>Dir</i><sub>1</sub><i>SW</i>[9] and an improved version of <i>Dir</i><sub>1</sub>SW (<i>Dir</i><sub>1</sub><i>SW</i><sup>+</sup>). The comparison shows that the mechanisms and mechanism sequencing of <i>Dir</i><sub>1</sub><i>SW</i> and <i>Dir</i><sub>1</sub><i>SW</i><sup>+</sup> are simpler than those for other protocols.   We also compare protocol performance by running eight benchmarks on 32 processor systems. Simulations show that <i>Dir</i><sub>1</sub><i>SW</i><sup>+</sup>s performance is comparable to more complex directory protocols. The significant disparity in hardware complexity and the small difference in performance argue that <i>Dir</i><sub>1</sub><i>SW</i><sup>+</sup> may be a more effective use of resources. The small performance difference is attributable to two factors: the low degree of sharing in the benchmarks and Check- In/Check-Out (CICO) directives [9].<br> <br>
1926264
L Codes and Number Systems
Abstract The notion of an L code is introduced as a generalization of the customary notion of a code. Attention is focused on unary L codes. where the target alphabet consists of one letter only. Unary L codes can be identified with such number systems where the representation is unique. Surprisingly many unary morphisms are L codes. Furthermore, even for non-L-codes there is only one ‘exceptional length’ We also give a complete classification for the binary case.
13899040
The Regularity of Two-Way Nondeterministic Tree Automata Languages
We establish that regularly extended two-way nondeterministic tree automata with unranked alphabets have the same expressive power as regularly extended nondeterministic tree automata with unranked alphabets alphabets. We obtain this results by establishing regularly extended versions of a congruence on trees and of a congruence on, so called, views. Our motivation for the study of these tree models is the Extensible Markup Language (XML), a metalanguage for defining document grammars. Such grammars have regular sets of right-hand sides for their productions and tree automata provide an alternative and useful modeling tool for them. In particular, we believe that they provide a useful computational model for what we call caterpillar expressions.
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.