Results 11 to 20 of about 211 (163)
Pathwidth of outerplanar graphs [PDF]
Journal of Graph Theory, 2006 AbstractWe are interested in the relation between the pathwidth of a biconnected outerplanar graph and the pathwidth of its (geometric) dual. Bodlaender and Fomin [3], after having proved that the pathwidth of every biconnected outerplanar graph is always at most twice the pathwidth of its (geometric) dual plus two, conjectured that there exists a ...
Coudert, David +2 more
openaire +3 more sources
Circular Separation Dimension of a Subclass of Planar Graphs [PDF]
Discrete Mathematics & Theoretical Computer Science, 2017 A pair of non-adjacent edges is said to be separated in a circular ordering of vertices, if the endpoints of the two edges do not alternate in the ordering.
Arpitha P. Bharathi +2 more
doaj +1 more source
Monotonic Representations of Outerplanar Graphs as Edge Intersection Graphs of Paths on a Grid
Journal of Graph Algorithms and Applications, 2022 In a representation of a graph $G$ as an edge intersection graph of paths on a grid (EPG) every vertex of $G$ is represented by a path on a grid and two paths share a grid edge iff the corresponding vertices are adjacent.
Eranda Çela, Elisabeth Gaar
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
Irreducible nonmetrizable path systems in graphs
Journal of Graph Theory, Volume 102, Issue 1, Page 5-14, January 2023., 2023 Abstract A path system P ${\mathscr{P}}$ in a graph G =(V , E ) $G=(V,E)$ is a collection of paths with a unique u v $uv$ path for every two vertices u , v ∈ V $u,v\in V$. We say that P ${\mathscr{P}}$ is consistent if for any path P ∈ P $P\in {\mathscr{P}}$, every subpath of P $P$ is also in P ${\mathscr{P}}$.
Daniel Cizma, Nati Linial
wiley +1 more source
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
Longest and shortest cycles in random planar graphs
Random Structures &Algorithms, Volume 60, Issue 3, Page 462-505, May 2022., 2022 Abstract Let be a graph chosen uniformly at random from the class of all planar graphs on vertex set with edges. We study the cycle and block structure of when . More precisely, we determine the asymptotic order of the length of the longest and shortest cycle in in the critical range when .
Mihyun Kang, Michael Missethan
wiley +1 more source
The Singularity of Oriented Outerplanar Graphs with a Given Number of Inner Edges
Journal of Mathematics, Volume 2022, Issue 1, 2022., 2022 A digraph is called oriented if there is at most one arc between two distinct vertices. An oriented graph is called nonsingular (singular) if its adjacency matrix A(D) is nonsingular (singular). In this paper, we study the singularity of the oriented outerplanar graph with a given number of inner edges.
Borui He +3 more
wiley +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
Site percolation and isoperimetric inequalities for plane graphs
Random Structures &Algorithms, Volume 58, Issue 1, Page 150-163, January 2021., 2021 We use isoperimetric inequalities combined with a new technique to prove upper bounds for the site percolation threshold of plane graphs with given minimum degree conditions. In the process we prove tight new isoperimetric bounds for certain classes of hyperbolic graphs.
John Haslegrave, Christoforos Panagiotis
wiley +1 more source