Results 21 to 30 of about 231 (167)
Planar, Outerplanar, and Toroidal Graphs of the Generalized Zero‐Divisor Graph of Commutative Rings
Journal of Mathematics, Volume 2021, Issue 1, 2021., 2021 Let A be a commutative ring with unity and let set of all zero divisors of A be denoted by ZA. An ideal ℐ of the ring A is said to be essential if it has a nonzero intersection with every nonzero ideal of A. It is denoted by ℐ≤eA. The generalized zero‐divisor graph denoted by ΓgA is an undirected graph with vertex set ZA∗ (set of all nonzero zero ...
Abdulaziz M. Alanazi +3 more
wiley +1 more source
Straight-Line Grid Drawings of Label-Constrained Outerplanar Graphs with O(n log n) Area
Journal of Graph Algorithms and Applications, 2011 A straight-line grid drawing of a planar graph G is a drawing of G on an integer grid such that each vertex is drawn as a grid point and each edge is drawn as a straight-line segment without edge crossings.
Md. Rezaul Karim +2 more
doaj +1 more source
Approximation of pathwidth of outerplanar graphs [PDF]
Journal of Algorithms, 2001 Summary: There exists a polynomial time algorithm to compute the pathwidth of outerplanar graphs, but the large exponent makes this algorithm impractical. In this paper, we give an algorithm that, given a biconnected outerplanar graph \(G\), finds a path decomposition of \(G\) of pathwidth at most twice the pathwidth of \(G\) plus one.
Hans L. Bodlaender, Fedor V. Fomin
openaire +6 more sources
Planar L-Drawings of Bimodal Graphs
Journal of Graph Algorithms and Applications, 2022 In a planar L-drawing of a directed graph (digraph) each edge $e$ is represented as a polyline composed of a vertical segment starting at the tail of $e$ and a horizontal segment ending at the head of $e$. Distinct edges may overlap, but not cross.
Patrizio Angelini +3 more
doaj +1 more source
The Electronic Journal of Combinatorics, 2017 A map is outerplanar if all its vertices lie in the outer face. We enumerate various classes of rooted outerplanar maps with respect to the number of edges and vertices. The proofs involve several bijections with lattice paths. As a consequence of our results, we obtain an efficient scheme for encoding simple outerplanar maps.
Ivan Geffner, Marc Noy
openaire +2 more sources
I/O-Optimal Algorithms for Outerplanar Graphs
Journal of Graph Algorithms and Applications, 2004 We present linear-I/O algorithms for fundamental graph problems on embedded outerplanar graphs. We show that breadth-first search, depth-first search, single-source shortest paths, triangulation, and computing an ϵ-separator of size O(1/ϵ) take O(scan(N))
Anil Maheshwari, Norbert Zeh
doaj +1 more source
A Characterization of Maximal Outerplanar-Open Distance Pattern Uniform Graphs
مجلة بغداد للعلوم, 2023 Let A ⊆ V(H) of any graph H, every node w of H be labeled using a set of numbers; , where d(w,v) denotes the distance between node w and the node v in H, known as its open A-distance pattern. A graph H is known as the open distance-pattern uniform (odpu)
BIBIN K JOSE
doaj +1 more source
Genus Distributions of Cubic Outerplanar Graphs
Journal of Graph Algorithms and Applications, 2011 We present a quadratic-time algorithm for computing the genus distribution of any 3-regular outerplanar graph. Although recursions and some formulas for genus distributions have previously been calculated for bouquets and for various kinds of ladders ...
Jonathan Gross
doaj +1 more source
Free Choosability of Outerplanar Graphs [PDF]
Graphs and Combinatorics, 2015 zbMATH Open Web Interface contents unavailable due to conflicting licenses.
Aubry, Yves +2 more
openaire +2 more sources
The Degree-Diameter Problem for Outerplanar Graphs
Discussiones Mathematicae Graph Theory, 2017 For positive integers Δ and D we define nΔ,D to be the largest number of vertices in an outerplanar graph of given maximum degree Δ and diameter D. We prove that nΔ,D=ΔD2+O (ΔD2−1)$n_{\Delta ,D} = \Delta ^{{D \over 2}} + O\left( {\Delta ^{{D \over 2 ...
Dankelmann Peter +2 more
doaj +1 more source