Results 71 to 80 of about 211 (163)
Triangle-Free Outerplanar 3-Graphs are Pairwise Compatibility Graphs
Journal of Graph Algorithms and Applications, 2013 A graph G = (V,E) is called a pairwise compatibility graph (PCG) if there exists an edge-weighted tree T and two non-negative real numbers dmin and dmax such that each vertex u′ ∈ V corresponds to a leaf u of T and there is an edge (u′, v′) ∈ E if and
Sammi Abida Salma +2 more
doaj +1 more source
Large Induced Acyclic and Outerplanar Subgraphs of 2-Outerplanar Graph [PDF]
Graphs and Combinatorics, 2017 Albertson and Berman conjectured that every planar graph has an induced forest on half of its vertices. The best known lower bound, due to Borodin, is that every planar graph has an induced forest on two fifths of its vertices. In a related result, Chartran and Kronk, proved that the vertices of every planar graph can be partitioned into three sets ...
Glencora Borradaile +2 more
openaire +2 more sources
The product structure of squaregraphs
Journal of Graph Theory, Volume 105, Issue 2, Page 179-191, February 2024.Abstract A squaregraph is a plane graph in which each internal face is a 4‐cycle and each internal vertex has degree at least 4. This paper proves that every squaregraph is isomorphic to a subgraph of the semistrong product of an outerplanar graph and a path.
Robert Hickingbotham +3 more
wiley +1 more source
k-colored Point-set Embeddability of Outerplanar Graphs
Journal of Graph Algorithms and Applications, 2008 This paper addresses the problem of designing drawing algorithms that receive as input a planar graph G, a partitioning of the vertices of G into k different semantic categories V0,…, Vk−1, and k disjoint sets S0, …, Sk−1 of points in the plane with |Vi|=
Emilio Di Giacomo +5 more
doaj +1 more source
Improved Bounds for Track Numbers of Planar Graphs
Journal of Graph Algorithms and Applications, 2020 A track layout of a graph consists of a vertex coloring and a total order of each color class, such that no two edges cross between any two color classes.
Sergey Pupyrev
doaj +1 more source
On the bend-number of planar and outerplanar graphs [PDF]
Discrete Applied Mathematics, 2012 appears in proceedings of 10th Latin American Symposium on Theoretical Informatics (LATIN 2012)
Heldt, Daniel +2 more
openaire +3 more sources
Star Coloring Outerplanar Bipartite Graphs
Discussiones Mathematicae Graph Theory, 2019 A proper coloring of the vertices of a graph is called a star coloring if at least three colors are used on every 4-vertex path. We show that all outerplanar bipartite graphs can be star colored using only five colors and construct the smallest known ...
Ramamurthi Radhika, Sanders Gina
doaj +1 more source
On the Planarity of Generalized Line Graphs
Theory and Applications of Graphs, 2019 One of the most familiar derived graphs is the line graph. The line graph $L(G)$ of a graph $G$ is that graph whose vertices are the edges of $G$ where two vertices of $L(G)$ are adjacent if the corresponding edges are adjacent in~$G$.
Khawlah H. Alhulwah +2 more
doaj +1 more source
Journal of Graph Algorithms and Applications, 2017 We introduce a new type of graph drawing called "rook-drawing". A rook-drawing of a graph $G$ is obtained by placing the $n$ nodes of $G$ on the intersections of a regular grid, such that each row and column of the grid supports exactly one node.
David Auber +3 more
doaj +1 more source