101 research outputs found
Graph Algorihms and Applications 3
No full textThis book contains Volume 6 of the Journal of Graph Algorithms and Applications (JGAA). JGAA is a peer-reviewed scientific journal devoted to the publication of high-quality research papers on the analysis, design, implementation, and applications of graph algorithms. Areas of interest include computational biology, computational geometry, computer graphics, computer-aided design, computer and interconnection networks, constraint systems, databases, graph drawing, graph embedding and layout, knowledge representation, multimedia, software engineering, telecommunications networks, user interfaces and visualization, and VLSI circuit design.
Graph Algorithms and Applications 3 presents contributions from prominent authors and includes selected papers from the Symposium on Graph Drawing (1999 and 2000). All papers in the book have extensive diagrams and offer a unique treatment of graph algorithms focusing on the important applications.
Contents:
* Triangle-Free Planar Graphs and Segment Intersection Graphs (N de Castro et al.)
* Traversing Directed Eulerian Mazes (S Bhatt et al.)
* A Fast Multi-Scale Method for Drawing Large Graphs (D Harel & Y Koren)
* GRIP: Graph Drawing with Intelligent Placement (P Gajer & S G Kobourov)
* Graph Drawing in Motion (C Friedrich & P Eades)
* A 6-Regular Torus Graph Family with Applications to Cellular and Interconnection Networks (M Iridon & D W Matula)
* and other paper
Graph Algorithms and Applications 2
No full textThis book contains Volumes 4 and 5 of the Journal of Graph Algorithms and Applications (JGAA). The first book of this series, Graph Algorithms and Applications 1, published in March 2002, contains Volumes 1–3 of JGAA.
JGAA is a peer-reviewed scientific journal devoted to the publication of high-quality research papers on the analysis, design, implementation, and applications of graph algorithms. Areas of interest include computational biology, computational geometry, computer graphics, computer-aided design, computer and interconnection networks, constraint systems, databases, graph drawing, graph embedding and layout, knowledge representation, multimedia, software engineering, telecommunications networks, user interfaces and visualization, and VLSI circuit design. The journal is supported by distinguished advisory and editorial boards, has high scientific standards, and takes advantage of current electronic document technology. The electronic version of JGAA is available on the Web at http://jgaa.info/.
Graph Algorithms and Applications 2 presents contributions from prominent authors and includes selected papers from the Dagstuhl Seminar on Graph Algorithms and Applications and the Symposium on Graph Drawing in 1998. All papers in the book have extensive diagrams and offer a unique treatment of graph algorithms focusing on the important applications.
Contents:
* Approximations of Weighted Independent Set and Hereditary Subset Problems (M M Halldórsson)
* Approximation Algorithms for Some Graph Partitioning Problems (G He et al.)
* Geometric Thickness of Complete Graphs (M B Dillencourt et al.)
* Techniques for the Refinement of Orthogonal Graph Drawings (J M Six et al.)
* Navigating Clustered Graphs Using Force-Directed Methods (P Eades & M L Huang)
* Clustering in Trees: Optimizing Cluster Sizes and Number of Subtrees (S E Hambrusch et al.)
* Planarizing Graphs — A Survey and Annotated Bibliography (A Liebers)
* Fully Dynamic 3-Dimensional Orthogonal Graph Drawing (M Closson et al.)
* 1-Bend 3-D Orthogonal Box-Drawings: Two Open Problems Solved (T Biedl)
* Computing an Optimal Orientation of a Balanced Decomposition Tree for Linear Arrangement Problems (R Bar-Yehuda et al.)
* New Bounds for Oblivious Mesh Routing (K Iwama et al.)
* Connectivity of Planar Graphs (H de Fraysseix & P O de Mendez)
* and other paper
Graph ALgorithms and Applications 4
No full textThis book contains Volume 7 of the Journal of Graph Algorithms and Applications (JGAA). JGAA is a peer-reviewed scientific journal devoted to the publication of high-quality research papers on the analysis, design, implementation, and applications of graph algorithms. Areas of interest include computational biology, computational geometry, computer graphics, computer-aided design, computer and interconnection networks, constraint systems, databases, graph drawing, graph embedding and layout, knowledge representation, multimedia, software engineering, telecommunications networks, user interfaces and visualization, and VLSI circuit design.
Graph Algorithms and Applications 4 presents contributions from prominent authors and includes selected papers from (a) the Seventh International Workshop on Algorithms and Data Structures (WADS 2001) and (b) the 2001 Symposium on Graph Drawing (GD 2001). All papers in the book have extensive diagrams and offer a unique treatment of graph algorithms focusing on the important applications.
Contents:
* Statistical Analysis of Algorithms: A Case Study of Market-Clearing Mechanisms in the Power Industry (C Barrett et al.)
* On External-Memory Planar Depth First Search (L Arge et al.)
* Finding Shortest Paths with Computational Geometry (P-S Loh)
* Polar Coordinate Drawing of Planar Graphs with Good Angular Resolution (C Duncan & S Kobourov)
* and other paper
Molecular characterization of an analphoid supernumerary marker chromosome derived from 18q22.1➔qter in prenatal diagnosis: a case report
No full textBACKGROUND: Small supernumerary marker chromosomes (sSMC) occur in 0.072% of unselected cases of prenatal diagnoses, and their molecular cytogenetic characterization is required to establish a reliable karyotype-phenotype correlation. A small group of sSMC are C-band-negative and devoid of alpha-satellite DNA. We report the molecular cytogenetic characterization of a de novo analphoid sSMC derived from 18q22.1-->qter in cultured amniocytes. RESULTS: We identified an analphoid sSMC in cultured amniocytes during a prenatal diagnosis performed because of advanced maternal age. GTG-banding revealed an sSMC in all metaphases. FISH experiments with a probe specific for the chromosome 18 centromere, and C-banding revealed neither alphoid sequences nor C-banding-positive satellite DNA thereby suggesting the presence of a neocentromere. To characterize the marker in greater detail, we carried out additional FISH experiments with a set of appropriate BAC clones. The pattern of the FISH signals indicated a symmetrical organization of the marker, the breakpoint likely representing the centromere of an inverted duplicated chromosome that results in tetrasomy of 18q22.1-->qter. The karyotype after molecular cytogenetic investigations was interpreted as follows: 47,XY,+inv dup(18)(qter-->q22.1::q22.1-->neo-->qter). CONCLUSION: Our case is the first report, in the prenatal diagnosis setting, of a de novo analphoid marker chromosome originating from the long arm of chromosome 18, and the second report of a neocentromere formation at 18q22.1
Planar drawings of fixed-mobile bigraphs
No full textA fixed-mobile bigraph G is a bipartite graph such that the vertices of one partition set are given with fixed positions in the plane and the mobile vertices of the other partition, together with the edges, must be added to the drawing without any restriction on their positions. We assume that G is planar and study the problem of finding a planar straight-line drawing of G. We show that deciding whether G admits such a drawing is NP-hard in the general case. Under the assumption that each mobile vertex is placed in the convex hull of its neighbors, we are able to prove that the problem is also in NP. Moreover, if the intersection graph of these convex hulls is a path, a cycle or, more generally, a cactus, the problem is polynomial-time solvable through a dynamic programming approach. Finally, we describe linear-time testing algorithms when the fixed vertices are collinear or when they lie on a finite set of horizontal levels (lines) and no edge can intersect a level except at its fixed vertex
- …
