190 research outputs found
On the embedding phase of the Hopcroft and Tarjan planarity testing algorithm
No full textWe give a detailed description of the embedding phase of the Hopcroft and Tarjan planarity testing algorithm. The embedding phase runs in linear time. An implementation based on this paper can be found in [Mehlhorn-Mutzel-Naeher-94]
On the Embedding Phase of the Hopcroft and Tarjan Planarity Testing Algorithm
No full textWe give a detailed description of the embedding phase of the Hopcroft and Tarjan planarity testing algorithm. The embedding phase runs in linear time. An implementation based on this paper can be found in [Mehlhorn, Mutzel, Näher, 1993]
Selected Open Problems in Graph Drawing
No full textIn this manuscript, we present several challenging and interesting open problems in graph drawing. The goal of the listing in this paper is to stimulate future research in graph drawing
An algorithmic framework for the exact solution of the prize-collecting Steiner tree problem
No full textSolving the Prize-Collecting Steiner Tree Problem to Optimality
No full textThe Prize-Collecting Steiner Tree Problem (PCST) on a graph with edge costs and vertex profits asks for a subtree minimizing the sum of the total cost of all edges in the subtree plus the total profit of all vertices not contained in the subtree. PCST appears frequently in the design of utility networks where profit generating customers and the network connecting them have to be chosen in the most profitable way. Our mai
Level Planarity Testing in Linear Time
No full textIn a leveled directed acyclic graph G = (V,E) the vertex set V is partitioned into k <= |V| levels V1,V2,...,Vk such that for each edge (u,v) in E with u in Vi and v in Vj we have i < j. The level planarity testing problem is to decide if G can be drawn in the plane such that for each level Vi, all v in Vi are drawn on the line li = {(x,k-i) | x in R}, the edges are drawn monotone with respect to the vertical direction, and no edges intersect except at their end vertices. If G has a single source, the test can be performed in O(|V|) time by an algorithm of Di Battista and Nardelli [Hierarchies and planarity theory. IEEE Trans. Systems Man Cybernet. 18 (1988), no. 6, 1035--1046] that uses the PQ-tree data structure introduced by Booth and Lueker [Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms. J. Comput. System Sci. 13 (1976), no. 3, 335--379].
PQ-trees have also been proposed by Heath and Pemmaraju (1996a,1996b) to test level planarity of leveled directed acyclic graphs with several sources and sinks. It has been shown in Jünger, Leipert and Mutzel (1997) that this algorithm is not correct in the sense that it does not state correctly level planarity of every level planar graph. In this paper, we present a correct linear time level planarity testing algorithm that is based on two main new techniques that replace the incorrect crucial parts of the algorithm of Heath and Pemmaraju (1996a,1996b)
Collisional energy transfer of highly vibrationally excited toluene and pyrazine: Transition probabilities and relaxation pathways from KCSI experiments and trajectory calculations.
No full textNew experimental results for the collisional energy transfer of highly vibrationally excited toluene and pyrazine employing the method of "kinetically controlled selective ionization (KCSI)" are presented. By means of a master equation approach we determine complete and detailed collisional transition probabilities P(E',E) for energies up to 50 000 cm(-1). The same monoexponential representation P(E',E) proportional to exp[ - ((E - E')/alpha (1)(E))(Y)] (for E' less than or equal to E) with a parametric exponent Y in the argument and linearly energy dependent alpha (1)(E) = C-0 + C1E successfully used in our earlier investigation [T. Lenzer, K. Luther, K. Reihs and A. C. Symonds, J. Chem. Phys., 2000, 112, 4090] can reproduce the toluene and pyrazine results for the whole range of bath gases studied. The parameters Y, C-0 and C-1 of P(E',E) show a smooth increase with the size of the collider. An approximately linear energy dependence of the first moment of energy transfer [DeltaE] is observed for all bath gases. Literature data from infrared fluorescence (IRF) experiments in general show significantly smaller - [DeltaE] values outside the uncertainty limits of the KCSI results. It is shown that this can mainly be traced back to the critical dependence of the IRF data on small uncertainties in the calibration curve. Some of the trends with respect to the energy transfer efficiencies of different colliders observed in the KCSI experiments are easily rationalized on the basis of accompanying trajectory calculations on the deactivation of highly vibrationally excited pyrazine by n-propane and CO2. The negligible influence of the V-V relaxation channel in the pyrazine + CO2 system observed in earlier IR diode laser studies is confirmed
An Alternative Method to Crossing Minimization on Hierarchical Graphs (extended abstract)
No full textA common method for drawing directed graphs is, as a first step, to partition the vertices into a set of k levels and then, as a second step, to permute the vertices within the levels such that number of crossings is minimized. We suggest an alternative method for second step, namely, removing the minimal number of edges such that the resulting graph is k-level planar. For the final diagram the removed edges are reinserted into a k-level planar drawing. Hence, instead of considering the k-level crossing minimization problem, we suggest solving the k-level planarization problem. In this paper we adress the case k=2. First, we give a motivation for our approach. Then, we adress the problem of extracting a 2-level planar subgraph of maximum weight in a given 2-level graph. This problem is np-hard. Based on characterization of 2-level planar graphs, we give an integer linear programming formulation for the 2-level planarization problem. Moreover, we define and investigate the polytope 2LPS(G) associated with the set of all 2-level planar subgraphs of a given 2-level graph G. We will see that this polytope has full dimensionand and that the inqualities occuring in the integer linear description are facet-defining for 2LPS(G). The inqualities in the integer linear programming formulation can be separated in polynomial time, hence they can be used efficiently in a cutting plane method for solving practical instances of the 2-level planarization problem. Furthermore, we derive new inqualities that substantially improve the quality of the obtained solution. We report on first computational results
- …
