A rectilinear-upward planar drawing of a digraph G is a crossing-free drawing of G where each edge is either a horizontal or a vertical segment, and such that no directed edge points downward. Rectilinear-Upward Planarity Testing is the problem of deciding whether a digraph G admits a rectilinear-upward planar drawing. We study the complexity of Rectilinear-Upward Planarity Testing and provide several algorithmic results. Precisely, we prove that: ( i ) the problem is NP-complete, even if G is biconnected; ( i i ) it can be solved in linear time when an upward planar embedding of G is fixed; ( i i i ) the problem is polynomial-time solvable for biconnected digraphs of treewidth at most two, i.e., for digraphs whose underlying undirected graph is a series-parallel graph; ( i v ) the problem is fixed-parameter tractable (namely, fixed-parameter linear) for all biconnected graphs, when parameterized by the number of sources and sinks in the digraph. • We study the algorithmic complexity of a problem that combines two well-established topics in graph drawing, namely rectilinear planar drawings and upward planar drawings. This problems, called rectilinear-upward planarity testing, asks to decide whether an input planar di-graph admits a planar drawing where each edge is either a horizontal or a vertical segment, and no edge points downwards. • We prove that rectilinear-upward planarity testing is NP-complete, even for biconnected digraphs. • We provide a linear-time algorithm for rectilinear-upward planarity testing of digraphs with a fixed upward planar embedding. • We provide a quadratic-time algorithm for rectilinear-upward planarity testing of biconnected partial 2-trees (i.e., digraphs whose underlying undirected graph is series-parallel) in the variable embedding setting. • We provide a fixed-parameter linear (FPL) algorithm for rectilinear- upward planarity testing of general biconnected digraphs in the variable embedding setting.

Given two classes of graphs, 𝒢₁ ⊆ 𝒢₂, and a c-connected graph G ∈ 𝒢₁, we wish to augment G with a smallest cardinality set of new edges F to obtain a k-connected graph G' = (V,E∪ F) ∈ 𝒢₂. In general, this is the c → k connectivity augmentation problem. Previous research considered variants where 𝒢₁ = 𝒢₂ is the class of planar graphs, plane graphs, or planar straight-line graphs. In all three settings, we prove that the c → k augmentation problem is NP-complete when 2 ≤ c < k ≤ 5. However, the connectivity of the augmented graph G' is at most 5 if 𝒢₂ is limited to planar graphs. We initiate the study of the c → k connectivity augmentation problem for arbitrary k ∈ ℕ, where 𝒢₁ is the class of planar graphs, plane graphs, or planar straight-line graphs, and 𝒢₂ is a beyond-planar class of graphs: 𝓁-planar, 𝓁-plane topological, or 𝓁-plane geometric graphs. We obtain tight bounds on the tradeoffs between the desired connectivity k and the local crossing number 𝓁 of the augmented graph G'. We also show that our hardness results apply to this setting. The connectivity augmentation problem for triangulations is intimately related to edge flips; and the minimum augmentation problem to the flip distance between triangulations. We prove that it is NP-complete to find the minimum flip distance between a given triangulation and a 4-connected triangulation, settling an open problem posed in 2014, and present an EPTAS for this problem.

A k-page book embedding of a directed acyclic graph consists of a topological order of its vertices and a k-coloring of its edges, such that no two edges of the same color cross, that is, their endpoints do not alternate in the order. The minimum value of k for which such an embedding exists is referred to as the page number of the graph. In contrast to general directed acyclic planar graphs, which may have unbounded page number [SIAM J. Comput. 28(5), 1999], it was recently shown that directed acyclic outerplanar graphs have bounded page number. In particular, Jungeblut, Merker and Ueckerdt provided an upper bound of 24,776 on their page number [FOCS 2023: 1937-1952]. In this work, we focus on so-called monotone directed acyclic outerplanar graphs. Starting from a single edge, these graphs are constructed by iteratively connecting a new vertex to the endpoints of an existing edge on the outer face using either two incoming or two outgoing edges incident to it. These graphs have twist-number 4 [GD 2023: 135-151] (i.e., they admit a topological order in which no more than four edges pairwise cross), a property, which was leveraged by Jungeblut, Merker and Ueckerdt to show that their page number is at most 128. We lower this upper bound to 5 and we also provide a lower bound of 4. A notable consequence of our result is a significant improvement of the upper bound on the page number of general directed outerplanar graphs from 24,776 to 1,160.

A well-known conjecture, named after David W. Barnette, asserts that every 3-regular, 3-connected, bipartite, planar graph (for short, Barnette graph) is Hamiltonian. As another step towards addressing Barnette’s conjecture positively, we show that every n-vertex Barnette graph admits a subhamiltonian cycle containing 5n/6 edges, improving upon the previous bound of 2n/3. Equivalently, every Barnette graph admits a 2-page book embedding in which at least 5n/6 consecutive vertex pairs along the spine are connected by edges. As a byproduct, we present a simple proof for a known result that guarantees the existence of Hamiltonian cycles in a certain subclass of Barnette graphs.

Some of the most important open problems for linear layouts of graphs ask for the relation between a graph’s queue number and its stack number or mixed number. In such, we seek a vertex order and edge partition of G into parts with pairwise non-crossing edges (a stack) or with pairwise non-nesting edges (a queue). Allowing only stacks, only queues, or both, the minimum number of required parts is the graph’s stack number sn(G), queue number qn(G), and mixed number mn(G), respectively. Already in 1992, Heath and Rosenberg asked whether qn(G) is bounded in terms of sn(G), that is, whether stacks "can be transformed into" queues. This is equivalent to bipartite 3-stack graphs having bounded queue number (Dujmović and Wood, 2005). Recently, Alam et al. asked whether qn(G) is bounded in terms of mn(G), which we show to also be equivalent to the previous questions. We approach the problem by considering separated linear layouts of bipartite graphs. In this natural setting all vertices of one part must precede all vertices of the other part. Separated stack and queue numbers coincide, and for fixed vertex orders, graphs with bounded separated stack/queue number can be characterized and efficiently recognized, whereas the separated mixed layouts are more challenging. In this work, we thoroughly investigate the relationship between separated and non-separated, mixed and pure linear layouts.

A drawing of a graph divides the plane into topologically connected regions, called faces (or cells ). The boundary of each face is formed by vertices, crossings, and edge portions. Given a positive integer , we say that is a -real face drawing of if the boundary of each face of contains at least vertices of . Graphs that admit a -real face drawing are -real face graphs ; they have been studied so far in terms of edge density and inclusion relationships with other notable classes of nonplanar graphs that can be drawn avoiding specific crossing configurations. In this paper, we investigate the complexity of recognizing -real face graphs, that is, the complexity of testing whether a given graph is -real face, for desired values of . We study both the general unconstrained scenario and the 2-layer scenario in which the graph is bipartite, the vertices of the two partition sets lie on two distinct horizontal layers, and the edges are drawn as straight-line segments. While we prove NP-completeness results for the unconstrained scenario, we describe efficient recognition algorithms for the 2-layer setting.

We introduce the Density Formula for (topological) drawings of graphs in the plane or on the sphere, which relates the number of edges, vertices, crossings, and sizes of cells in the drawing. We demonstrate its capability by providing several applications: we prove tight upper bounds on the edge density of various beyond-planar graph classes, including so-called $k$-planar graphs with $k=1,2$, fan-crossing / fan-planar graphs, $k$-bend RAC-graphs with $k=0,1,2$, quasiplanar graphs, and $k^+$-real face graphs. In some cases ($1$-bend and $2$-bend RAC-graphs and fan-crossing / fan-planar graphs), we thereby obtain the first tight upper bounds on the edge density of the respective graph classes. In other cases, we give new streamlined and significantly shorter proofs for bounds that were already known in the literature. Thanks to the Density Formula, all of our proofs are mostly elementary counting and mostly circumvent the typical intricate case analysis found in earlier proofs. Further, in some cases (simple and non-homotopic quasiplanar graphs), our alternative proofs using the Density Formula lead to the first tight lower bound examples.

Beyond-planarity focuses on the study of geometric and topological graphs that are in some sense nearly-planar. Here, planarity is relaxed by allowing edge crossings, but only with respect to some local forbidden crossing configurations. Early research dates back to the 1960s (e.g., Avital and Hanani 1966) for extremal problems on geometric graphs, but is also related to graph drawing problems where visual clutter by edge crossings should be minimized (e.g., Huang et al. 2008) that could negatively affect the readability of the drawing. Different types of forbidden crossing configurations give rise to different families of nearly-planar graphs. Most of the literature focuses on Turán-type problems, which ask for the maximum number of edges a nearly-planar graph can have. Here, we study this problem for bipartite topological graphs, considering several types of nearly-planar graphs, i.e., 1-planar, 2-planar, fan-planar, and RAC graphs. We prove bounds on the number of edges that are tight up to small additive constants; some of them are surprising and not along the lines of the known results for non-bipartite graphs. Our findings lead to an improvement of the leading constant of the well-known Crossing Lemma for bipartite graphs, as well as to a number of interesting research questions on topological graphs.

A RAC graph is one admitting a RAC drawing, that is, a polyline drawing in which each crossing occurs at a right angle. Originally motivated by psychological studies on readability of graph layouts, RAC graphs form one of the most prominent graph classes in beyond planarity. In this work, we study a subclass of RAC graphs, called axis-parallel RAC (or apRAC, for short), that restricts the crossings to pairs of axis-parallel edge-segments. apRAC drawings combine the readability of planar drawings with the clarity of (non-planar) orthogonal drawings. We consider these graphs both with and without bends. Our contribution is as follows: (i) We study inclusion relationships between apRAC and traditional RAC graphs. (ii) We establish bounds on the edge density of apRAC graphs. (iii) We show that every graph with maximum degree 8 is 2-bend apRAC and give a linear time drawing algorithm. Some of our results on apRAC graphs also improve the state of the art for general RAC graphs. We conclude our work with a list of open questions and a discussion of a natural generalization of the apRAC model.

Abstract We investigate the queue number of posets in terms of their width, that is, the maximum number of pairwise incomparable elements. A long-standing conjecture of Heath and Pemmaraju asserts that every poset of width w has queue number at most w. The conjecture has been confirmed for posets of width $$w=2$$ w = 2 via so-called lazy linear extension. We extend and thoroughly analyze lazy linear extensions for posets of width $$w > 2$$ w > 2 . Our analysis implies an upper bound of $$(w-1)^2 +1$$ ( w - 1 ) 2 + 1 on the queue number of width-w posets, which is tight for the strategy and yields an improvement over the previously best-known bound. Further, we provide an example of a poset that requires at least $$w+1$$ w + 1 queues in every linear extension, thereby disproving the conjecture for posets of width $$w > 2$$ w > 2 .

Abstract A planar orthogonal drawing of a planar 4-graph G (i.e., a planar graph with vertex-degree at most four) is a crossing-free drawing that maps each vertex of G to a distinct point of the plane and each edge of G to a polygonal chain consisting of horizontal and vertical segments. A longstanding open question in Graph Drawing, dating back over 30 years, is whether there exists a linear-time algorithm to compute an orthogonal drawing of a plane 4-graph with the minimum number of bends. The term “plane” indicates that the input graph comes together with a planar embedding, which must be preserved by the drawing (i.e., the drawing must have the same set of faces as the input graph). In this paper we positively answer the question above for the widely-studied class of series–parallel graphs. Our linear-time algorithm is based on a characterization of the planar series–parallel graphs that admit an orthogonal drawing without bends. This characterization is given in terms of the orthogonal spirality that each type of triconnected component of the graph can take; the orthogonal spirality of a component measures how much that component is “rolled-up” in an orthogonal drawing of the graph.

Graph product structure theory expresses certain graphs as subgraphs of the strong product of much simpler graphs. In particular, an elegant formulation for the corresponding structural theorems involves the strong product of a path and of a bounded treewidth graph, and allows to lift combinatorial results for bounded treewidth graphs to graph classes for which the product structure holds, such as to planar graphs [Dujmović et al., J. ACM, 67(4), 22:1-38, 2020]. In this paper, we join the search for extensions of this powerful tool beyond planarity by considering the h-framed graphs, a graph class that includes 1-planar, optimal 2-planar, and k-map graphs (for appropriate values of h). We establish a graph product structure theorem for h-framed graphs stating that the graphs in this class are subgraphs of the strong product of a path, of a planar graph of treewidth at most 3, and of a clique of size 3⌊h2 ⌋ + ⌊h3 ⌋ - 1. This allows us to improve over the previous structural theorems for 1-planar and k-map graphs. Our results constitute significant progress over the previous bounds on the queue number, non-repetitive chromatic number, and p-centered chromatic number of these graph classes, e.g., we lower the currently best upper bound on the queue number of 1-planar graphs and k-map graphs from 115 to 82 and from ⌊332 (k + 3⌊k2 ⌋-3)⌋ to ⌊332 (3⌊k2 ⌋ + ⌊k3 ⌋ - 1)⌋, respectively. We also employ the product structure machinery to improve the current upper bounds on the twin-width of 1-planar graphs from O(1) to 80. All our structural results are constructive and yield efficient algorithms to obtain the corresponding decompositions.

Motivated by cognitive experiments providing evidence that large crossing-angles do not impair the readability of a graph drawing, RAC (Right Angle Crossing) drawings were introduced to address the problem of producing readable representations of non-planar graphs by supporting the optimal case in which all crossings form 90° angles. In this work, we make progress on the problem of finding RAC drawings of graphs of low degree. In this context, a long-standing open question asks whether all degree-3 graphs admit straight-line RAC drawings. This question has been positively answered for the Hamiltonian degree-3 graphs. We improve on this result by extending to the class of 3-edge-colorable degree-3 graphs. When each edge is allowed to have one bend, we prove that degree-4 graphs admit such RAC drawings, a result which was previously known only for degree-3 graphs. Finally, we show that 7-edge-colorable degree-7 graphs admit RAC drawings with two bends per edge. This improves over the previous result on degree-6 graphs.

Abstract We study how to place arrow heads in directed graph drawings aiming at minimizing their overlaps and avoiding intersections between arrow heads and edges. The objective is to support users to correctly and quickly recognize edge orientations, i.e. to deduce unambiguously the edge orientations. Our contribution is two‐fold: (i) We present exact and heuristic algorithms for this arrow placement problem, along with an extensive experimental analysis of these techniques; and (ii) we report on a user study aimed to understand the impact of different arrow placement strategies on performing global and local analysis tasks on directed graph layouts.

Abstract The crossing resolution of a non-planar drawing of a graph is the value of the minimum angle formed by any pair of crossing edges. Recent experiments suggest that the larger the crossing resolution is, the easier it is to read and interpret a drawing of a graph. However, maximizing the crossing resolution turns out to be an NP-hard problem in general, and only heuristic algorithms are known that are mainly based on appropriately adjusting force-directed algorithms. In this paper, we propose a new heuristic algorithm for the crossing resolution maximization problem and we experimentally compare it against the known approaches from the literature. Our experimental evaluation indicates that the new heuristic produces drawings with better crossing resolution, but this comes at the cost of slightly higher edge-length ratio, especially when the input graph is large.

We present new bounds for the required area of Right Angle Crossing (RAC) drawings for complete graphs, i.e. drawings where any two crossing edges are perpendicular to each other. First, we improve upon results by Didimo et al. [Walter Didimo et al., 2011] and Di Giacomo et al. [Emilio Di Giacomo et al., 2011] by showing how to compute a RAC drawing with three bends per edge in cubic area. We also show that quadratic area can be achieved when allowing eight bends per edge in general or with three bends per edge for p-partite graphs. As a counterpart, we prove that in general quadratic area is not sufficient for RAC drawings with three bends per edge.

In a fan-planar drawing of a graph an edge can cross only edges with a common end-vertex. In this paper, we study fan-planar drawings that use h (horizontal) layers and are proper, i.e., edges connect adjacent layers. We show that if the embedding of the graph is fixed, then testing the existence of such drawings is fixed-parameter tractable in h, via a reduction to a similar result for planar graphs by Dujmović et al. If the embedding is not fixed, then we give partial results for h = 2: It was already known how to test the existence of fan-planar proper 2-layer drawings for 2-connected graphs, and we show here how to test this for trees. Along the way, we exhibit other interesting results for graphs with a fan-planar proper h-layer drawing; in particular we bound their pathwidth and show that they have a bar-1-visibility representation.

Abstract A queue layout of a graph G consists of a linear order of the vertices of G and a partition of the edges of G into queues , so that no two independent edges of the same queue are nested. The queue number of graph G is defined as the minimum number of queues required by any queue layout of G . In this paper, we continue the study of the queue number of planar 3-trees, which form a well-studied subclass of planar graphs. Prior to this work, it was known that the queue number of planar 3-trees is at most seven. In this work, we improve this upper bound to five. We also show that there exist planar 3-trees whose queue number is at least four. Notably, this is the first example of a planar graph with queue number greater than three.

Beyond-planarity focuses on combinatorial properties of classes of non-planar graphs that allow for representations satisfying certain local geometric or topological constraints on their edge crossings. Beside the study of a specific graph class for its maximum edge density, another parameter that is often considered in the literature is the size of the largest complete or complete bipartite graph belonging to it. Overcoming the limitations of standard combinatorial arguments, we present a technique to systematically generate all non-isomorphic topological representations of complete and complete bipartite graphs, taking into account the constraints of the specific class. As a proof of concept, we apply our technique to various beyond-planarity classes and achieve new tight bounds for the aforementioned parameter.

A graph is k-planar if it can be drawn in the plane such that no edge is crossed more than k times. While for k=1, optimal 1-planar graphs, i.e., those with n vertices and exactly 4n-8 edges, have been completely characterized, this has not been the case for k > 1. For k=2,3 and 4, upper bounds on the edge density have been developed for the case of simple graphs by Pach and Tóth, Pach et al. and Ackerman, which have been used to improve the well-known "Crossing Lemma". Recently, we proved that these bounds also apply to non-simple 2- and 3-planar graphs without homotopic parallel edges and self-loops. In this paper, we completely characterize optimal 2- and 3-planar graphs, i.e., those that achieve the aforementioned upper bounds. We prove that they have a remarkably simple regular structure, although they might be non-simple. The new characterization allows us to develop notable insights concerning new inclusion relationships with other graph classes.

Packing graphs is a combinatorial problem where several given graphs are being mapped into a common host graph such that every edge is used at most once. In the planar tree packing problem we are given two trees T1 and T2 on n vertices and have to find a planar graph on n vertices that is the edge-disjoint union of T1 and T2. A clear exception that must be made is the star which cannot be packed together with any other tree. But according to a conjecture of Garcia et al. from 1997 this is the only exception, and all other pairs of trees admit a planar packing. Previous results addressed various special cases, such as a tree and a spider tree, a tree and a caterpillar, two trees of diameter four, two isomorphic trees, and trees of maximum degree three. Here we settle the conjecture in the affirmative and prove its general form, thus making it the planar tree packing theorem. The proof is constructive and provides a polynomial time algorithm to obtain a packing for two given nonstar trees.

MOTIVATION: Gene set analysis has revolutionized the interpretation of high-throughput transcriptomic data. Nowadays, with comprehensive studies that measure multiple -omics from the same sample, powerful tools for the integrative analysis of multi-omics datasets are required. RESULTS: Here, we present GeneTrail2, a web service allowing the integrated analysis of transcriptomic, miRNomic, genomic and proteomic datasets. It offers multiple statistical tests, a large number of predefined reference sets, as well as a comprehensive collection of biological categories and enables direct comparisons between the computed results. We used GeneTrail2 to explore pathogenic mechanisms of Wilms tumors. We not only succeeded in revealing signaling cascades that may contribute to the malignancy of blastemal subtype tumors but also identified potential biomarkers for nephroblastoma with adverse prognosis. The presented use-case demonstrates that GeneTrail2 is well equipped for the integrative analysis of comprehensive -omics data and may help to shed light on complex pathogenic mechanisms in cancer and other diseases. AVAILABILITY AND IMPLEMENTATION: GeneTrail2 can be freely accessed under https://genetrail2.bioinf.uni-sb.de CONTACT: : [email protected] SUPPLEMENTARY INFORMATION: Supplementary data are available at Bioinformatics online.

Static drawings of biological pathways are still an important research tool for biologists. Gerhard Michal created his seminal drawings of metabolic networks in the 1960s and thus defined canonical representations of some key pathways. The Kyoto Encyclopedia of Genes and Genomes (KEGG) provides the most popular static drawings of biological networks of different types, used in a huge number of publications. These drawings are so widely known that they are immediately recognizable to most biologists. This enables collaborative work and simplifies the communication of analysis results. Automatic layout of these pathway maps is complicated by the fact that the information available from KEGG does not contain the entire layout information of the reference maps. Here we present a fully automated algorithm for interactive KEGG layout construction. The algorithm conserves the original KEGG layout to the extent possible while improving readability by removing unnecessary elements (in organism-specific maps). Multiple pathway maps can be laid out simultaneously to facilitate the navigation of larger networks. The algorithm supports the hierarchical layout of sub networks and thus supports interactive exploration of large datasets.

The display of data related to graphical objects on a map is a well studied problem in cartography and several approaches have been published. Adapting the idea of boundary labeling using a focus region, we face the problem of emphasizing additional information and labels for objects within a focus region even when the region might be moving. We propose four different approaches that support effective solutions in various ways, and discuss advantages and drawbacks. Our algorithms regard the dynamic nature of the focus region to place the labels and preserve the mental map of the analyzed drawing. We demonstrate our methods by applying them to biological networks.

UNLABELLED: The deregulation of biochemical pathways plays a central role in many diseases like cancer or Parkinsons's disease. In silico tools for calculating these deregulated pathways may help to gain new insights into pathogenic mechanisms and may open novel avenues for therapy stratification in the sense of personalized medicine. Here, we present NetworkTrail, a web service for the detection of deregulated pathways and subgraphs in biological networks. NetworkTrail uses a state-of-the-art integer linear programming-based approach for this task and offers interfaces to the Biological Network Analyzer (BiNA) and Cytoscape Web for visualizing the resulting subnetworks. By providing an accessible interface to otherwise hard-to-use command line tools, the new web service enables non-experts to quickly and reliably carry out this type of network analyses. AVAILABILITY AND IMPLEMENTATION: NetworkTrail is a JavaServer Pages-based web service. The algorithm for finding deregulated subnetworks has been implemented in C++. NetworkTrail is available at http://networktrail.bioinf.uni-sb.de/.

In a rectilinear dual of a planar graph vertices are represented by simple rectilinear polygons, while edges are represented by side-contact between the corresponding polygons. A rectilinear dual is called a cartogram if the area of each region is equal to a pre-specified weight.

BACKGROUND: Expression profiling provides new insights into regulatory and metabolic processes and in particular into pathogenic mechanisms associated with diseases. Besides genes, non-coding transcripts as microRNAs (miRNAs) gained increasing relevance in the last decade. To understand the regulatory processes of miRNAs on genes, integrative computer-aided approaches are essential, especially in the light of complex human diseases as cancer. RESULTS: Here, we present miRTrail, an integrative tool that allows for performing comprehensive analyses of interactions of genes and miRNAs based on expression profiles. The integrated analysis of mRNA and miRNA data should generate more robust and reliable results on deregulated pathogenic processes and may also offer novel insights into the regulatory interactions between miRNAs and genes. Our web-server excels in carrying out gene sets analysis, analysis of miRNA sets as well as the combination of both in a systems biology approach. To this end, miRTrail integrates information on 20.000 genes, almost 1.000 miRNAs, and roughly 280.000 putative interactions, for Homo sapiens and accordingly for Mus musculus and Danio rerio. The well-established, classical Chi-squared test is one of the central techniques of our tool for the joint consideration of miRNAs and their targets. For interactively visualizing obtained results, it relies on the network analyzers and viewers BiNA or Cytoscape-web, also enabling direct access to relevant literature. We demonstrated the potential of miRTrail by applying our tool to mRNA and miRNA data of malignant melanoma. MiRTrail identified several deregulated miRNAs that target deregulated mRNAs including miRNAs hsa-miR-23b and hsa-miR-223, which target the highest numbers of deregulated mRNAs and regulate the pathway "basal cell carcinoma". In addition, both miRNAs target genes like PTCH1 and RASA1 that are involved in many oncogenic processes. CONCLUSIONS: The application on melanoma samples demonstrates that the miRTrail platform may open avenues for investigating the regulatory interactions between genes and miRNAs for a wide range of human diseases. Moreover, miRTrail cannot only be applied to microarray based expression profiles, but also to NGS-based transcriptomic data. The program is freely available as web-server at mirtrail.bioinf.uni-sb.de.

Boundary labeling is a relatively new labeling method. It can be useful in automating the production of technical drawings and medical maps, where it is common to explain certain parts of the drawing with text labels, arranged on its boundary so that other parts of the drawing are not obscured. In boundary labeling, we are given a rectangle R which encloses a set of n sites. Each site si is associated with an axis-parallel rectangular label li. The labels must be placed in distinct positions on the boundary of R and to be connected to their corresponding sites with polygonal lines, called leaders, so that the labels are pairwise disjoint and the leaders do not intersect each other. In this paper, we study a version of the boundary labeling problem where the sites can “float ” within a polygonal region. We present a polynomial time algorithm that produces a labeling of minimum total leader length for labels of uniform size placed in fixed positions on the boundary of R.

MOTIVATION: Deregulated signaling cascades are known to play a crucial role in many pathogenic processes, among them are tumor initiation and progression. In the recent past, modern experimental techniques that allow for measuring the amount of mRNA transcripts of almost all known human genes in a tissue or even in a single cell have opened new avenues for studying the activity of the signaling cascades and for understanding the information flow in the networks. RESULTS: We present a novel dynamic programming algorithm for detecting deregulated signaling cascades. The so-called FiDePa (Finding Deregulated Paths) algorithm interprets differences in the expression profiles of tumor and normal tissues. It relies on the well-known gene set enrichment analysis (GSEA) and efficiently detects all paths in a given regulatory or signaling network that are significantly enriched with differentially expressed genes or proteins. Since our algorithm allows for comparing a single tumor expression profile with the control group, it facilitates the detection of specific regulatory features of a tumor that may help to optimize tumor therapy. To demonstrate the capabilities of our algorithm, we analyzed a glioma expression dataset with respect to a directed graph that combined the regulatory networks of the KEGG and TRANSPATH database. The resulting glioma consensus network that encompasses all detected deregulated paths contained many genes and pathways that are known to be key players in glioma or cancer-related pathogenic processes. Moreover, we were able to correlate clinically relevant features like necrosis or metastasis with the detected paths. AVAILABILITY: C++ source code is freely available, BiNA can be downloaded from http://www.bnplusplus.org/. CONTACT: [email protected] SUPPLEMENTARY INFORMATION: Supplementary data are available at Bioinformatics online.

BACKGROUND: High-throughput methods that allow for measuring the expression of thousands of genes or proteins simultaneously have opened new avenues for studying biochemical processes. While the noisiness of the data necessitates an extensive pre-processing of the raw data, the high dimensionality requires effective statistical analysis methods that facilitate the identification of crucial biological features and relations. For these reasons, the evaluation and interpretation of expression data is a complex, labor-intensive multi-step process. While a variety of tools for normalizing, analysing, or visualizing expression profiles has been developed in the last years, most of these tools offer only functionality for accomplishing certain steps of the evaluation pipeline. RESULTS: Here, we present a web-based toolbox that provides rich functionality for all steps of the evaluation pipeline. Our tool GeneTrailExpress offers besides standard normalization procedures powerful statistical analysis methods for studying a large variety of biological categories and pathways. Furthermore, an integrated graph visualization tool, BiNA, enables the user to draw the relevant biological pathways applying cutting-edge graph-layout algorithms. CONCLUSION: Our gene expression toolbox with its interactive visualization of the pathways and the expression values projected onto the nodes will simplify the analysis and interpretation of biochemical pathways considerably.

Clustering is often formulated as a discrete optimization problem. The objective is to find, among all partitions of the data set, the best one according to some quality measure. However, in the statistical setting where we assume that the finite data set has been sampled from some underlying space, the goal is not to find the best partition of the given sample, but to approximate the true partition of the under- lying space. We argue that the discrete optimization approach usually does not achieve this goal. As an alternative, we suggest the paradigm of “nearest neighbor clustering”. Instead of selecting the best out of all partitions of the sample, it only considers partitions in some restricted function class. Using tools from statistical learning theory we prove that nearest neighbor clustering is statistically consis- tent. Moreover, its worst case complexity is polynomial by construction, and it can be implemented with small average case complexity using branch and bound.

BACKGROUND: Technological advances in high-throughput techniques and efficient data acquisition methods have resulted in a massive amount of life science data. The data is stored in numerous databases that have been established over the last decades and are essential resources for scientists nowadays. However, the diversity of the databases and the underlying data models make it difficult to combine this information for solving complex problems in systems biology. Currently, researchers typically have to browse several, often highly focused, databases to obtain the required information. Hence, there is a pressing need for more efficient systems for integrating, analyzing, and interpreting these data. The standardization and virtual consolidation of the databases is a major challenge resulting in a unified access to a variety of data sources. DESCRIPTION: We present the Biochemical Network Database (BNDB), a powerful relational database platform, allowing a complete semantic integration of an extensive collection of external databases. BNDB is built upon a comprehensive and extensible object model called BioCore, which is powerful enough to model most known biochemical processes and at the same time easily extensible to be adapted to new biological concepts. Besides a web interface for the search and curation of the data, a Java-based viewer (BiNA) provides a powerful platform-independent visualization and navigation of the data. BiNA uses sophisticated graph layout algorithms for an interactive visualization and navigation of BNDB. CONCLUSION: BNDB allows a simple, unified access to a variety of external data sources. Its tight integration with the biochemical network library BN++ offers the possibility for import, integration, analysis, and visualization of the data. BNDB is freely accessible at http://www.bndb.org.

While the evolution of biological networks can be modeled sensefully as a series of mutation and selection, evolution of other networks such as the social network in a city or the network of streets in a country is not determined by selection since there is no alternative network with which these singular networks have to compete. Nonetheless, these singular networks do evolve due to dynamic changes of vertices and edges. In this article we present a formal, analyzable framework for the evolution of singular networks. We show that the careful design of adaptation rules can lead to the emergence of network topologies with satisfying performance in polynomial time while other adaptation rules yield exponential runtime. We further show by example how the framework could be applied to some ad-hoc communication scenarios.

BACKGROUND: We present a complete re-implementation of the segment-based approach to multiple protein alignment that contains a number of improvements compared to the previous version 2.2 of DIALIGN. This previous version is superior to Needleman-Wunsch-based multi-alignment programs on locally related sequence sets. However, it is often outperformed by these methods on data sets with global but weak similarity at the primary-sequence level. RESULTS: In the present paper, we discuss strengths and weaknesses of DIALIGN in view of the underlying objective function. Based on these results, we propose several heuristics to improve the segment-based alignment approach. For pairwise alignment, we implemented a fragment-chaining algorithm that favours chains of low-scoring local alignments over isolated high-scoring fragments. For multiple alignment, we use an improved greedy procedure that is less sensitive to spurious local sequence similarities. To evaluate our method on globally related protein families, we used the well-known database BAliBASE. For benchmarking tests on locally related sequences, we created a new reference database called IRMBASE which consists of simulated conserved motifs implanted into non-related random sequences. CONCLUSION: On BAliBASE, our new program performs significantly better than the previous version of DIALIGN and is comparable to the standard global aligner CLUSTAL W, though it is outperformed by some newly developed programs that focus on global alignment. On the locally related test sets in IRMBASE, our method outperforms all other programs that we evaluated.

BACKGROUND: Parallel computing is frequently used to speed up computationally expensive tasks in Bioinformatics. RESULTS: Herein, a parallel version of the multi-alignment program DIALIGN is introduced. We propose two ways of dividing the program into independent sub-routines that can be run on different processors: (a) pair-wise sequence alignments that are used as a first step to multiple alignment account for most of the CPU time in DIALIGN. Since alignments of different sequence pairs are completely independent of each other, they can be distributed to multiple processors without any effect on the resulting output alignments. (b) For alignments of large genomic sequences, we use a heuristics by splitting up sequences into sub-sequences based on a previously introduced anchored alignment procedure. For our test sequences, this combined approach reduces the program running time of DIALIGN by up to 97%. CONCLUSIONS: By distributing sub-routines to multiple processors, the running time of DIALIGN can be crucially improved. With these improvements, it is possible to apply the program in large-scale genomics and proteomics projects that were previously beyond its scope.

This paper presents new upper bounds for channel routing of multiterminal nets, which answers the long-standing open question whether or not multiterminal problems really require channels two times wider than 2-terminal problems. We transform any multiterminal problem of density d into a so-called extended simple channel routing problem (ESCRP) of density 3d /2 + O√ d log d) . We then descibe routing algorithms for solving ESCRPs in three different models. The channel width w is ≤ 3d/2 +O(√d log d) in the knock-knee and unit-vertical-overlap models, and w ≤ 3d/2 + O√d log d) + O(ƒ) in the Manhattan model, where f is the flux of the problem. In all three cases, we improve the best-known upper bounds.

The paper considers the problem of finding edge-disjoint paths between pairs of vertices in a finite grid graph. The homotopy class for each path to be routed is prespecified. A very fast algorithm that guarantees to find a solution for any solvable homotopic routing problem is given.

This paper presents the problem of drawing a graph in the plane so that edges appear as straight lines and the minimum angle formed by any pair of incident edges is maximized. The resolution of a layout is defined to be the size of the minimum angle formed by incident edges of the graph, and the resolution of a graph to be the maximum resolution of any layout of the graph. The resolution R of a graph is characterized in terms of the maximum node degree d of the graph by proving that $\Omega (\frac{1}{{d^2 }}) \leqslant R \leqslant \frac{{2\pi }}{d}$ for any graph. Moreover, it is proved that $R = \Theta (\frac{1}{d})$ for many graphs including planar graphs, complete graphs, hypercubes, multidimensional meshes and tori, and other special networks. It is also shown that the problem of deciding if $R = \frac{{2\pi }}{d}$ for a graph is NP-hard for $d = 4$, and by using a counting argument that $R = O(\frac{{\log d}}{{d^2 }})$ for many graphs.

Article Matching the bisection bound for routing and sorting on the mesh Share on Authors: Michael Kaufmann View Profile , Sanguthevar Rajasekaran View Profile , Jop F. Sibeyn View Profile Authors Info & Claims SPAA '92: Proceedings of the fourth annual ACM symposium on Parallel algorithms and architecturesJune 1992 Pages 31–40https://doi.org/10.1145/140901.140905Published:01 June 1992 30citation197DownloadsMetricsTotal Citations30Total Downloads197Last 12 Months1Last 6 weeks0 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 SiteGet Access

We study rigid motions of a rectangle amidst polygonal obstacles. The best known algorithms for this problem have running time Ω(n2) where n is the number of obstacle corners. We introduce the tightness of a motion planning problem as a measure of the difficulty of a planning problem in an intuitive sense and describe an algorithm with running time ο((a/b · 1/ε crit + 1)n(log n)2), where a ≥ b are the lengths of the sides of a rectangle and εcrit is the tightness of the problem. We show further that the complexity (= number of vertices) of the boundary of n bow-ties (c.f. Figure 1.1) is Ο(n). Similar results for the union of other simple geometric figures such as triangles and wedges are also presented.

Art gallery problems which have been extensively studied over the last decade ask how to station a small (minimum) set of guards in a polygon such that every point of the polygon is watched by at least one guard. The graph-theoretic formulation and solution to the gallery problem for polygons in standard form is given. A complexity analysis is carried out, and open problems are discussed.>

The problem of drawing a graph in the plane so that edges appear as straight lines and the minimum angle formed by any pair of incident edges is maximized is studied. The resolution of a layout is defined to be the size of the minimum angle formed by incident edges of the graph, and the resolution of a graph is defined to be the maximum resolution of any layout of the graph. The resolution R of a graph is characterized in terms of the maximum node degree d of the graph by proving that Omega (1/d/sup 2/)>

An algorithm for the problem of routing two-terminal nets in a convex grid is presented. A convex grid is a subset R of the planar rectangular grid without any nontrivial holes, i.e. every finite face has exactly four incident vertices, so that every vertical and horizontal line crosses the boundary of the grid at most twice. A net is a pair of vertices of nonmaximal degree on the boundary of A. A solution of the problem is a set of edge-disjoint paths, one for each net. The vertices of a net are called its terminals. The algorithm is based on a theorem of H. Okamura and P.D. Seymour (J. Combinatorial Theory, vol.31, series B., p.75-81, 1981) on multicommodity flows in a planar graphs. The algorithm is very simple, uses only one simple data structure and works in time O(n) on a more general routing region.>

We give an Ο(n3·log n) time and Ο(n3) space algorithm for the continuous homotopic one layer routing problem. The main contribution is an extension of the sweep paradigm to a universal cover space of the plane.

This paper presents a new algorithm for channel routing of multiterminal nets. We first transform any multiterminal problem of density d to a socalled extended simple channel routing problem (ESCRP ) of density 3d/2+O(√dlog d), which will then be solved with channel width w ≤3d/2+O(√dlog d) in the knock-knee model. The same strategy can be used for routing in the other two models: The channel width is w ≤ 3d/2+O(√dlog d)+O(f) in the Manhattan model, where f is the flux of the problem, and w ≤ 3d/2+O(√dlogd) in the unit-vertical-overlap model. In all three cases we improve the best known upper bounds.