Results 11 to 20 of about 1,056 (209)
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
core +6 more sources
Outerplanar Graph Drawings with Few Slopes [PDF]
Computational Geometry, 2012 Major revision of the whole ...
Kolja B. Knauer +2 more
openaire +7 more sources
On the Edge-Length Ratio of Outerplanar Graphs [PDF]
Theoretical Computer Science, 2018 We show that any outerplanar graph admits a planar straightline drawing such that the length ratio of the longest to the shortest edges is strictly less than 2. This result is tight in the sense that for any $ε> 0$ there are outerplanar graphs that cannot be drawn with an edge-length ratio smaller than $2 - ε$.
Lazard, Sylvain +2 more
openaire +7 more sources
Outerplanar Partitions of Planar Graphs
Journal of Combinatorial Theory, Series B, 1996 zbMATH Open Web Interface contents unavailable due to conflicting licenses.
Kedlaya, Kiran S.
openaire +3 more sources
Proximity Drawings of Outerplanar Graphs.
, 1997 A proximity drawing of a graph is one in which pairs of adjacent vertices are drawn relatively close together according to some proximity measure while pairs of non-adjacent vertices are drawn relatively far apart. The fundamental question concerning proximity drawability is: Given a graph G and a definition of proximity, is it possible to construct a ...
W. Lenhart, LIOTTA, Giuseppe
core +4 more sources
Pathlength of Outerplanar Graphs
Theoretical Computer Science, 2022 A path-decomposition of a graph G = (V, E) is a sequence of subsets of V , called bags, that satisfy some connectivity properties. The length of a path-decomposition of a graph G is the greatest distance between two vertices that belong to a same bag and the pathlength, denoted by pl(G), of G is the smallest length of its path-decompositions.
Dissaux, Thomas, Nisse, Nicolas
openaire +4 more sources
Splitting Plane Graphs to Outerplanarity
Journal of Graph Algorithms and Applications, 2023 Vertex splitting replaces a vertex by two copies and partitions its incident edges amongst the copies. This problem has been studied as a graph editing operation to achieve desired properties with as few splits as possible, most often planarity, for which the problem is NP-hard.Here we study how to minimize the number of splits to turn a plane graph ...
Martin Gronemann +2 more
openaire +2 more sources
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
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
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