This paper studies planar drawings of graphs in which each vertex is represented as a point along a sequence of horizontal lines, called levels, and each edge is either a horizontal segment or a strictly y -monotone curve. A graph is s -span weakly leveled planar if it admits such a drawing where the edges have span at most s ; the span of an edge is the number of levels it touches minus one. We investigate the problem of computing s -span weakly leveled planar drawings from both the computational and the combinatorial perspectives. We prove the problem to be para-NP-hard with respect to its natural parameter s and investigate its complexity with respect to widely used structural parameters. We show the existence of a polynomial-size kernel with respect to vertex cover number and prove that the problem is FPT when parameterized by treedepth. We also present upper and lower bounds on the span for various graph classes. Notably, we show that cycle trees, a family of 2-outerplanar graphs generalizing Halin graphs, are Θ(log n )-span weakly leveled planar and 4-span weakly leveled planar when 3-connected. As a byproduct of these combinatorial results, we obtain improved bounds on the edge-length ratio of the graph families under consideration.

We study a question that lies at the intersection of classical research subjects in Topological Graph Theory and Graph Drawing: Computing a drawing of a graph with a prescribed number of crossings on a given set S of points, while ensuring that its curve complexity (i.e., maximum number of bends per edge) is bounded by a constant. We focus on trees: Let T be a tree, ϑ(T) be its thrackle number, and χ be any integer in the interval [0,ϑ(T)]. In the tangling phase we compute a topological linear embedding of T with ϑ(T) edge crossings and a constant number of spine traversals. In the untangling phase we remove edge crossings without increasing the spine traversals until we reach χ crossings. The computed linear embedding is used to construct a drawing of T on S with χ crossings and constant curve complexity. Our approach gives rise to an O(n²)-time algorithm for general trees and an O(n log n)-time algorithm for paths. We also adapt the approach to compute RAC drawings, i.e. drawings where the angles formed at edge crossings are π/2.

This paper studies planar drawings of graphs in which each vertex is represented as a point along a sequence of horizontal lines, called levels, and each edge is either a horizontal segment or a strictly $y$-monotone curve. A graph is $s$-span weakly leveled planar if it admits such a drawing where the edges have span at most $s$; the span of an edge is the number of levels it touches minus one. We investigate the problem of computing $s$-span weakly leveled planar drawings from both the computational and the combinatorial perspectives. We prove the problem to be para-NP-hard with respect to its natural parameter $s$ and investigate its complexity with respect to widely used structural parameters. We show the existence of a polynomial-size kernel with respect to vertex cover number and prove that the problem is FPT when parameterized by treedepth. We also present upper and lower bounds on the span for various graph classes. Notably, we show that cycle trees, a family of $2$-outerplanar graphs generalizing Halin graphs, are $Θ(\log n)$-span weakly leveled planar and $4$-span weakly leveled planar when $3$-connected. As a byproduct of these combinatorial results, we obtain improved bounds on the edge-length ratio of the graph families under consideration.

A weak dominance drawing Γ of a DAG G = ( V , E ) is a d -dimensional drawing such that D ( u ) < D ( v ) for every dimension D of Γ if there is a directed path from a vertex u to a vertex v in G , where D ( w ) is the coordinate of vertex w ∈ V in dimension D of Γ. If D ( u ) < D ( v ) for every dimension D of Γ, but there is no path from u to v , we have a falsely implied path (fip) . Minimizing the number of fips is an important theoretical and practical problem. Computing 2-dimensional weak dominance drawings with minimum number of fips is NP-hard. We show that this problem is FPT parameterized by the dimension d and the modular width mw . A key ingredient of our proof is the Compaction Lemma , where we show an interesting property of any weak dominance drawing of G with the minimum number of fips. This FPT result in weak dominance, which is interesting by itself because the fip-minimization problem is NP-hard, is used to prove our main contributions. Computing the dominance dimension of G , that is, the minimum number of dimensions d for which G has a d -dimensional dominance drawing (a weak dominance drawing with 0 fips), is a well-known NP-hard problem. We show that the dominance dimension of G is bounded by m w 2 (or mw , if m w < 4 ) and that computing the dominance dimension of G is an FPT problem with parameter mw . As far as we know, this the first FPT-algorithm to compute the dominance dimension of a DAG.

We present practical linear and almost linear-time algorithms to compute a chain decomposition of a directed acyclic graph (DAG), $G=(V,E)$. The number of vertex-disjoint chains computed is very close to the minimum. The time complexity of our algorithm is $O(|E|+c*l)$, where $c$ is the number of path concatenations and $l$ is the length of a longest path of the graph. We give a comprehensive explanation on factors $c$ and $l$ in the following sections. Our techniques have important applications in many areas, including the design of faster practical transitive closure algorithms. We observe that $|E_{red}|\leq width*|V|$ ($E_{red}$: non-transitive edges) and show how to find a substantially large subset of $E_{tr}$ (transitive edges) using a chain decomposition in linear time, without calculating the transitive closure. Our extensive experimental results show the interplay between the width, $E_{red}$, $E_{tr}$ in various models of graphs. We show how to compute a reachability indexing scheme in $O(k_c*|E_{red}|)$ time, where $k_c$ is the number of chains and $|E_{red}|$ is the number of non-transitive edges. This scheme can answer reachabilitiy queries in constant time. The space complexity of the scheme is $O(k_c*|V|)$. The experimental results reveal that our methods are even better in practice than the theoretical bounds imply, indicating how fast chain decomposition algorithms can be applied to the transitive closure problem.

Abstract Overloaded orthogonal drawing (OOD) is a recent graph visualization style specifically conceived for directed graphs. It merges the advantages of some popular drawing conventions like layered drawings and orthogonal drawings, and provides additional support for some common analysis tasks. We present a visualization framework called DAGView, which implements algorithms and graphical features for the OOD style. Besides the algorithm for acyclic digraphs, the DAGView framework implements extensions to visualize both digraphs with cycles and undirected graphs, with the additional possibility of taking into account user preferences and constraints. It also supports an interactive visualization of clustered digraphs, based on the use of strongly connected components. Moreover, we describe an experimental user study, aimed to investigate the usability of OOD within the DAGView framework. The results of our study suggest that OOD can be effectively exploited to perform some basic tasks of analysis in a faster and more accurate way when compared to other drawing styles for directed graphs.

BACKGROUND: The SYMBIOmatics Specific Support Action (SSA) is "an information gathering and dissemination activity" that seeks "to identify synergies between the bioinformatics and the medical informatics" domain to improve collaborative progress between both domains (ref. to http://www.symbiomatics.org). As part of the project experts in both research fields will be identified and approached through a survey. To provide input to the survey, the scientific literature was analysed to extract topics relevant to both medical informatics and bioinformatics. RESULTS: This paper presents results of a systematic analysis of the scientific literature from medical informatics research and bioinformatics research. In the analysis pairs of words (bigrams) from the leading bioinformatics and medical informatics journals have been used as indication of existing and emerging technologies and topics over the period 2000-2005 ("recent") and 1990-1990 ("past"). We identified emerging topics that were equally important to bioinformatics and medical informatics in recent years such as microarray experiments, ontologies, open source, text mining and support vector machines. Emerging topics that evolved only in bioinformatics were system biology, protein interaction networks and statistical methods for microarray analyses, whereas emerging topics in medical informatics were grid technology and tissue microarrays. CONCLUSION: We conclude that although both fields have their own specific domains of interest, they share common technological developments that tend to be initiated by new developments in biotechnology and computer science.

This paper reports on an analysis of the bioinformatics and medical informatics literature with the objective to identify upcoming trends that are shared among both research fields to derive benefits from potential collaborative initiatives for their future. Our results present the main characteristics of the two fields and show that these domains are still relatively separated.

Abstract Graphical notations are widely used for system specification. The usefulness of these notations depends primarily on their readability. Hence, automatic methods are needed to obtain efficient and understandable graphical representations of requirements. In this paper, we present an algorithm that automatically generates layouts of statecharts. We assume that relevant information is stored in a structure that we call a decomposition tree, and we draw the graph that models a statechart in a hierarchical fashion. Our approach excludes diagrams with inter‐level transitions. Copyright © 2001 John Wiley & Sons, Ltd.

The automatic placement of text or symbol labels corresponding to graphical objects is critical in several application areas such as Cartography, Geographical Information Systems, and Graph Drawing. In this paper we present a general framework for solving the problem of assigning text or symbol labels to a set of graphical features in two dimensional drawings or maps. Our approach does not favor the labeling of one type of graphical feature (such as a node, edge, or area) over another. Additionally, the labels are allowed to have arbitrary size and orientation. We have applied our framework to drawings of graphs. We have implemented our techniques and have performed extensive experimentation on hierarchical and orthogonal drawings of graphs. The resulting label assignments are very practical and indicate the effectiveness of our approach. 1 Introduction An important aspect of information visualization is the automatic placement of text or symbol labels corresponding to graphical object...

Many applications require human interaction during the design process. The user is given the ability to alter the graph as the design progresses. Interactive Graph Drawing allows the user to dynamically interact with the drawing of a graph. In this paper, we discuss features that are essential for an interactive orthogonal graph drawing system. We also describe some possible interactive drawing scenarios, present results on two of them, and compare their performance.

Let F be a spiral floorplan where each of its five basic rectangles has k implementations. In this paper, we show that there can be as many as /spl Omega/(k/sup 2/) useful implementations generated for F, in the worst case. This implies that the previously known O(k/sup 2/ log k)-time algorithm is almost optimal.

In this paper, we consider the two row maximum planar subset (TRMPS) problem in over-the-cell routing. The TRMPS problem requires selection of the maximum planar subset of nets, which can be routed between two rows of terminals in a cell row. This problem was first encountered by Gong, Liu, and Preas (1990). They stated the complexity of this problem to be unknown, and presented a min {1,k/d(S)} approximation algorithm, where k is the number of tracks available over the cell area and d(S) is the density of a solution S. We show that TRMPS problem can be solved optimally in polynomial time. We present a O(kn/sup 2/) dynamic programming algorithm for the TRMPS problem, where n is the number of nets. We also present a parallel version of our algorithm, which has a complexity of O(kn). Our algorithm can also be extended to solve the TRMPS problem, in the presence of prerouted nets, a chosen subset of nets, as well as for planar channel routing. We also apply our technique to obtain a 0.5 approximation, for over the cell routing in middle terminal model, thus improving the best known existing algorithm. The weighted version of the TRMPS problem, as well as, all the extensions can also be solved in O(kn/sup 2/) time.

Drawing graphs is an important problem that combines elements of computational geometry and graph theory. Applications can be found in a variety of areas including circuit layout, network management, software engineering, and graphics. The main contributions of this paper can be summarized as follows: • We devise a model for dynamic graph algorithms, based on performing queries and updates on an implicit representation of the drawing, and we show its applications. • We present efficient dynamic drawing algorithms for trees and series-parallel digraphs. As further applications of the model, we give dynamic drawing algorithms for planar $st$-digraphs and planar graphs. Our algorithms adopt a variety of representations (e.g., straight line, polyline, visibility) and update the drawing in a smooth way.

Studies the layer assignment problem of multi-chip modules (MMCs) and presents algorithms for layer assignment of 2-terminal and multiterminal nets. Solutions obtained by our experimental results show a significant reduction in the number of plane-pairs required by our algorithms, in comparison with the previous algorithms. We improve the upper bound for multiterminal nets and show that the solutions obtained by our algorithms are close to the lower bounds. >

We consider the problem of minimizing the area of a given floorplan by slightly changing its topology and present algorithms for solving it. Our algorithms are very efficient and the results compare favorably with the optimal solutions of the original floorplans. Specifically, we concentrate on converting spiral floorplans into slicing floorplans such that the area is minimized. Naturally, the cyclic channel precedence constraints disappear, which implies that the routing phase will be easier and will require less area. Surprisingly, our experimental results show that in most cases, this conversion is very good with respect to the area of the original spiral floorplan. Namely, the resulting slicing floorplans are smaller than the corresponding spiral floorplans.>

We present new algorithms for the layer assignment problem of multichip modules (MCM's). Our algorithms produce results that require between 70% and 25% of the number of layers required by the previous algorithms. We also present a new model for the problem that results in a better utilization of the routing area of the MCM, thus reducing the number of required layers even more. We provide lower and upper bounds on the performance of our algorithms which are tighter than the ones obtained before. Through our experimental results we show that the solutions obtained by our algorithms are close to the lower bounds.>

Difference bases are discussed and their relevance to sensor arrays is described. Several new analytical difference base structures that result in near optimal low-redundancy sensor arrays are introduced. Algorithms are also presented for efficiently obtaining sparse sensor arrays and/or difference bases. New bounds, related to arrays that have both redundancies and holes in their coarray, are presented. Some extensions to the idea of difference bases that may yield useful results for sensor array design are discussed.>

In this paper we give a model for dynamic graph algorithms, based on performing queries and updates on an implicit representation of the drawing. We present dynamic algorithms for drawing planar graphs that use a variety of drawing standards (such as polyline, straight-line, orthogonal, grid, upward, and visibility drawings), and address aesthetic criteria that are important for readability, such as the display of planarity, symmetry, and reachability. Also, we provide techniques that are especially tailored for important subclasses of planar graphs such as trees and series-parallel digraphs. Our dynamic drawing algorithms have the important property of performing “smooth updates” of the drawing. Of special geometric interest is the possibility of performing point-location and window queries on the implicit representation of the drawing.

An improved algorithm for solving the area optimization problem of spiral floorplans is presented. Each of the five basic rectangles of a spiral floorplan have O(n) implementations. The algorithm takes O(n/sup 2/logn) time, and requires O(n/sup 2/) space to solve the area optimization problem. The best previously known algorithm solved the problem in O(n/sup 3/logn) time and O(n/sup 3/) space.>

A complete characterization of the class of graphs that admit a cylindric visibility representation is presented, where vertices are represented by intervals parallel to the axis of the cylinder and the edges correspond to pairs of visible intervals. Moreover, linear time algorithms are given for testing the existence of and constructing such a representation. Important applications of cylindric visibility representations can be found in the layout of regular VLSI circuits, such as linear systolic arrays and bit-slice architectures. Also, alternative “dual” characterizations are presented of the graphs that admit visibility representations in the plane and in the cylinder.It is interesting to observe that neither of these two classes is contained in the other, although they have a nonempty intersection.

The author introduces a technique for wiring knock-knee layouts, without using two-colorable maps. This technique can be easily adapted to wire layouts on any type of grid, something that is rather complicated if one uses two-colorable maps. The author presents an algorithm for wiring a given layout in the square grid that uses at most four layers, and produces a two-layer wiring for a given layout, if such a wiring exists. The algorithm runs in time linear with respect to the area occupied by the layout.>

The problem of minimizing the average time to search for a key in a stored list of keys in a sequential access machine model (SAM) (e.g. a magnetic tape) is considered. The time to access a key in the list and the time to compare it to the given search key are taken into account. The time to access a key in the list is assumed proportional to the distance the head moves from its current location to reach the key. The time to read and compare the key to the search key is taken to be constant. Two classes of algorithms are analyzed and a matching lower bound on the average search time is presented. These results answer an open problem posed by S. Nishihara and H. Nishino (1987) regarding the optimal search algorithm for such a model. It is shown that the organization of the input data is crucial in determining the SAM complexity of the search problem.>

Consideration is given to the problem of finding a shortest path between two points in 3-D space with a restricted class of polyhedral obstacles (vertical buildings with a fixed number k of distinct heights). For the case when all the obstacles have equal heights, a shortest-path algorithm is presented with complexity O(n/sup 2/), i.e. the same complexity as for the 2-D case (n is the total number of corners in all the obstacles). For the general case (k distinct heights), an algorithm is presented for finding a shortest path in time O(n/sup 6k-1/). Also presented is an O(n/sup 2/) approximation algorithm that finds paths that are, at most, 8% longer than the shortest path for the case of k distinct heights when certain minimum separation requirements are satisfied, and a description is given of how the approximation algorithm can be extended to the general case (arbitrary separations).>

Article Free Access Share on Area requirement and symmetry display in drawing graphs Authors: G. Di Battista Dipartimento di Informatica e Sistemistica - University of Rome, Via Buonarroti, 12 - 00185 Rome, Italy Dipartimento di Informatica e Sistemistica - University of Rome, Via Buonarroti, 12 - 00185 Rome, ItalyView Profile , R. Tamassia Department of Computer Science - Brown University, Box 1910 - Providence, RI Department of Computer Science - Brown University, Box 1910 - Providence, RIView Profile , I. G. Tollis Department of Computer Science - The University of Texas at Dallas, P.O. Box 830688, MP 3.1- Richardson, TX Department of Computer Science - The University of Texas at Dallas, P.O. Box 830688, MP 3.1- Richardson, TXView Profile Authors Info & Claims SCG '89: Proceedings of the fifth annual symposium on Computational geometryJune 1989 Pages 51–60https://doi.org/10.1145/73833.73839Online:05 June 1989Publication History 22citation409DownloadsMetricsTotal Citations22Total Downloads409Last 12 Months5Last 6 weeks2 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF

Article Free Access Share on A 2n-2 step algorithm for routing in an nxn array with constant size queues Authors: T. Leighton Mathematics Department and Laboratory for Computer Science, Massachusetts Institute of Technology, Cambridge, MA Mathematics Department and Laboratory for Computer Science, Massachusetts Institute of Technology, Cambridge, MAView Profile , F. Makedon Department of Computer Science, University of Texas at Dallas, Richardson, TX Department of Computer Science, University of Texas at Dallas, Richardson, TXView Profile , I. G. Tollis Department of Computer Science, University of Texas at Dallas, Richardson, TX Department of Computer Science, University of Texas at Dallas, Richardson, TXView Profile Authors Info & Claims SPAA '89: Proceedings of the first annual ACM symposium on Parallel algorithms and architecturesMarch 1989 Pages 328–335https://doi.org/10.1145/72935.72970Published:01 March 1989Publication History 64citation353DownloadsMetricsTotal Citations64Total Downloads353Last 12 Months19Last 6 weeks1 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF

The problem is presented in the context of some recent theoretical advances on a related problem, called random satisfiability. These recent results indicate the theoretical limitations inherent in the problem of computing signal probabilities. Such limitations exist even if one uses Monte Carlo techniques for estimating signal probabilities. Theoretical results indicate that any practical method devised to compute signal probabilities would have to be evaluated purely on an empirical basis. An improved algorithm is offered for estimating the signal probabilities that takes into account the first-order effects of reconvergent input leads. It is demonstrated that this algorithm is linear in the product of the size of the network and the number of inputs. Empirical evidence is given indicating the improved performance obtained using this method over the straightforward probability computations. The results are very good, and the algorithm is very fast and easy to implement.>