Results 21 to 30 of about 3,679 (179)
Pathwidth of outerplanar graphs [PDF]
Journal of Graph Theory, 2006 We are interested in the relation between the pathwidth of a biconnected outerplanar graph and the pathwidth of its (geometric) dual. Bodlaender and Fomin, 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 constant $c ...
Coudert, David +2 more
openaire +5 more sources
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
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
Nullspace Embeddings for Outerplanar Graphs [PDF]
, 2017 21 pages.
Lovász, L., Schrijver, A.
openaire +4 more sources
Large Induced Acyclic and Outerplanar Subgraphs of 2-Outerplanar Graph [PDF]
Graphs and Combinatorics, 2017 13 pages, 7 figures.
Glencora Borradaile +2 more
openaire +2 more sources
Strongly Monotone Drawings of Planar Graphs [PDF]
, 2016 A straight-line drawing of a graph is a monotone drawing if for each pair of vertices there is a path which is monotonically increasing in some direction, and it is called a strongly monotone drawing if the direction of monotonicity is given by the ...
Felsner, Stefan +5 more
core +2 more sources
Algorithms, 2013 The maximum common connected edge subgraph problem is to find a connected graph with the maximum number of edges that is isomorphic to a subgraph of each of the two input graphs, where it has applications in pattern recognition and chemistry.
Takeyuki Tamura, Tatsuya Akutsu
doaj +1 more source
Double domination in maximal outerplanar graphs
Open Mathematics, 2022 In graph GG, a vertex dominates itself and its neighbors. A subset S⊆V(G)S\subseteq V\left(G) is said to be a double-dominating set of GG if SS dominates every vertex of GG at least twice.
Zhuang Wei, Zheng Qiuju
doaj +1 more source
Directed Acyclic Outerplanar Graphs Have Constant Stack Number [PDF]
TheoretiCSThe stack number of a directed acyclic graph $G$ is the minimum $k$ for which there is a topological ordering of $G$ and a $k$-coloring of the edges such that no two edges of the same color cross, i.e., have alternating endpoints along the topological ...
Paul Jungeblut +2 more
doaj +1 more source
On the spread of outerplanar graphs
Special Matrices, 2022 The spread of a graph is the difference between the largest and most negative eigenvalue of its adjacency matrix. We show that for sufficiently large nn, the nn-vertex outerplanar graph with maximum spread is a vertex joined to a linear forest with Ω(n ...
Gotshall Daniel +2 more
doaj +1 more source