Search

Your search keyword '"triconnected components"' showing total 8 results
Start Over Descriptor "triconnected components"
8 results on '"triconnected components"'

1. 2.5-Connectivity: Unique Components, Critical Graphs, and Applications

Author

Heinrich, Irene, Heller, Till, Schmidt, Eva, Streicher, Manuel, Goos, Gerhard, Founding Editor, Hartmanis, Juris, Founding Editor, Bertino, Elisa, Editorial Board Member, Gao, Wen, Editorial Board Member, Steffen, Bernhard, Editorial Board Member, Woeginger, Gerhard, Editorial Board Member, Yung, Moti, Editorial Board Member, Adler, Isolde, editor, and Müller, Haiko, editor

Published
2020
Full Text
View/download PDF

2. Faster Network Algorithms Based on Graph Decomposition

Author

Kashyop, Manas Jyoti, Nagayama, Tsunehiko, Sadakane, Kunihiko, Hutchison, David, Series editor, Kanade, Takeo, Series editor, Kittler, Josef, Series editor, Kleinberg, Jon M., Series editor, Mattern, Friedemann, Series editor, Mitchell, John C., Series editor, Naor, Moni, Series editor, Pandu Rangan, C., Series editor, Steffen, Bernhard, Series editor, Terzopoulos, Demetri, Series editor, Tygar, Doug, Series editor, Weikum, Gerhard, Series editor, Rahman, M. Sohel, editor, Sung, Wing-Kin, editor, and Uehara, Ryuhei, editor

Published
2018
Full Text
View/download PDF

3. Testing Full Outer-2-planarity in Linear Time

Author

Hong, Seok-Hee, Nagamochi, Hiroshi, Hutchison, David, Series editor, Kanade, Takeo, Series editor, Kittler, Josef, Series editor, Kleinberg, Jon M., Series editor, Mattern, Friedemann, Series editor, Mitchell, John C., Series editor, Naor, Moni, Series editor, Pandu Rangan, C., Series editor, Steffen, Bernhard, Series editor, Terzopoulos, Demetri, Series editor, Tygar, Doug, Series editor, Weikum, Gerhard, Series editor, and Mayr, Ernst W., editor

Published
2016
Full Text
View/download PDF

5. Finding a Minimum-depth Embedding of a Planar Graph in O( n) Time.

Author

Angelini, Patrizio, Battista, Giuseppe, and Patrignani, Maurizio

Subjects
*MOTHERBOARDS, *COMPUTER algorithms, *GRAPH algorithms, *GRAPH theory, *EMBEDDED computer systems
Abstract

Consider an n-vertex planar graph G. The depth of an embedding Γ of G is the maximum distance of its internal faces from the external one. Several researchers pointed out that the quality of a planar embedding can be measured in terms of its depth. We present an O( n)-time algorithm for computing an embedding of G with minimum depth. This bound improves on the best previous bound by an O( nlog n) factor. As a side effect, our algorithm improves the bounds of several algorithms that require the computation of a minimum-depth embedding. [ABSTRACT FROM AUTHOR]

Published
2011
Full Text
View/download PDF

6. On-line maintenance of triconnected components with SPQR-trees.

Author

Battista, G. and Tamassia, R.

Abstract

We consider the problem of maintaining on-line the triconnected components of a graph G. Let n be the current number of vertices of G. We present an O(n)-space data structure that supports insertions of vertices and edges, and queries of the type 'Are there three vertex-disjoint paths between vertices v and v?' A sequence of k operations takes time O(k·α(k, n)) if G is biconnected (α(k, n) denotes the well-known Ackermann's function inverse), and time O( n log n+ k) if G is not biconnected. Note that the bounds do not depend on the number of edges of G. We use the SPQR-tree, a versatile data structure that represents the decomposition of a biconnected graph with respect to its triconnected components, and the BC-tree, which represents the decomposition of a connected graph with respect to its biconnected components. [ABSTRACT FROM AUTHOR]

Published
1996
Full Text
View/download PDF

8. Optimal upward planarity testing of single-source digraphs

Author

Roberto Tamassia, Carlo Mannino, Paola Bertolazzi, Giuseppe Di Battista, Thomas Lengauer, P., Bertolazzi, DI BATTISTA, Giuseppe, C., Mannino, and R., Tamassia

Subjects
Discrete mathematics, SPQR tree, General Computer Science, General Mathematics, Parallel algorithm, planar graph, upward drawing, Graph theory, Digraph, Computer Science::Computational Geometry, Planarity testing, Upward planar drawing, Planar graph, Combinatorics, graph drawing, symbols.namesake, Graph drawing, parallel algorithm, TheoryofComputation_ANALYSISOFALGORITHMSANDPROBLEMCOMPLEXITY, symbols, triconnected components, MathematicsofComputing_DISCRETEMATHEMATICS, Mathematics
Abstract

A digraph is upward planar if it has a planar drawing such that all the edges are monotone with respect to the vertical direction. Testing upward planarity and constructing upward planar drawings is important for displaying hierarchical network structures, which frequently arise in software engineering, project management, and visual languages. In this paper we investigate upward planarity testing of single-source digraphs; we provide a new combinatorial characterization of upward planarity and give an optimal algorithm for upward planarity testing. Our algorithm tests whether a single-source digraph with n vertices is upward planar in O(n) sequential time, and in O(log n) time on a CRCW PRAM with $n \log \log n/\log n$ processors, using O(n,) space. The algorithm also constructs an upward planar drawing if the test is successful. The previously known best result is an O(n2)-time algorithm by Hutton and Lubiw [Proc. 2nd ACM--SIAM Symposium on Discrete Algorithms, SIAM, Philadelphia, 1991, pp. 203--211]. No efficient parallel algorithms for upward planarity testing were previously known.

Published
1998

Catalog

Books, media, physical & digital resources
See catalog results