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.
6720403
The visual specification of context
We introduce a simple and novel visual technique for the specification of context in structured documents called T-graphs that we base on T-configurations in document trees. The technique is implemented in the current version of DESIGNER. Although we are applying this technique in the specification of context-dependent style sheets for HTML, XML, and SGML documents, it is clear that it can be used in other environments such as query specification for structured documents and for computer program transformations. We compare T-graphs with the context specification techniques found in other style-sheet systems and we also provide examples of context that we can and cannot specify with T-graphs. Although T-graphs are restrictive, they lend themselves to visual construction and modification, our main requirement when we designed this context specification method. We also investigate the time and space complexity of T-graph matching, a necessity for efficient implementation.
12635352
Planar Strong Visibility
Strong visibility is a generalization of standard visibility, defined with respect to a fixed set of line orientations. We investigate computational properties of this generalized visibility, as well as the related notion of strong convexity, and describe algorithms for the following tasks: 1. Testing the strong visibility of two points in a polygon. 2. Finding the strong convex hull of a point set or polygon. 3. Constructing the strong kernel of a polygon. 4. Identifying the points that are strongly visible from a given point.
29528938
Caterpillars: A Context Specification Technique
30874363
Synchronized EOL Forms Under Uniform Interpretation
— The aim ofthis paper is thejurther study oj EOLjorms under uniform interprétation. We are naturally led to the considération oj synchronized EOLjorms, which become the central thème of this paper. We prove: a ""strongest"" possible normaljorm resuit, the spanning normalJorm theorem; the non-existence oj uni-generatorsjor "reasonable" language amilies, which include thefinite, regular and context-jree j amilies; and a char act erization oj those ynchronized jorms which, under uniform interprétation, yield all regular languages. In closing we remark on three topics which are worthy oj separate investigation. Résumé. — Le but de cet article est de poursuivre l'étude des EOL-jormes sous des interprétations unijormes. Nous sommes conduits naturellement à considérer les EOL-jormes synchronisées qui deviennent le thème central de cet article. Nous établissons : un résultat sur la forme normale la plus « serrée » possible, le théorème sur la forme normale recouvrante, la non-existence d'uni-générateurs pour des jamilles « raisonnables » de langages qui comprennent les langages finis, rationnels et algébriques; et une caractérisation des formes synchronisées qui donnent, par interprétation unijorme, tous les langages rationnels. Pour terminer, nous effleurons trois domaines qui méritent une étude séparée.
448131
On the Complexity of the Balanced Vertex Ordering Problem
We consider the problem of finding a balanced ordering of the vertices of a graph. More precisely, we want to minimise the sum, taken over all vertices v, of the difference between the number of neighbours to the left and right of v. This problem, which has applications in graph drawing, was recently introduced by Biedl et al. [Discrete Applied Math. 148:27―48, 2005]. They proved that the problem is solvable in polynomial time for graphs with maximum degree three, but NP-hard for graphs with maximum degree six. One of our main results is to close the gap in these results, by proving NP-hardness for graphs with maximum degree four. Furthermore, we prove that the problem remains NP-hard for planar graphs with maximum degree four and for 5-regular graphs. On the other hand, we introduce a polynomial time algorithm that determines whetherthere is a vertex ordering with total imbalance smaller than a fixed constant, and a polynomial time algorithm that determines whether a given multigraph with even degrees has an 'almost balanced' ordering.
16845895
Refinement of Three-Dimensional Orthogonal Graph Drawings
In this paper we introduce a number of techniques for the refinement of three-dimensional orthogonal drawings of maximum degree six graphs. We have implemented several existing algorithms for three-dimensional orthogonal graph drawing including a number of heuristics to improve their performance. The performance of the refinements on the produced drawings is then evaluated in an extensive experimental study. We measure the aesthetic criteria of the bounding box volume, the average and maximum number of bends per edge, and the average and maximum edge length. On the same set of graphs used in Di Battista et al. [3], our main refinement algorithm improves the above aesthetic criteria by 80%, 38%, 10%, 54% and 49%, respectively.
52806192
Minimising the Number of Bends and Volume in 3-Dimensional
Orthogonal Graph Drawings with a Diagonal Vertex Layout
Abstract 
A 3-dimensional orthogonal drawing of a graph with maximum
degree at most 6, positions the vertices at grid-points in the 3-dimensional
orthogonal grid, and routes edges along grid-lines such that edge routes only
intersect at common end-vertices. Minimising the number of bends and the volume
of 3-dimensional orthogonal drawings are established criteria for measuring the
aesthetic quality of a given drawing. In this paper we present two algorithms
for producing 3-dimensional orthogonal graph drawings with the vertices
positioned along the main diagonal of a cube, so-called diagonal
drawings. This vertex-layout strategy was introduced in the 3-BENDS
algorithm of Eades et al. [Discrete Applied Math.
103:55–87, 2000]. We show that minimising the number of bends in a
diagonal drawing of a given graph is NP-hard. Our first algorithm minimises the
total number of bends for a fixed ordering of the vertices along the diagonal
in linear time. Using two heuristics for determining this vertex-ordering we
obtain upper bounds on the number of bends. Our second algorithm, which is a
variation of the above-mentioned 3-BENDS algorithm, produces 3-bend
drawings with n3+o(n3) volume, which is the best known upper bound for
the volume of 3-dimensional orthogonal graph drawings with at most three bends per
edge. 


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.